在b-树中,您可以将键和数据存储在内部节点和叶节点中,但在b+树中,您必须仅将数据存储在叶节点中。
在b+树中这样做有什么好处吗?
为什么不在所有地方都使用b-树而不是b+树,因为直觉上它们看起来更快?
我的意思是,为什么需要在b+树中复制键(数据)?
在b-树中,您可以将键和数据存储在内部节点和叶节点中,但在b+树中,您必须仅将数据存储在叶节点中。
在b+树中这样做有什么好处吗?
为什么不在所有地方都使用b-树而不是b+树,因为直觉上它们看起来更快?
我的意思是,为什么需要在b+树中复制键(数据)?
当前回答
由于终端节点形成了一个链表,B+树更容易进行全面扫描,而且性能更高,可以查看树索引的每一块数据。要使用B-Tree进行完整扫描,您需要进行完整的树遍历以查找所有数据。
另一方面,当您执行seek(按键查找特定数据段)时,B-Trees可以更快,特别是当树驻留在RAM或其他非块存储中时。由于可以提升树中常用的节点,因此获取数据所需的比较较少。
其他回答
在B+树中,由于只有指针存储在内部节点中,因此它们的大小明显小于B树的内部节点(存储数据+键)。 因此,B+树的索引可以在一次磁盘读取中从外部存储中提取,处理后找到目标的位置。如果它是一个B树,那么每个决策过程都需要读取磁盘。希望我把我的观点讲清楚了!:)
B+树相对于B树的主要优点是,它们允许您通过删除指向数据的指针来打包更多指向其他节点的指针,从而增加扇出并潜在地降低树的深度。
缺点是,当您可能在内部节点中找到匹配时,无法提前退出。但由于这两种数据结构都有巨大的扇出,绝大多数匹配都将在叶节点上,这使得B+树的平均效率更高。
B+树的一个可能的用途是它适用于各种情况 哪里的树长得太大,以至于它不适合可用 内存。因此,您通常期望执行多个I/O。 B+树确实经常被使用,即使它实际上适合 内存,然后你的缓存管理器可能会永久保存它。但 这是一个特殊的情况,而不是一般的情况,缓存策略是 与B+树的维护分开。
另外,在B+树中,叶子页以 一个链表(或双链表),用于优化遍历 (用于范围搜索、排序等)。所以指针的数量是 所使用的特定算法的函数。
下图有助于显示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树包含每个键的数据,所以经常访问的节点可以位于更靠近根的位置,因此可以更快地访问。
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.