本博客日IP超过2000，PV 3000 左右，急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包，请加博主新的微信号：xttblog2，之前的微信号好友位已满，备注：返现
受密码保护的文章请关注“业余草”公众号，回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽，请关注文末小程序
腾讯云】1核2G5M轻量应用服务器50元首年，高性价比，助您轻松上云
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 的话，大约能存上亿条。树的高度太高的话，查询效率会大打折扣！
最后，欢迎关注我的个人微信公众号：业余草（yyucao）！可加作者微信号：xttblog2。备注：“1”，添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注！后续有精彩内容会第一时间发给您！原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系！
本文原文出处：业余草： » 图解B+树的插入过程