B树和B +树之间的差异
dha*_*0us 281 database data-structures
在b树中,您可以将密钥和数据存储在内部和叶节点中,但是在b +树中,您必须仅将数据存储在叶节点中.
在b +树中执行上述操作有什么好处吗？
为什么不在任何地方使用b-trees而不是b + tree,直觉上它们似乎更快？
我的意思是,为什么你需要在b +树中复制密钥(数据)？
Ros*_*one 399
下图有助于显示B +树和B树之间的差异.
B +树的优点:
- 因为B +树没有与内部节点相关联的数据,所以更多的键可以放在内存页面上.因此,为了访问叶节点上的数据,它将需要更少的高速缓存未命中.
- B +树的叶节点是链接的,因此对树中的所有对象进行全扫描只需要一个线性通过所有叶节点.另一方面,AB树需要遍历树中的每个级别.这种全树遍历可能涉及比B +叶的线性遍历更多的缓存未命中.
B树的优点:
- 由于B树包含每个密钥的数据,因此频繁访问的节点可以更靠近根,因此可以更快地访问.
- @TLE好问题!是.硬盘驱动器一次访问最少一页内存,因此我们希望将所有指针放在单页内存中.我们希望每个叶子访问只需要一个磁盘读取,因此我们不希望为叶子分配超过页面大小的指针.如果我们用一个页面大小的指针填充一个叶子,然后我们想要添加另一个指向这个叶子的指针,我们创建这个节点的两个子节点,并给每个新子节点提供一半叶子的指针.当然,可能需要进行一些改组以确保树木的高度保持在最低水平.这有帮助吗？ (36认同)
- 很抱歉碰到这么老的帖子,但@ Babyburger关于camino评论如何正确的评论实际上并不属实; 事实上,B树没有连接叶节点.肯定是B +. (8认同)
- 他们对叶节点中条目数的限制是什么？ (2认同)
小智 103
B +树相对于B树的主要优点是它们允许您通过删除指向数据的指针来包含更多指向其他节点的指针,从而增加扇出并可能减少树的深度.
缺点是,当您在内部节点中找到匹配项时,没有早期出局.但由于两个数据结构都有巨大的扇出,所以绝大多数匹配都会在叶子节点上进行,这使得B +树的平均效率更高.
- 我更喜欢杰夫的答案，因为它强调了进行全面扫描时效率的差异。 (2认同)
- @JorgeBucaran fanout =来自节点的边数 (2认同)
Jef*_* Mc 31
B +树执行全扫描更容易,性能更高,就像查看树索引的每一段数据一样,因为终端节点形成链表.要使用B树进行完整扫描,您需要进行完整的树遍历以查找所有数据.
另一方面,当您进行搜索(通过密钥查找特定数据)时,B树可以更快,特别是当树驻留在RAM或其他非块存储中时.由于您可以提升树中常用节点,因此获取数据所需的比较较少.
- 您是否同意，B+ 树将用于可能对所有数据进行顺序读取从而能够遍历叶子的情况。那么 B 树对于随机访问情况来说是理想的选择吗？ (2认同)
and*_*ter 28
- 在B树中搜索密钥和存储在内部或叶节点中的数据.但在B + -tree数据中只存储叶子节点.
- 搜索B +树中的任何数据非常容易,因为所有数据都在叶节点中找到.搜索B树需要完整遍历.
- 在B树中,可以在叶节点或内部节点中找到数据.删除内部节点非常复杂.在B +树中,数据仅在叶节点中找到.删除叶节点很容易.
- B树中的插入比B +树更复杂.
- B +树存储冗余搜索关键字,但B树没有冗余值.
- 在B +树中,叶节点数据按顺序链接列表排序,但在B树中,不能使用链接列表存储叶节点.许多数据库系统的实现更喜欢B +树的结构简单性.
cam*_*ino 14
数据库系统概念示例第5
B + - 树
相应的B树
- 我认为B树没有链接到该节点的子节点的链接。例如，从“ Clearview bucket”到“ Mianus Bucket”。无论如何，这样做并没有多大意义，因为在两者之间您拥有“ Downtown bucket”，如果您要在B树中进行索引扫描（需要回溯），则会进行大量搜索。你从哪儿得到的？ (3认同)
- @EvanCarroll 数据库系统概念 5，可能需要和作者确认一下 :) (2认同)
小智 11
Adegoke A,Amit
我想人们缺少的一个关键点是数据和指针之间的差异,如本节所述.
指针:指向其他节点的指针.
数据: - 在数据库索引的上下文中,数据只是指向其他位置的实际数据(行)的另一个指针.
因此,在B树的情况下,每个节点具有三个信息密钥,指向与密钥相关联的数据的指针和指向子节点的指针.
在B +树内部节点保持键和指向子节点的指针,而叶节点保持键和指向相关数据的指针.这允许给定大小的节点具有更多数量的密钥.节点的大小主要由块大小决定.
上面解释了每个节点拥有更多密钥的优势,因此我将节省我的打字工作量.
Jav*_*ier 10
B + Trees在基于块的存储中特别好(例如:硬盘).考虑到这一点,你可以获得几个优势,例如(从我的头脑中):
高扇出/低深度:这意味着您必须获得更少的块来获取数据.如果数据与指针混合在一起,则每次读取都会获得较少的指针,因此您需要更多的搜索来获取数据
简单一致的块存储:内部节点有N个指针,没有别的,叶子节点有数据,没有别的.这使得解析,调试甚至重构变得容易.
高密钥密度意味着顶级节点几乎肯定在缓存上,在许多情况下,所有内部节点都可以快速缓存,因此只有数据访问才能进入磁盘.
- 主要用于记忆中的树木; 但还有其他流行的选择,如红黑树,跳过列表等. (2认同)
- @AdegokeA：一个B+树有两种节点：内部节点只有键和指针，没有数据；和叶节点，有数据，没有指针。这允许在每个内部节点上使用最大数量的键。如果您将数据存储在内部节点上，那么您可以容纳更少的指针并且您的树变得更高。 (2认同)
小智 6
**
B-Tree 的主要缺点是难以按顺序遍历键。B+ Tree 保留了 B-Tree 的快速随机访问特性，同时也允许快速顺序访问
** 参考：使用 C 的数据结构// 作者：Aaro M Tenenbaum
- 这应该是正确的答案。简而言之：参考位置。 (2认同)
小智 5
在B + Tree中,由于只有指针存储在内部节点中,因此它们的大小明显小于B树的内部节点(存储数据+密钥).因此,B +树的索引可以在单个磁盘读取中从外部存储器获取,处理以找到目标的位置.如果它是B树,则每个决策过程都需要读取磁盘.希望我明白我的观点!:)