深入理解什么是B+树

前言

上一篇已经详细的介绍了什么是B树，但B树这种结构仍有不足之处，比如对范围检索就比较费劲，所以科学大佬们就继续改造扩展，在B树的基础上发明了B+树，上篇文章中也简单提到过B+树，本篇我们就来详细的学习一下。

B+树的结构定义

首先B+树是B树的一种扩展，在B+树里面，非叶子节点不再存储数据，仅仅存在索引，而叶子这点存储具体的数据，并且最底层的数据直接之间从做到右是按照从小到大的顺序分布，并且是一个双链表的结构。也就是说的所有的关键码均出现在叶节点上，各层节点中的关键码均是下一层相应节点中的最大或者最小的关键码的复写。

m阶B+树的结构定义如下：

（1）每个节点最多有m个子节点

（2）除根节点外，每个节点至少有m/2个子节点，注意如果结果除不尽，就向上取整，比如5/2=3。

（3）根节点要么是空，要么是独根，否则至少有2个子节点

（4）有k个子节点的节点必有k个关键码

（5）叶节点的高度一致

我们看下面的图对比下B树和B+树：

B树的结构：

B+树的结构：

注意B+树的几个特点，父节点的关键码有几个，下面就有多少个子节点，并且父节点里面的关键码在子节点或者是子树里面的值总是最大或者最小，这些特点与B树不同，不要搞混淆，B树里面含k个关键码的父节点，有k+1的子节点，B树里面的关键码起到分割界限的作用，每个关键码并不都是子树里面最大的值，这一点要特别注意，网上很多关于B+树的图示，其实都是B树的图片，但实际上他们两者是不一样的。

下图是一个2阶B+树的例子：

注意从底部，向上每一层其实都是一个有序的序列，单纯从这种形式上来看，B+树的结构与跳跃表是非常相似的，不同的是B+树是采用树的方式来组织索引，而跳跃表则是采用多层索引的方式。跳跃表支持的功能和B+树一样丰富，跳跃表毕竟是面向内存的数据结构，并不适合给数据量较大的数据库做索引，这也是B+树为什么出现的原因，但实际上跳跃表（1989年）比B+树（1972年）出现的要晚，推测在一定程度上借鉴了B+树的思想。

B+树的操作

查询

B+树的查询与B树大致上一样，但不同的是在B+树里面查找必须找到叶节点层才行，因为B+树里面最底层的叶节点才是全集，而在B树里面非叶子节点也可以存储数据，所以直接查询遇到查找的值就返回。

B+树的两种查询方式：

（1）从root出发一直查询到叶节点。

（2）从叶节点的最左侧出发，进行顺序查找，这个比较适合迭代输出全量数据的时候使用。

插入

过程和B树类似，如果关键码没有超过上界即可，如果超过了就需要分裂，另外如果新插入的关键码是最大的，这种情况下实在最右边是新插入的值的时候，那么需要保证父节点的复写关键码也要更新到最大或者最小的。

插入的情况如下：

（1）对于一个3阶的B树，插入15，插入前如下：

插入后如下，因为没有溢出，这种情况就比较简单,所以直接添加即可：

（2）继续插入16

这个时候要注意，3阶B+树，节点和关键码的个数都是2到3，此时继续插入16就会导致溢出，所以就需要分裂，分裂后的结果如下：

注意关键码的复写，要上升到父节点里面。

（3）继续插入17，因为没有溢出直接插入即可，

（4）继续插入19，就会发生溢出：

如下图，关键码个数变成了4发生溢出，这个时候就需要分裂：

分裂完后的图如下，但此时我们就会发现，分裂导致根节点的关键码也溢出了：

怎么办呢？如果父节点也发生溢出，那么还需要继续分裂，如果是在根节点这一层，最终分裂的结果会导致树升高一级，最终分裂后的结果如下：

删除

（1）如下图m=3的时候，删除23：

删除，首先需要找到这个值，这个跟查询流程一样，要一直找到叶子节点，如果不出现溢出，直接删除即可， 这里面需要注意，如果删除的是叶子节点，那么父节点的复写副本，其实是不一定需要删除的，只要它能正确的分界，便可以不需要删除，结果如下：

（2）极限情况下删除，m=2时，删除20，如下图：

首先m=2时，阶和关键码的个数范围是1-2，在上图中如果删除20，那么就会导致叶节点的高度不一致，所以需要合并均衡，合并后的结果如下：

但上图仍然是不均衡的，因为叶节点的高度不一致，那么应该怎么办呢， 其实比较容易，如下，

这种是允许的，因为没有违背B+树的性质，只是看上去有点特殊。

B+树的优点

（1）B+树相比B树的存储效率更高。B+树其实是多级索引，这个前面也提到过这种结构与跳跃表是非常的相似，最下一层是所有关键码的全集，因此可以把此层形成顺序的双链链表，正因为在B+树里面非叶层节点不需要存储额外的指向磁盘的指针，所以相比B树，B+树存储效率更高。

假设一个主文件有N个记录，假设一个页块页可以存储m个二元对（关键码，子节点的页块地址），假设B+树平均每个节点的充盈度为0.75，因为最少是0.5，最大是1，所以取中间是0.75，那么B+树的高度为log0.75mN，而同样情况下B树的充盈度为0.5，即B树的高度约为log0.5mN

（2）通过（1）的优点，我们还可以发现B+树的高度更小，也就是说B+树的检索效率更高

（3）B+树支持范围检索，在实际应用中更为广泛。

（4）插入和删除更为方便，其实流程和B树类似，但B+树里面，关键码的个数和子节点的个数是对等的，所以从记忆角度来说，B+树更方便记忆使用，而B树则需要时刻注意节点数和关键码的对应关系。

关于B+树节点个数的思考

前面说过B+树是多路查找树，子节点的个数可以是2到无限个，那么问题来了，是不是B+树的子节点个数越多越好呢？

其实不然，如果是极端情况子节点个数就等于总个数，那么B+树退化成了线性表数组，检索效率大大下降，这种情况肯定是不行的，其实思考这个问题也很容易，我们想一下B树出现的初衷是为了解决磁盘系统的高效率的检索，树的高度自然是越低越好，但也不意味着子节点的个数应该尽可能的多，B树的设计要充分考虑磁盘的读写和缓冲机制，前面的文章说过，磁盘块和页内存一般都是4kb，而磁盘有预读机制，每次读的时候都是加载一个磁盘页到内存里面，所以我们的节点数的总大小应该是尽可能的贴近磁盘页的大小，这样以来可以达到最好的读写效率也充分的利用了磁盘cache的预读机制。

总结

本文主要深入的介绍了B+树的相关内容，B+树是B树的扩展，此外还有B树，这里提下B树，其充盈程度是0.75到1之间，在实际应用中并不常见，所以不再细说。B+树的设计思路与B树大致类似，因为支持范围查找及存储效率更高，所以在实际工程中应用更为广泛。关于B树，B+树或者时充盈度更高的B*树，其保持均衡的关键主要有两点，第一是阶和关键码的对应关系与限制，第二是所有的叶节点高度一致，而处理均衡的策略包含了分裂，合并，交换等手段，理解了这些知识，再去思考或者学习B树（泛指）相关的内容就会容易很多。