MySQL索引为什么要用B+树实现？

待我称王封你为后i 2024-03-17 11:15 80阅读 0赞

首先，得先了解什么是B树什么是B+树

### 什么是B树 ###

自平衡二叉树虽然能保持查询操作的时间复杂度在O(logn)，但是因为它本质上是一个二叉树，每个节点只能有 2 个子节点，那么当节点个数越多的时候，树的高度也会相应变高，这样就会增加磁盘的 I/O 次数，从而影响数据查询的效率。

为了解决降低树的高度的问题，后面就出来了 B 树，它不再限制一个节点就只能有 2 个子节点，而是允许 M 个子节点 (M>2)，从而降低树的高度。

B 树的每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶，所以 B 树就是一个多叉树。

假设 M = 3，那么就是一棵 3 阶的 B 树，特点就是每个节点最多有 2 个（M-1个）数据和最多有 3 个（M个）子节点，超过这些要求的话，就会分裂节点，比如下面的的动图：  
![请添加图片描述][eb719552627b4db1ade671a8d793da23.gif]  
我们来看看一棵 3 阶的 B 树的查询过程是怎样的？  
![请添加图片描述][b83ad437d66e4fe3b9c2c5fb27d5f50c.gif]

假设我们在上图一棵 3 阶的 B 树中要查找的索引值是 9 的记录那么步骤可以分为以下几步：

