B树和B +树之间的差异

B树中 ,可以将内存和叶节点中的密钥和数据都存储,但在b +树中, 只能将数据存储在叶节点中

在b +树中做上述有没有什么好处?

为什么不在所有地方都使用b树而不是b +树,直观地看起来好多了?

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

下图显示了B +树和B树之间的区别。

B +树的优点:

  • 由于B +树没有与内部节点相关的数据,更多的键可以放在内存页面上。 因此,为了访问叶节点上的数据,将需要更less的高速caching未命中。
  • B +树的叶节点是链接的,所以对树中所有对象进行全面扫描只需要一个线性遍历所有叶节点。 另一方面,AB树需要遍历树中的每一层。 这种全树遍历可能涉及比B +树叶的线性遍历更多的caching未命中。

B树的优势:

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

B和B +树

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

缺点是当你在一个内部节点中find一个匹配时,就不会有早期的输出。 但是由于这两个数据结构都有大量的扇出,所以绝大多数的匹配都会在叶节点上,从而使得B +树的平均效率更高。

由于terminal节点形成一个链表,所以B +树更容易和更高效地执行全面扫描,就像查看树索引的每一条数据一样。 要使用B-Tree进行全面扫描,您需要执行完整的树遍历以查找所有数据。

另一方面,当你寻找一个特定的数据片段时(特别是当这个数据块驻留在RAM或其他非块存储器中时),B-树会更快。 由于您可以提升树中常用的节点,所以需要较less的比较来获取数据。

  1. 在B树中search关键字和数据存储在内部或叶节点。 但在B +树数据中只存储叶节点。
  2. 在B +树中search任何数据是非常容易的,因为所有的数据都在叶节点中find。 在B树中,无法在叶节点中find数据。
  3. 在B树中,可以在叶节点或内部节点中find数据。 内部节点的删除非常复杂。 在B +树中,只能在叶节点中find数据。 删除叶节点很容易。
  4. B树中的插入比B +树更复杂。
  5. B +树存储冗余search关键字,但B树没有冗余值。
  6. 在B +树中,叶节点数据按顺序链接列表sorting,但在B树中,叶节点不能使用链表进行存储。 许多数据库系统的实现更喜欢B +树的结构简单性。

定义“更快”。 渐近地他们差不多。 差异在于他们如何利用二级存储。 B树和B +树上的维基百科文章看起来非常值得信赖。

数据库系统概念示例5

B + – 树 B +树

相应的B树 B树

Adegoke A,Amit

我猜想人们缺less的一个关键点是数据和指针之间的区别,正如本节所述。

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

数据: – 在数据库索引的情况下,数据只是指向其他地方的真实数据(行)的另一个指针。

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

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

上面已经解释了每个节点具有更多密钥的好处,所以我将节省我的打字力度。

在B +树中,由于只有指针被存储在内部节点中,所以它们的大小比B树的内部节点(其存储数据+密钥)小得多。 因此,B +树的索引可以在单个磁盘读取中从外部存储器获取,处理以find目标的位置。 如果它是B树,每个决策过程都需要磁盘读取。 希望我明确了我的观点! 🙂

B +树在基于块的存储(例如:硬盘)方面尤其出色。 考虑到这一点,你会得到几个优点,例如(从我的头顶):

  • 高扇出/低深度:这意味着你必须得到更less的块来获取数据。 数据与指针混合在一起,每个读取的指针都会减less,所以您需要更多的查找来获取数据

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

  • 高密度密度意味着顶级节点几乎肯定在高速caching上,在很多情况下,所有内部节点都得到快速高速caching,所以只有数据访问权限才能到达磁盘。

B树和B +树的主要区别在于B树消除了search关键字值的冗余存储。由于search关键字在B-树中不重复,所以我们可能无法使用更less的树节点来存储索引然而,由于出现在非叶节点中的search关键字在B树中没有出现,所以我们被迫在非叶节点中为每个search关键字包括一个额外的指针字段。 它们是B-树的空间优势,因为重复不会发生,可用于大型指数。

**

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

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

http://books.google.co.in/books?id=X0Cd1Pr2W0gC&pg=PA456&lpg=PA456&dq=drawback+of+B-Tree+is+the+difficulty+of+Traversing+the+keys+sequentially&source=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 =假

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

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

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

B +树从数据中分离键。

但是,如果你的数据量less,那么你可以用B树所做的键来存储它们。

B +树的一个可能的用途是它适合于树长得如此之大以至于不需要适应可用内存的情况。 因此,你通常会期望做多个I / O。 通常情况下,即使事实上它适合内存,也会使用B +树,然后cachingpipe理器可能会永久保留它。 但是这是一个特殊的情况,而不是一般情况,caching策略与B +树维护是分开的。

而且,在B +树中,叶页在链接列表(或双向链表)中链接在一起,这优化了遍历(用于范围search,sorting等)。 所以指针的数量是所使用的具体algorithm的函数。