图解B+树的插入过程

B+ 树在现代数据库中很常见，如果我们了解它，在工作中可能对性能优化会有更好的帮助！

最近我一直在思考 B+ 树的高度是由什么决定的。知道我了解了 B+ 树的插入过程，才有一种恍然大悟的感觉！

网上的一些资料杂乱无章，不同的数据库可能还有对 B+ 树有不同的实现。但是万变不离其宗，B+ 树的定义，大致如下所示：

总结一下，B+ 树有下面 5 个重要的特点。

• B+ 树包含 2 种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有 1 个。
• B+ 树与 B 树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。
• m 阶 B+ 树表示了内部结点最多有 m-1 个关键字（或者说内部结点最多有 m 个子树），阶数 m 同时限制了叶子结点最多存储 m-1 个记录。
• 内部结点中的 key 都按照从小到大的顺序排列，对于内部结点中的一个 key，左树中的所有 key 都小于它，右子树中的 key 都大于等于它。叶子结点中的记录也按照 key 的大小排列。
• 每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。

根据上面的特点，我们来看看 B+ 树的插入过程。

下面以一棵 5 阶 B+ 树的插入过程，5 阶 B+ 树的节点最少 2 个 key，最多 4 个 key。

1、当树为空树，插入 5。

只有一个关键字，叫根节点或叶子节点都是一样的。

2、再次插入 3 个索引关键字，8，10，15。

当前节点 key 存满了，如果再插入当前节点就要进行分裂。

3、再插入关键字 16。

可以看到，这个 B+ 树，现在满足分裂条件了。所以要进行节点分裂。

插入 16 后超过了关键字的个数限制，所以要进行分裂。在叶子结点分裂时，假设分裂出来的左结点有 2 个记录，右节点有 3 个记录，中间 key 成为索引结点中的 key，会成为一个父节点，分裂后的两个节点都指向了父结点（根结点）。

4、假设我们再插入 17 这个关键字。

注意，节点都是有序的。

5、然后，我们再插入一个 18。

此时，我们发现右边的节点，满足了分裂条件，所有我们要进行分裂。

分裂前后，节点上的关键字保持有序性。

就这样，当我们再插入 10 个数据后，假设结构如下所示：

此时，根节点的关键字个数超过 4，需要进行分裂。分裂后，左结点 2 个关键字，右结点 2 个关键字，关键字 16 进入到父结点中，将分裂后的节点指向父结点，结果如下图所示。

以此类推，当插入的数据满足节点分裂时就会进行分裂。但是分裂后，关键字都是有序的。

根据这个插入过程，一个 B+ 树的高度，是有一个节点能存储多少关键字，也就是索引决定的。通常，一棵 MySQL 的 B+ 树，树高为 3 的话，大约能存上亿条。树的高度太高的话，查询效率会大打折扣！

： » 图解B+树的插入过程