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

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

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

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


当前回答

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

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

其他回答

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

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

B+树将键和数据分开。

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

In a B tree search keys and data are stored in internal or leaf nodes. But in a B+-tree data is stored only in leaf nodes. Full scan of a B+ tree is very easy because all data are found in leaf nodes. Full scan of a B tree requires a full traversal. In a B tree, data may be found in leaf nodes or internal nodes. Deletion of internal nodes is very complicated. In a B+ tree, data is only found in leaf nodes. Deletion of leaf nodes is easy. Insertion in B tree is more complicated than B+ tree. B+ trees store redundant search keys but B tree has no redundant value. In a B+ tree, leaf node data is ordered as a sequential linked list but in a B tree the leaf node cannot be stored using a linked list. Many database systems' implementations prefer the structural simplicity of a B+ tree.

下图有助于显示B+树和B树之间的区别。

B+树的优点:

Because B+ trees don't have data associated with interior nodes, more keys can fit on a page of memory. Therefore, it will require fewer cache misses in order to access data that is on a leaf node. The leaf nodes of B+ trees are linked, so doing a full scan of all objects in a tree requires just one linear pass through all the leaf nodes. A B tree, on the other hand, would require a traversal of every level in the tree. This full-tree traversal will likely involve more cache misses than the linear traversal of B+ leaves.

B树的优点:

因为B树包含每个键的数据,所以经常访问的节点可以位于更靠近根的位置,因此可以更快地访问。


数据库系统概念示例

B+树

相应的b -树

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