全程图解——轻松搞定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.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
图例
看这些纯文字的特性实在是费脑子，按照本人一贯的风格，我们用生动的具体的例子来看看吧。
B+树
我们可以看到每一个父节点的元素都出现在子节点中，而且是子节点中的最大或者最小的元素。
看到没，根节点的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，范围查询高效。
好了，这期的文章就到这里了。感谢支持，下期再见！