本文转载自微信公众号《架构改进之路》，作者的架构精炼之路。转载本文请联系建筑改良之路公众号。写在前面在上一讲中，我们介绍了B-tree的特点，并将其与平衡二叉树进行了比较，得到了B-tree等数据结构的优势。《面试官：谈谈你对索引的认知》系列B-tree，B+树是B-tree的升级版，有什么优势？本次讲座将继续为大家揭开B+树的神秘面纱，让它不再是你进步的阻碍！B+树简介B+树是B树的升级版，也是一种多路搜索树。与B-tree相比，B+树充分利用了节点的空间，使得查询速度更加稳定，其速度完全接近Binarysearch。从上面B-tree的简化图，我们可以发现几个显着的特点：数据只出现在叶子节点（非叶子节点不存储真实数据）所有叶子节点添加一个链指针B+树VSB-树1，数据结构不同，查询复杂度不同。B+树中的节点不存储数据，所有数据都存储在叶子节点中，导致查询时间复杂度固定为logn。B-tree查询时间复杂度不是固定的，和key在树中的位置有关，最好是O(1)。比如我们分别查询B-tree/B+tree中nodekey为50的数据。B-treekey为50的节点恰好在第一层，B-tree只需要一次磁盘IO就可以完成查找。所以B树查询的最佳时间复杂度是O(1)。B+树由于B+树的所有数据字段都在根节点中，查询关键字为50的节点必须从根节点索引到叶节点，时间复杂度固定为O(logn)。总结：由于B-tree的每个节点都有key和data，所以查询的时候可能不需要O(logn)的复杂度，甚至最好的情况也是O(1)找数据，而B+树只有叶子节点存储数据，因此必须经过O(logn)复杂度才能找到数据。2、B+树可以更好的利用局部性原理。B+树叶子节点成对连接，可以大大增加区间可达性，可以用于范围查询等，而B-tree每个节点的key和data在一起，不能区间搜索.空间局部性原则：如果内存中的某个位置被访问，那么它附近的位置也会被访问。如果我们访问节点密钥50，则将来也可能访问密钥为55、60和62的节点。我们可以利用磁盘预读的原理，将这些数据提前读入内存，减少磁盘IO次数。当然B+树也可以很好的完成范围查询。比如查询key值在50-70之间的节点。总结：由于B+树的叶子节点的数据是通过链表连接起来的，并且是顺序存储在磁盘上的，所以当读取到某个值时，磁盘预读的原理会提前读取所有的数据进入内存，进行范围查询和快速排序。3、B+树的每个节点可以索引的范围更大更准确，因为它的内部节点不存储数据，所以一个节点可以存储更多的key。由于B-tree节点中的每个key都有一个data字段，而B+树节点只存储了key的一个副本，所以真正的key和data字段都存储在叶子节点中。上面说了磁盘是分块的，一次磁盘IO会读取几个块，这跟操作系统有关。由于磁盘IO数据的大小是固定的，在一次IO中，单个元素越小，数量越大。这意味着B+树的单次磁盘IO的信息量要大于B树。从这一点来看，B+树的磁盘IO次数要少于B树。从上图可以看出，同样大小的区域，B树只有2个key，而B+树有3个key。总结：由于B树的所有节点都存储key和数据，而B+树只有叶子节点存储数据，所以非叶子节点只是索引值，没有实际数据。这意味着可以在一次IO中读取B+树。有更多的指标值。这样就减少了查询所需的IO数量！B-tree相对于B+tree的优势在于，如果经常访问的数据离根节点很近，而B-tree的非叶子节点本身就有key及其数据的地址，所以这种数据检索会比B+树快。但是B+树的优势更明显：B+树比B树的层数少，B+每个非叶子节点存储的关键词更多，树的层数更少，所以查询数据更快；B+树查询速度更稳定B+所有关键字数据地址都存储在叶子节点上，所以每次搜索的次数相同，所以查询速度比B-tree更稳定；B+树天生就有排序的功能。B+树的所有叶子节点数据构成一个有序链表。查询大小范围内的数据比较方便，数据紧凑度很高，缓存的命中率会比B-tree高。B+树全节点遍历更快B+树遍历整棵树只需要遍历所有叶子节点，而不是像B树那样遍历每一层，有利于数据库进行全表扫描。
