《面试官：谈谈你对索引的认知》系列之 B+ 树

写在前面

前面一讲我们介绍了 B-树的特性，以及与平衡二叉树的对比得出 B-树这类数据结构的优势。

https://xie.infoq.cn/article/d0485a1327e300611281f2194

那 B+树作为 B 树的一个升级版，那它又有哪些优势呢？本讲继续为大家揭开 B+树的神秘面纱，让它不再成为你前进的羁绊！

B+树 简介

B+树是 B-树的一个升级版，也是一种多路搜索树，相对于 B 树来说 B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。

从上图 B-树的简化图，我们可以发现几个显著特点：

• 据只出现在叶子节点（非叶子节点并不存储真正的 data）

• 所有叶子节点增加了一个链指针

B+树 VS B-树

1、数据实现结构不同，查询复杂度不同

B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而 B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为 O(1)。

如我们分别查询 B-树/B+树节点 key 为 50 的 data。

• B-树

key 为 50 的节点恰好就在第一层，B-树只需要一次磁盘 IO 即可完成查找。所以说 B-树的查询最好时间复杂度是 O(1)。

• +树

由于 B+树所有的 data 域都在根节点，所以查询 key 为 50 的节点必须从根节点索引到叶节点，时间复杂度固定为 O(log n)。

小结：

B 树的由于每个节点都有 key 和 data，所以查询的时候可能不需要 O(logn)的复杂度，甚至最好的情况是 O(1)就可以找到数据，而 B+树由于只有叶子节点保存了 data，所以必须经历 O(logn)复杂度才能找到数据。

2、B+树可以更好的利用局部性原理

B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而 B-树每个节点 key 和 data 在一起，则无法区间查找。

空间局部性原理：如果一个存储器的某个位置被访问，那么将它附近的位置也会被访问。

若我们访问节点 key 为 50，则 key 为 55、60、62 的节点将来也可能被访问，我们可以利用磁盘预读原理提前将这些数据读入内存，减少了磁盘 IO 的次数。当然 B+树也能够很好的完成范围查询。比如查询 key 值在 50-70 之间的节点。

小结：

由于 B+树的叶子节点的数据都是使用链表连接起来的，而且他们在磁盘里是顺序存储的，所以当读到某个值的时候，磁盘预读原理就会提前把这些数据都读进内存，使得范围查询和排序都很快。

3、B+树每个节点能索引的范围更大更精确

因为它内节点不存储 data，这样一个节点就可以存储更多的 key。

由于 B-树节点内部每个 key 都带着 data 域，而 B+树节点只存储 key 的副本，真实的 key 和 data 域都在叶子节点存储。前面说过磁盘是分 block 的，一次磁盘 IO 会读取若干个 block，具体和操作系统有关，那么由于磁盘 IO 数据大小是固定的，在一次 IO 中，单个元素越小，量就越大。这就意味着 B+树单次磁盘 IO 的信息量大于 B-树，从这点来看 B+树相对 B-树磁盘 IO 次数少。

从上图可以看出相同大小的区域，B-树仅有 2 个 key，而 B+树有 3 个 key。

小结：

由于 B 树的节点都存了 key 和 data，而 B+树只有叶子节点存 data，非叶子节点都只是索引值，没有实际的数据，这就时 B+树在一次 IO 里面，能读出的索引值更多。从而减少查询时候需要的 IO 次数！

总结

B-树相对于 B+树的优点是，如果经常访问的数据离根节点很近，而 B 树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比 B+树快。

但是 B+树的优势更加明显：

• B+树的层级更少

相较于 B 树 B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；

• B+树查询速度更稳定

B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比 B 树更稳定;

• B+树天然具备排序功能

B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比 B 树高。

• B+树全节点遍历更快

B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像 B 树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

作者：架构精进之路，十年研发风雨路，大厂架构师，CSDN 博客专家，专注架构技术沉淀学习及分享，职业与认知升级，坚持分享接地气儿的干货文章，期待与你一起成长

关注并私信我回复“01”，送你一份程序员成长进阶大礼包，欢迎勾搭。

🎉 文章首发于个人公众号「架构精进之路」，原文链接：《面试官：谈谈你对索引的认知》系列之B+树

Thanks for reading!