B树和B+树有什么区别?

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

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

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

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

263243 次浏览
小开

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

小开
B+树的一个可能的用途是它适用于各种情况 哪里的树长得太大，以至于它不适合可用 内存。因此，您通常期望执行多个I/O。
B+树确实经常被使用，即使它实际上适合 内存，然后你的缓存管理器可能会永久保存它。但 这是一个特殊的情况，而不是一般的情况，缓存策略是 与B+树的维护分开 同样，在B+树中，叶子页链接在一起 一个链表(或双链表)，用于优化遍历 (用于范围搜索、排序等)。所以指针的数量是 所使用的特定算法的函数
小开

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

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

小开

B+树尤其适用于基于块的存储(例如:硬盘)。考虑到这一点，你会得到几个优势，例如(从我的脑海中):

  • 高扇出/低深度:这意味着你必须获得更少的块来获取数据。由于数据与指针混合在一起，每次读取得到的指针更少，因此需要更多的查找来获取数据

  • 简单一致的块存储:内部节点有N个指针，没有其他，叶节点有数据，没有其他。这使得它易于解析、调试甚至重构。

  • 高键密度意味着顶部节点几乎肯定在缓存中，在许多情况下，所有内部节点都被快速缓存，因此只有数据访问必须到磁盘。

小开

由于终端节点形成了一个链表，B+树更容易进行全面扫描，而且性能更高，可以查看树索引的每一块数据。要使用B-Tree进行完整扫描，您需要进行完整的树遍历以查找所有数据。

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

小开
在B+树中，由于只有指针存储在内部节点中，因此它们的大小明显小于B树的内部节点(存储数据+键)。 因此，B+树的索引可以在一次磁盘读取中从外部存储中提取，处理后找到目标的位置。如果它是一个B树，那么每个决策过程都需要读取磁盘。希望我把我的观点讲清楚了!:) < / p >
小开
B+树是一种平衡树，其中从树的根到叶子的每条路径都是相同的长度，树的每个非叶子节点都有[n/2]到[n]个子节点，其中n是特定树的固定值。它包含索引页和数据页。 二叉树的每个父节点只有两个子节点，B+树的每个父节点

可以有不同数量的子节点
小开

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

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

B+树将键和数据分开。

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

小开

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

B+树的优点:

  • 因为B+树没有与内部节点相关联的数据，所以一页内存可以容纳更多的键。因此，为了访问叶节点上的数据，它将需要更少的缓存遗漏。
  • B+树的叶节点是链接的，因此要对树中的所有对象进行全面扫描，只需要对所有叶节点进行一次线性遍历。另一方面，B树需要遍历树中的每一层。这种全树遍历可能比B+叶的线性遍历涉及更多的缓存遗漏。

B树的优点:

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

B和B+树

小开
B-树和B+树的主要区别在于B-树消除了搜索键值的冗余存储。由于搜索键在B-树中不重复，我们可能无法使用比对应的B+树索引中更少的树节点来存储索引。然而，由于出现在非叶节点中的搜索键在b树的其他地方都不会出现，我们被迫为非叶节点中的每个搜索键包含一个额外的指针字段。 它们是b -树的空间优势，因为不会发生重复，可以用于大索引
小开

**

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

< p > * * 参考:Data Structures Using C// Author: Aaro M Tenenbaum

< a href = " http://books.google.co.in/books?id=X0Cd1Pr2W0gC& pg = PA456&液化石油气= PA456& dq =缺点+ + b - tree +是+ + +的+穿越困难+ +键+ sequentially&源= bl& ots = pGcPQSEJMS&团体= F9MY7zEXYAMVKl_Sg4W-0LTRor8& hl = en& sa = X& ei = nD5AUbeeH4zwrQe12oCYAQ& ved = 0 cdsq6aewag # v = onepage& q = % 20的缺点% 20 b - tree % 20的% 20困难% 20 % 20 % 20遍历% 20 % 20键% 20 sequentially& f = false”rel = " noreferrer " > http://books.google.co.in/books?id=X0Cd1Pr2W0gC& pg = PA456&液化石油气= PA456& dq =缺点+ + b - tree +是+ + +的+穿越困难+ +键+ sequentially&源= bl& ots = pGcPQSEJMS&团体= F9MY7zEXYAMVKl_Sg4W-0LTRor8& hl = en& sa = X& ei = nD5AUbeeH4zwrQe12oCYAQ& ved = 0 cdsq6aewag # v = onepage& q = % 20的缺点% 20 b - tree % 20的% 20困难% 20 % 20 % 20遍历% 20 % 20键% 20 sequentially& f = false < / >

小开

Adegoke A, Amit

我想你们忽略的一个关键点是数据和指针之间的区别，就像本节中解释的那样。

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

数据:—在数据库索引的上下文中，数据只是另一个指向其他地方的真实数据(行)的指针。

因此在B树的情况下，每个节点都有三个信息键，指向与键相关的数据的指针和指向子节点的指针。

在B+树中，内部节点保存指向子节点的键和指针，而叶节点保存指向相关数据的键和指针。这允许为给定大小的节点提供更多的键数。节点大小主要由块大小决定。

每个节点拥有更多键的好处已经在上面解释过了，这样可以节省我的输入工作量。

小开
  1. 在B树中，搜索键和数据存储在内部节点或叶节点中。但在B+树中，数据只存储在叶节点中。
  2. B+树的全扫描非常容易，因为所有数据都在叶节点中找到。B树的完整扫描需要完整的遍历。
  3. 在B树中，数据可以在叶节点或内部节点中找到。删除内部节点非常复杂。在B+树中，数据只能在叶节点中找到。叶节点的删除很容易。
  4. 插入B树比插入B+树更复杂。
  5. B+树存储冗余搜索键，但B树没有冗余值。
  6. 在B+树中，叶子节点数据按顺序链表排序，但在B树中，叶子节点不能使用链表存储。许多数据库系统的实现更倾向于结构简单的B+树。
小开

数据库系统概念示例

< p > B +树 < img src = " https://i.stack.imgur.com/rwrgt.png " alt = " B +树”> < / p > < p >相应的b -树 < img src = " https://i.stack.imgur.com/gikEE.png " alt = " Btree " > < / p >

提交答案