不知道你有没有这样的困惑，B+树的资料看了很多，依旧对B+树没有一个具象的认识。我也是这么走过来的，所以希望这篇笔记能帮到你。

一、演化阶段
你或许知道，或许不知道。B＋树是由二叉树不断演化过来的。
大致的演化路线如下：
二叉查找树 -> 平衡二叉树 -> B树 -> B+树。

为了说清楚B+说，我们很有必要搞清楚演化过程中每个阶段的特点。

0、二叉查找树
一棵空树，或满足以下特点的二叉树
0.0、若任意节点的左子树不空，则左子树上所有节点的值均小于它根节点的值；
0.1、若任意节点的右子树不空，则右子树上所有节点的值均大于它根节点的值；
0.2、任意节点的左、右子树也分别为二叉查找树；
0.3、没有键值相等的节点。

把如下序列[2, 3, 5, 6, 7, 8]构造为一棵二叉查找树，如下图

注：二叉查找树也称为二叉搜索树

我们很容易发现，这颗二叉查找树的查找效率跟顺序查找差不多。主要原因是树的高度比较高，左右子树不平衡。我们需要这颗二叉查找树是平衡的，于是就演化出了平衡二叉查找树。

1、平衡二叉树
平衡二叉查找树简称平衡二叉树，即AVL树，平衡二叉树的特点：
1.0、是一棵二叉查找树。
1.1、必须满足任何节点的两个子树的高度最大差为1。

同样的序列[2, 3, 5, 6, 7, 8]构造为一棵平衡二叉树，如下图

平衡二叉树的查询效率很高，但是插入和更新节点后需要通过左旋和右旋来维护树的平衡有一定的开销。一般用于内存结构对象中，所以维护的开销相对较小。

如果数据量巨大，无法维护在内存中。我们往往需要把数据保存在磁盘上。由于平衡二叉树的高度比较高，就需要进行多次磁盘I/O。这显然是非常低效的。我们需要降低树的高度，多叉树是一个很好的演化方向，于是就演化出了B树。

2、B树
一棵m阶的B树有以下特性:
2.0、每一个节点最多有 m 个子节点
2.1、每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点
2.2、如果根节点不是叶子节点，那么它至少有两个子节点
2.3、有 k 个子节点的非叶子节点拥有 k − 1 个键
2.4、所有的叶子节点都在同一层

注意：所有的数据都存储在树叶节点上

B树内部节点可以拥有可变数量的子节点（数量范围预先定义好）。当数据被插入或从一个节点中移除，它的子节点数量发生变化。为了维持在预先设定的数量范围内，内部节点可能会被合并或者分离。因为子节点数量有一定的允许范围，所以B树不需要像其他自平衡查找树那样频繁地重新保持平衡，但是由于节点没有被完全填充，可能浪费了一些空间。

一棵3阶的B树示意图如下：

B树降低了树的高度，但是无法进行区间查找，于是演化出了B+树。

3、B+树
B+树由在B树的基础上，增加叶节点上的双向指针，可以进行顺序查找。同时内部节点只存放关键字和孩子指针，因此最大化了内部节点的分支因子(也就是树的阶树更多，高度更低)。

一棵4阶的B+树示意图如下：

二、特点
B树、B+树是为磁盘或其他直接存取辅助设备设计的一种多路平衡查找树。对存储在磁盘上一棵大的B+树，阶数通常在50 – 2000之间，具体取决于一个关键字相对于一个磁盘页的大小。

一棵阶数为1001，高度为2的B+树，叶节点可以存储10亿多个关键字。如下图：

层数 节点数 关键字数

第一层 1 1000

第二层 1001 1001 * 1000 = 100100

第三层 1002001 = 1001 * 1001 1002001000 = 1002001 * 1000

三、应用
B+树主要应用常见，作为MySQL索引存储数据结构。我们需要注意单纯的B+树和B+树作为索引数据结构的时候，有差异。具体差异参见下篇文章。
《B+树在MySQL索引存储中的应用》

四、时间复杂度
B+树查找时间复杂度: m表示低数，n表示总数。以m为低n的对数。
O(log m n)

参考：
维基百科:二
叉查找树
《MySQL技术内幕InnoDB存储引擎》
维基百科:B树
维基百科: B+树《数据结构与算法分析–C语言描述》
《算法导论》
lvanzz博客:B+树详解