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

写在前面

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

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

那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+树

由于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树一样需要对每一层进行遍历，这有利于数据库做全表扫描。