提问



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


在b +树中执行上述操作有什么好处吗?


为什么不在任何地方使用b-trees而不是b + tree,直觉上它们似乎更快?


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

最佳参考


下图有助于显示B +树和B树之间的差异。


B +树的优点:



  • 由于B +树没有与内部节点相关的数据,因此更多的密钥可以放在内存页面上。因此,为了访问叶子节点上的数据,需要更少的缓存未命中。

  • B +树的叶节点是链接的,因此对树中的所有对象进行全扫描只需要一个线性遍历所有叶节点。另一方面,B树需要遍历树中的每个级别。这种全树遍历可能涉及比B +叶子的线性遍历更多的缓存未命中。



B树的优点:



  • 由于B树包含每个密钥的数据,因此频繁访问的节点可以更靠近根,因此可以更快地访问。








其它参考1


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


缺点是,当您在内部节点中找到匹配项时,没有早期出局。但由于两个数据结构都有巨大的扇出,所以绝大多数匹配都会在叶子节点上进行,平均而言B +树的效率更高。

其它参考2


B +树执行全扫描更容易,性能更高,就像查看树索引的每个数据一样,因为终端节点形成链表。要使用B树进行完整扫描,您需要执行完整的树遍历以查找所有数据。


另一方面,当您进行搜索(按键查找特定数据)时,B树可以更快,特别是当树驻留在RAM或其他非块存储中时。由于您可以提升树中常用节点,因此获取数据所需的比较较少。

其它参考3


数据库系统概念的示例第5


B + - 树



相应的B树


其它参考4



  

      
  1. 在B树中搜索存储在内部或叶节点中的密钥和数据。但是在B + -tree数据中只存储叶子节点。

  2.   
  3. 搜索B +树中的任何数据非常容易,因为所有数据都在叶节点中找到。搜索B树需要完整遍历。

  4.   
  5. 在B树中,可以在叶节点或内部节点中找到数据。删除内部节点非常复杂。在B +树中,数据仅在叶节点中找到。删除叶节点很容易。

  6.   
  7. 在B树中插入比B +树更复杂。

  8.   
  9. B +树存储冗余搜索关键字,但B树没有冗余值。

  10.   
  11. 在B +树中,叶节点数据按顺序链接列表排序,但在B树中,叶节点不能使用链接列表存储。许多数据库系统的实现更喜欢B +树的结构简单性。

  12.   


其它参考5


定义快得多。渐渐地,他们大致相同。不同之处在于他们如何利用二级存储。维基百科关于B树和B +树的文章看起来非常值得信赖。[1] [2]

其它参考6


Adegoke A,Amit


我想人们缺少的一个关键点是数据和指针之间的差异,如本节所述。


指针:指向其他节点的指针。


数据: - 在数据库索引的上下文中,数据只是指向其他位置的实际数据(行)的另一个指针。


因此,在B树的情况下,每个节点具有三个信息密钥,指向与密钥相关联的数据的指针和指向子节点的指针。


在B +树中,内部节点保持键和指向子节点的指针,而叶节点保存键和指向相关数据的指针。这允许给定大小的节点具有更多数量的密钥。节点的大小主要由块大小决定。


上面解释了每个节点拥有更多密钥的优点,因此我将节省我的打字工作量。

其它参考7


B + Trees在基于块的存储方面特别好(例如:硬盘)。考虑到这一点,你可以获得几个优势,例如(从我的头脑中):



  • 高扇出/低深度:这意味着您必须获得更少的块来获取数据。如果数据与指针混合,每次读取的指针都会减少,因此您需要更多的搜索来获取数据

  • 简单且一致的块存储:内部节点有N个指针,没有别的,叶子节点有数据,没有别的。这使得解析,调试甚至重构变得容易。

  • 高密钥密度意味着顶级节点几乎肯定在缓存上,在许多情况下,所有内部节点都会快速缓存,因此只有数据访问才能进入磁盘。


其它参考8


在B + Tree中,由于只有指针存储在内部节点中,因此它们的大小明显小于B树的内部节点(存储数据+密钥)。
因此,可以在单个磁盘读取中从外部存储器获取B +树的索引,进行处理以找到目标的位置。如果它是B树,则每个决策过程都需要磁盘读取。希望我明白我的观点! :)

其它参考9


B树和B +树之间的主要区别是B树消除了搜索键值的冗余存储。由于搜索键不在B树中重复,我们可能无法使用较少的树节点存储索引然而,由于出现在非叶节点中的搜索关键字出现在B树中的其他地方,我们不得不为非叶节点中的每个搜索关键字包括一个额外的指针字段。
它们是B树的空间优势,因为重复不会发生并且可以用于大型指数。

其它参考10


**



  B-Tree的主要缺点是遍历键的难度
  顺序。 B + Tree保留了快速随机访问属性
  B-Tree同时还允许快速顺序访问



**
ref:数据结构使用C//作者:Aaro M Tenenbaum


http://books.google.co.in/books?id=X0Cd1Pr2W0gC\u0026amp;pg=PA456\u0026amp;lpg=PA456\u0026amp;dq=drawback+of+B-Tree+is+the+difficulty+of+Traversing+the+keys+依次&安培;源= BL&安培; OTS=pGcPQSEJMS&安培; SIG=F9MY7zEXYAMVKl_Sg4W-0LTRor8&安培; HL=EN&安培; SA=X&安培; EI=nD5AUbeeH4zwrQe12oCYAQ&安培; VED=0CDsQ6AEwAg#v=onepage&安培; q =缺点%20of%20B-树%图20是%第二十条% 20difficulty%20of%20Traversing%第二十条%20keys%20sequentially&安培; F =假[3]

其它参考11


B +发束的一种可能用途是它适用于某些情况
树长得太大以至于无法适应可用的树
记忆。因此,您通常希望做多个I/O.经常
确实发生了B +树的使用,即使它实际上适合
内存,然后您的缓存管理器可能会永久保留它。但
这是一个特例,而不是一般情况,缓存策略是一个
与B +树维护分开。


此外,在B +树中,叶页被链接在一起
链接列表(或双向链表),用于优化遍历
(用于范围搜索,排序等)。所以指针的数量是
使用的特定算法的功能。

其它参考12


B +树是一棵平衡树,其中从树根到叶子的每条路径长度相同,树的每个非叶节点都在[[n/2]]和[[n]]个子节点之间,其中n是为特定树修复。它包含索引页面和数据页面。
二叉树每个父节点只有两个子节点,B +树可以为每个父节点提供可变数量的子节点

其它参考13


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


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


B +树将密钥与数据分开。


但是如果您的数据大小较小,那么您可以使用B树存储的密钥存储它们。