1.  与根节点的索引(4，8）进行比较，9 大于 8，那么往右边的子节点走；
2.  然后该子节点的索引为（10，12），因为 9 小于 10，所以会往该节点的左边子节点走；
3.  走到索引为9的节点，然后我们找到了索引值 9 的节点。

可以看到，一棵 3 阶的 B 树在查询叶子节点中的数据时，由于树的高度是 3 ，所以在查询过程中会发生 3 次磁盘 I/O 操作。

而如果同样的节点数量在平衡二叉树的场景下，树的高度就会很高，意味着磁盘 I/O 操作会更多。所以，B 树在数据查询中比平衡二叉树效率要高。

但是 B 树的每个节点都包含数据（索引+记录），而用户的记录数据的大小很有可能远远超过了索引数据，这就需要花费更多的磁盘 I/O 操作次数来读到「有用的索引数据」。

而且，在我们查询位于底层的某个节点（比如 A 记录）过程中，「非 A 记录节点」里的记录数据会从磁盘加载到内存，但是这些记录数据是没用的，我们只是想读取这些节点的索引数据来做比较查询，而「非 A 记录节点」里的记录数据对我们是没用的，这样不仅增多磁盘 I/O 操作次数，也占用内存资源。

另外，如果使用 B 树来做范围查询的话，需要使用中序遍历，这会涉及多个节点的磁盘 I/O 问题，从而导致整体速度下降。

### 什么是 B+ 树？ ###

B+ 树就是对 B 树做了一个升级，MySQL 中索引的数据结构就是采用了 B+ 树，B+ 树结构如下图：  
![在这里插入图片描述][be31396bb1464ba1ad457a834765620f.png]  
B+ 树与 B 树差异的点，主要是以下这几点：

叶子节点（最底部的节点）才会存放实际数据（索引+记录），非叶子节点只会存放索引；

所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表；

非叶子节点的索引也会同时存在在子节点中，并且是在子节点中所有索引的最大（或最小）。

非叶子节点中有多少个子节点，就有多少个索引；

下面通过三个方面，比较下 B+ 和 B 树的性能区别。

#### 1、单点查询 ####

B 树进行单个索引查询时，最快可以在 O(1) 的时间代价内就查到，而从平均时间代价来看，会比 B+ 树稍快一些。

但是 B 树的查询波动会比较大，因为每个节点即存索引又存记录，所以有时候访问到了非叶子节点就可以找到索引，而有时需要访问到叶子节点才能找到索引。

B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比存储即存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O次数会更少。

#### 2、插入和删除效率 ####

B+ 树有大量的冗余节点，这样使得删除一个节点的时候，可以直接从叶子节点中删除，甚至可以不动非叶子节点，这样删除非常快，

> 注意：B+ 树对于非叶子节点的子节点和索引的个数，定义方式可能会有不同，有的是说非叶子节点的子节点的个数为 M 阶，而索引的个数为  
> M-1（这个是维基百科里的定义），因此我本文关于 B+ 树的动图都是基于这个。但是我在前面介绍 B+ 树与 B+  
> 树的差异时，说的是「非叶子节点中有多少个子节点，就有多少个索引」，主要是 MySQL 用到的 B+ 树就是这个特性。

甚至，B+ 树在删除根节点的时候，由于存在冗余的节点，所以不会发生复杂的树的变形。  
B 树则不同，B 树没有冗余节点，删除节点的时候非常复杂，比如删除根节点中的数据，可能涉及复杂的树的变形。

B+ 树的插入也是一样，有冗余节点，插入可能存在节点的分裂（如果节点饱和），但是最多只涉及树的一条路径。而且 B+ 树会自动平衡，不需要像更多复杂的算法，类似红黑树的旋转操作等。

因此，**B+ 树的插入和删除效率更高。**

#### 3、范围查询 ####

B 树和 B+ 树等值查询原理基本一致，先从根节点查找，然后对比目标数据的范围，最后递归的进入子节点查找。

因为 B+ 树所有叶子节点间还有一个链表进行连接，这种设计对范围查找非常有帮助，比如说我们想知道 12 月 1 日和 12 月 12 日之间的订单，这个时候可以先查找到 12 月 1 日所在的叶子节点，然后利用链表向右遍历，直到找到 12 月12 日的节点，这样就不需要从根节点查询了，进一步节省查询需要的时间。

而 B 树没有将所有叶子节点用链表串联起来的结构，因此只能通过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。

因此，存在大量范围检索的场景，适合使用 B+树，比如数据库。而对于大量的单个索引查询的场景，可以考虑 B 树，比如 nosql 的MongoDB。

MySQL 的存储方式根据存储引擎的不同而不同，我们最常用的就是 Innodb 存储引擎，它就是采用了 B+ 树作为了索引的数据结构。

MySQL 中的 B+ 树  
![在这里插入图片描述][2d0ae64cdfce4307b43fa643273a46a8.png]

但是 Innodb 使用的 B+ 树有一些特别的点，比如：

B+ 树的叶子节点之间是用「双向链表」进行连接，这样的好处是既能向右遍历，也能向左遍历。

B+ 树点节点内容是数据页，数据页里存放了用户的记录以及各种信息，每个数据页默认大小是 16 KB。

Innodb 根据索引类型不同，分为聚集和二级索引。他们区别在于，聚集索引的叶子节点存放的是实际数据，所有完整的用户记录都存放在聚集索引的叶子节点，而二级索引的叶子节点存放的是主键值，而不是实际数据。

因为表的数据都是存放在聚集索引的叶子节点里，所以 InnoDB 存储引擎一定会为表创建一个聚集索引，且由于数据在物理上只会保存一份，所以聚簇索引只能有一个，而二级索引可以创建多个。

了解完B树和B+树再去思考MySQL索引为什么要用B+树实现更加透彻

### 为什么需要索引？ ###

在数据库中，索引是一种特殊的数据结构，用于加速数据的检索。通过索引，数据库可以快速地定位记录，从而提高查询效率。如果没有索引，数据库中的每条记录都需要逐条扫描，查询效率将大大降低。

### 总结：为什么选择B+树作为索引结构？ ###

在选择索引结构时，需要考虑以下因素：

*  支持哪些查询操作
 *  数据量大小
 *  数据的插入、更新、删除操作频率

B+树正好满足这些要求，具有以下特点：

*  B+树的叶子节点包含了所有的关键字和指向数据的指针，因此B+树支持非常高效的范围查询操作，例如“查找所有年龄在20~30岁之间的人”。
 *  B+树非常适合存储大量数据，每个节点可以存储多个关键字和指针，可以大大减少磁盘I/O的次数。
 *  B+树的插入和删除操作相对于其他数据结构来说，效率非常高。每次插入和删除只需要操作B+树的叶子节点，因此不需要涉及到非叶子节点的复杂调整操作。

因此，MySQL选择使用B+树作为索引结构来达到高效的检索，尤其是对于大数据量的查询和更新操作时。

看到这，相信大家不仅对索引有了理解，也对B+树的实现更加清晰  
下面是根据chatgpt生成的图**the thinking monkey**  
![在这里插入图片描述][9f45ff5fd97b49d08e3e5bf4edde250f.png]

[eb719552627b4db1ade671a8d793da23.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/9750bc3ceeda43b2a7dafc377e6ff1e4.png
[b83ad437d66e4fe3b9c2c5fb27d5f50c.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/5bc7e58a3a7341a28d1736305337b87c.png
[be31396bb1464ba1ad457a834765620f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/437e00a56ead4950a5cdf06b50318d4e.png
[2d0ae64cdfce4307b43fa643273a46a8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/98e1dcc9624b42a1b9a19a1ecea4470b.png
[9f45ff5fd97b49d08e3e5bf4edde250f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/ee8bffa7daf6456592af2d84e7ac6ee1.png