全程图解——轻松搞定B+树?
前戏
上篇文章我们生动的讲解了B-树,本期文章我们聊下B+树,其实是B-树的一种变体吧。它的查询效率更加的高。我们现在都已经知道了一个m阶的B-树一下几个特征:
1.根结点至少有两个子女。
2.每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m
3.每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m
4.所有的叶子结点都位于同一层。
5.每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
B+树的特性跟B-看起来比较像,但是他们还是不同的特性的,一个m阶的B+树特性如下:
1.有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。
图例
看这些纯文字的特性实在是费脑子,按照本人一贯的风格,我们用生动的具体的例子来看看吧。
我们可以看到每一个父节点的元素都出现在子节点中,而且是子节点中的最大或者最小的元素。
看到没,根节点的8是子节点的最大元素,也是叶子的最大元素。以此类推,15也是最大元素。需要注的是根节点的最大元素,其实是整个树的最大元素。无论树怎么发生变化,始终要保持最大元素在根节点中。因为父节点都出现在子节点中,所以叶子节点包含了所有的元素,对不对?哈哈哈。
每个叶子中都有一个指针是指向下一个叶子节点的。这样是不是就形成了一个链表了。看下图:
这个链表是来干嘛的呢?这个我们下面会讲到。
B+树还有一个特点【卫星数据】的位置不同。所谓的【卫星数据】就是索引元素指向的真正的数据。在B-树中,无论中无论中间节点还是叶子节点都是存有【卫星数据】的。看下图:
但是在B+树中,只有叶子节点是带【卫星数据】的,中间节点只是索引而已。看下图:
看到这里,有些童鞋可能会问了,为什么要设计呢?为什么在中间节点存放【卫星数据】呢?这样做有什么好处呢?
B+树设计成这样,主要是体现在查询性能上,下面我就来分析下。
在单元素查询时候,B+树会从上到下的查询,比如我们要找3元素。
第一次查找:
第二次查找:
第三查找:
可能有些童鞋又会问了,这跟B-树也差不多啊,他们有什么区别呢?
他们还是有两点不同
- 1,B+树中间节点没有卫星数据,所以可以存放更多的元素节点。这意味着什么,它会变得更加的矮胖,矮胖意味着什么?阶数更低,查询更快。
- 2,B+数的查找一定会找到叶子节点,而B-是不需要的。也可能在中间节点就找到了。这样意味着什么?B-树查询不稳定。可能在根节点找到,可能要找到叶子节点。而B+树就很稳定,矮胖的叶子节点。
好了,我们来看下范围查询他们的不同。
B-树如果范围查找就会依靠中序遍历,我们看下面的例子查找3到11元素:
自顶向下,查找到范围的下限(3):
中序遍历到元素6:
中序遍历到元素8:
中序遍历到元素9:
中序遍历到元素11,遍历结束:
实在是繁琐至极。
我们来看下B+树的范围查找过程
自顶向下,查找到范围的下限(3):
通过链表指针,遍历到元素6, 8:
通过链表指针,遍历到元素9, 11,遍历结束:
有没有看到,是不是简单了很多。
总结
B+树相对于B-树的优势:
- 1,遍历次数更少。
- 2,查询稳定,之前有提到过哦
- 3,范围查询高效。
好了,这期的文章就到这里了。感谢支持,下期再见!