【数据库专题】一文搞懂 B+树凭什么成为关系型数据库索引的主流数据结构

不念不忘少年蓝@ 2024-05-06 09:43 1阅读 0赞

#### 文章目录 ####

*  一、非B+树不可吗？
 *  二、二叉树演变B+树过程
 *  三、B+树总结
 *  四、和B树的关系

> 🍍每日推荐
> 
> 🍖文章开始之前我想首先介绍一下[牛客][Link 1]，以便没有使用过的小伙伴能够快速入手，[牛客网][Link 1]是国内最大的算法、面试、招聘网站，涵盖了多种大厂面试真题以及题解，里面大佬云集，各种题目的解决方案层出不穷，绝对能让你大开眼界，而且[牛客][Link 1]是你在人生中不同的阶段都能对你有所帮助的编程软件（完全免费），如果感兴趣可以访问注册一下
> 
> 访问链接：[牛客-国内最大的刷题网站][Link 1]

## 一、非B+树不可吗？ ##

数据库最常用的两个功能就是“等值查询”和“范围查询”。如果只是为了满足“等值查询”，那么Hash散列表和平衡二叉查找树都能胜任数据库索引这个使用场景，但是“范围查询”却加大了难度，使得它们不太适合了。

在原先讲过的“跳表”倒是很契合，但实际场景中，大家都是使用的B+树。

## 二、二叉树演变B+树过程 ##

二叉树我们前面也都了解过了，我们来看下，用它来作为索引的数据结构会存在什么问题？首先它是能够满足“等值查询”的，但是无法进行“范围查询”，所以，我们需要对其进行改造：

*  树中的每个节点都不存储具体的数据，而是存储索引；
 *  叶子节点从左到右用双向链表绑定起来；

改造前后的二叉树结构示意图如下：

![二叉树改造前后示意图][14b19adae4d34ccdaa8fee54e456e22e.webp_pic_center]

改造后的好处是：

*  只是存储索引的话，使得二叉树的大小不会很大；
 *  叶子节点使用双向链表串起来之后，就可以进行范围查找了；
 *  等值查找的时间复杂度还是树高O(logn)；

看上去还不错，但是实际使用时有问题，因为我们数据库中需要存储的数据实在是非常多，如果使用这样的改造后的二叉树，树的高度将是非常惊人的。不但查找起来非常缓慢，而且这么多节点全部加载到内存中也是不现实的。

我们再次进行如下的改造：

*  只把所有索引树的根节点放入到内存中，其它子节点都放到磁盘上；
 *  将二叉树改造为m叉树，每个节点的子节点个数最多为m个，如此树的高度就大大降低了，减少了IO磁盘查找的次数；
 *  每个子节点的大小不能超过一页的大小，通常为4kb，保证m最大的同时，OS单次读页就能将该节点加载完毕；

改造后的数据结构示意图如下：

![B+树改造示意图][B]

改造后的好处是：

*  没有把索引树的全部节点加载到内存，减少了内存的压力；
 *  m叉树使得索引树的高度尽可能降低了，减少了IO查找节点的次数，提高了时间效率；
 *  m取值有了理论依据，使得时间效率最大化；
 *

但同时也有部分缺点：

*  数据的写入和删除都会导致索引的更新，从而需要更改索引树；
 *  当插入数据的时候，如果某个节点的子节点个数超过m，就需要分裂，极端情况下，需要从下往上传导分裂；
 *  当删除数据的时候，如果某个节点的个数小于m/2，则需要合并节点，否则这样的节点多了，影响查询效率；

## 三、B+树总结 ##

*  每个节点中的子节点个数不能超过m，不能小于m/2；
 *  根节点的子节点个数可以小于m/2，但是不能超过m；
 *  每个节点只存储索引，并不存储数据；
 *  所有叶子节点都是双链表串联的，方便范围查找；
 *  根节点会被存储在内存中，其它节点存储在磁盘中；

## 四、和B树的关系 ##

B+树是在B树的基础上改进的，B树中每个节点是存储真实的数据的，所以整个树会很大；B树的叶子节点是没有用链表串联的，所以还是无法满足范围查找的场景；因此，B树其实就是一个子节点不能小于m/2的m叉树；

B+树和B树的关系，以及MySQL中不同存储引擎数据结构的不同可以参考[《【数据库专题】如何理解数据库的索引？》][Link 2]

> 🍍 每日推荐
> 
> 🍖文章开始之前我想首先介绍一下[牛客][Link 1]，以便没有使用过的小伙伴能够快速入手，[牛客网][Link 1]是国内最大的算法、面试、招聘网站，涵盖了多种大厂面试真题以及题解，里面大佬云集，各种题目的解决方案层出不穷，绝对能让你大开眼界，而且[牛客][Link 1]是你在人生中不同的阶段都能对你有所帮助的编程软件（完全免费），如果感兴趣可以访问注册一下
> 
> 访问链接：[牛客-国内最大的刷题网站][Link 1]

[Link 1]: https://www.nowcoder.com/exam/oj?page=1&tab=SQL%E7%AF%87&topicId=199&fromPut=pc_csdncpt_ddssyx_sql
[14b19adae4d34ccdaa8fee54e456e22e.webp_pic_center]: https://img-blog.csdnimg.cn/14b19adae4d34ccdaa8fee54e456e22e.webp#pic_center
[B]: https://img-blog.csdnimg.cn/f2b6f656d0484984b4d38d873778f678.webp#pic_center
[Link 2]: https://blog.csdn.net/weixin_42469135/article/details/125139540?csdn_share_tail=%7B%22type%22:%22blog%22,%22rType%22:%22article%22,%22rId%22:%22125139540%22,%22source%22:%22weixin_42469135%22%7D&ctrtid=rLfXN