在b-树中,您可以将键和数据存储在内部节点和叶节点中,但在b+树中,您必须仅将数据存储在叶节点中。

在b+树中这样做有什么好处吗?

为什么不在所有地方都使用b-树而不是b+树,因为直觉上它们看起来更快?

我的意思是,为什么需要在b+树中复制键(数据)?


当前回答

定义“快得多”。渐近地它们是相同的。不同之处在于它们如何使用二级存储。维基百科上关于B-树和B+树的文章看起来相当可信。

其他回答

B+树是一种平衡的树,其中从树的根到叶子的每条路径都是相同的长度,树的每个非叶子节点都有[n/2]到[n]个子节点,其中n对于特定的树是固定的。它包含索引页和数据页。 二叉树的每个父节点只有两个子节点,而B+树的每个父节点可以有不同数量的子节点

举个例子——你有一个每一行都有大量数据的表。这意味着对象的每个实例都是大的。

如果在这里使用B树,那么大部分时间都花在扫描带有数据的页面上——这是没有用的。在数据库中,这就是使用B+树来避免扫描对象数据的原因。

B+树将键和数据分开。

但如果你的数据量比较小,你可以用键来存储它们就像B树那样。

B+树相对于B树的主要优点是,它们允许您通过删除指向数据的指针来打包更多指向其他节点的指针,从而增加扇出并潜在地降低树的深度。

缺点是,当您可能在内部节点中找到匹配时,无法提前退出。但由于这两种数据结构都有巨大的扇出,绝大多数匹配都将在叶节点上,这使得B+树的平均效率更高。

The primary distinction between B-tree and B+tree is that B-tree eliminates the redundant storage of search key values.Since search keys are not repeated in the B-tree,we may not be able to store the index using fewer tree nodes than in corresponding B+tree index.However,since search key that appear in non-leaf nodes appear nowhere else in B-tree,we are forced to include an additional pointer field for each search key in a non-leaf node. Their are space advantages for B-tree, as repetition does not occur and can be used for large indices.

在B+树中,由于只有指针存储在内部节点中,因此它们的大小明显小于B树的内部节点(存储数据+键)。 因此,B+树的索引可以在一次磁盘读取中从外部存储中提取,处理后找到目标的位置。如果它是一个B树,那么每个决策过程都需要读取磁盘。希望我把我的观点讲清楚了!:)