图解B+树的插入过程

SQL herman 254浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog,发送下载链接帮助你免费下载!
本博客日IP超过1800,PV 2600 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog,之前的微信号好友位已满,备注:返现
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

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。

B+ 树根结点

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

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

B+ 树索引类型节点

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

3、再插入关键字 16。

B+ 树满足分裂条件

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

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

B+ 树分裂图

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

B+ 树关键字节点

注意,节点都是有序的。

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

B+ 数据节点数据满足分裂条件

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

B+ 树节点分裂效果图

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

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

B+ 树的根节点满足分裂条件

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

B+ 树根节点分裂后效果图

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

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

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加QQ1群:135430763(2000人群已满),QQ2群:454796847(已满),QQ3群:187424846(已满)。QQ群进群密码:xttblog,想加微信群的朋友,之前的微信号好友已满,请加博主新的微信号:xttblog,备注:“xttblog”,添加博主微信拉你进群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作可添加助理微信进行沟通!

本文原文出处:业余草: » 图解B+树的插入过程