深入理解 MySQL 索引底层数据结构

喜欢ヅ旅行 2024-03-24 16:09 50阅读 0赞

## 1 引言 ##

在日常工作中，我们会遇见一些慢 SQL，在分析这些慢 SQL 时，我们通常会看下 SQL 的执行计划，验证 SQL 执行过程中有没有走索引。通常我们会调整一些查询条件，增加必要的索引，SQL 执行效率就会提升几个数量级。我们有没有思考过，为什么加了索引就会能提高 SQL 的查询效率，为什么有时候加了索引 SQL 执行反而会没有变化，本文就从 MySQL 索引的底层数据结构和算法来进行详细分析。

## 2 索引数据结构对比 ##

索引的定义：索引 (Index) 是帮助 MySQL 高效获取数据的排好序的数据结构。

索引中常见的数据结构有以下几种：

*  Hash 表
 *  二叉树
 *  红黑树
 *  B-Tree
 *  B+Tree

**Hash 表**  
通过索引的 key 进行一次 hash 计算，就可以快速获取磁盘文件指针，对于指定索引查找文件非常快，但是对于范围查找没法支持，有时候也会出现 Hash 冲突的情况。

![cb4aa4d7259666cca3ee7d68a3b1d4aa.png][]

**二叉树**  
二叉树的特点：左边子节点的数据小于父节点数据，右边子节点的数据大于父节点数据。如下图所示，如果 col2 是索引，查找索引为 65 的行元素，只需要查找两次，就可以获取到行元素所在的磁盘指针地址。

![2b3e669a91009418f17de2dd0c0e6751.png][]

但如果是一个按照顺序递增的值，例如为 col1 建立索引，不再适合使用二叉树建立索引，因为此时使用二叉树建立索引将会变成一个链式索引，此时的索引结构如下图所示，如果查找 6 节点需要 6 次遍历才能找到。

![4deab7fd6b34cb43b2095af93daaacff.png][]

**红黑树**  
红黑树是一种二叉平衡树，可以提高查询效率，此时若再查找 6 节点只需要遍历 3 次就能找到了。但红黑树也有缺点，当存储大数据量时，树的高度就会变的不可控， 数量越大，树的高度越高，查询的效率将会大大降低。

![75ef63c5e2b64dba005adba7160ab89c.png][]

**B-Tree**  
B-Tree 是一种多路二叉树，所具有的特点：1 叶节点具有相同的深度，叶节点的指针为空；2 所有索引元素不重复；3 节点中的数据索引从左到右递增排列。

![9b19b7e775e082d9012af56b7505a21e.png][]

**B+Tree**  
B+Tree 是 B-Tree 的变种，所具有的特点：1 非叶子节点不存储 data，只存储索引 (冗余)，可以放更多的索引；2 叶子节点包含所有索引字段；3 叶子节点用指针连接，提高区间访问的性能。

![be41c6b8c4c66bb4f06df8d7a7120d24.png][]

与红黑树相比，B-Tree 和 B+Tree 两种数据结构都更加矮胖，存储相同数量级的索引数据时，层级更低。

B-Tree 和 B+Tree 之间一个很大的不同，是 B+Tree 的节点上不储存 value，只储存 key，而叶子节点上储存了所有 key-value 集合，并且节点之间都是有序的。这样的好处是每一次磁盘 IO 能够读取的节点更多，也就是树的度 (Max.Degree) 可以设置的更大一些，因为每次磁盘 IO 读取的磁盘页数是一定的。例如，每次磁盘 IO 能够读取 1 页 = 4kb，那么省去 value 的情况下同样一页数据能够读取更多的 key，这样就大大减少了磁盘的 IO 次数。

此外，B+Tree 也是排好序的数据结构，数据库中 >< 或者 order by 等都可以直接依赖这一特性。

MySQL 中对于索引使用的主要数据结构也是 B+Tree，目的也是在读取数据时能够减少磁盘 IO。

## 3 千万级数据如何用 B + 树索引快速查找 ##

MySQL 官方对非叶子节点 (如最上层 h = 1 的节点，B+Tree 高度为 3) 的大小是有限制的，最大的大小是 16K，可以通过以下 SQL 语句查询到，当然这个值是可以调的，既然官方给出这个阈值说明再大的话会影响磁盘 IO 效率。

![500b987a0b4982e76ff63b85fe602b37.png][]

从执行结果，可以看到大小为 16384，即 16K 大小。

假如：B+Tree 的表都存满了。主键索引的类型为 BigInt，大小为 8B，指针存储了下个节点的文件地址，大小为 6B。最后一层，假如 存放的数据 data 为 1K 大小，那么

1.  第一层最大节点数为： 16k / (8B + 6B) ≈ 1170 (个)；
2.  第二层最大节点数也应为：1170 个；
3.  第三层最大节点数为：16K / 1K = 16 (个)。

则，一张 B+Tree 的表最多存放 1170 *1170* 16 ≈ 2 千万。

![2ffaf36b09740ad5f00af13a4d08620e.png][]

所以，通过分析，我们可以得出，B+Tree 结构的表可以容纳千万数据量的查询。而且一般来说，MySQL 会把 B+Tree 根节点放在内存中，那只需要两次磁盘 IO 就行。

## 4 存储引擎索引实现 ##

MySQL 中索引储存在哪里呢？和数据一样，索引以文件形式储存在硬盘上。  
在 MyISAM 储存引擎中，数据和索引文件试试分开储存的，数据存在.MYD 结尾的文件中，索引单独存在.MYI 结尾的文件中。

![2f59406bea812bdb4e759c84c62cea0a.png][]

在 InnoDB 中，数据和索引文件是合起来储存的，注意下图中没有了.MYI 结尾的文件，只有一个.ibd 结尾的文件。

![ec5fbb61a5d097bf415c09b9c962724d.png][]

MyISAM 索引文件和数据文件是分离的 (非聚集)，并且主键索引和辅助索引（二级索引）的储存方式是一样的。

![1c6dc70a6b0426cddfbe00103bb7430c.png][]

![78d29e8c2adada9b6109edc898504e97.png][]

InnoDB 中索引文件和数据文件是同一个文件（聚集），并且主键索引和二级索引储存方式有所不同，如图所示，二级索引的叶子节点不储存数据，仅储存主键 ID。

![88e8413f20917a7b931480f50e08dc9b.png][]

![bc8fd8aed3e388290ab312a686904db1.png][]

这里思考几个问题：

*  为什么建议 InnoDB 表必须建主键，并且推荐使用整型的自增主键？
 *  为什么非主键索引结构叶子节点存储的是主键值？

如果我们在创建表时不设置主键，InnoDB 会自动帮我们从第一列开始筛选一列数据不重复的列做为主键，如果找不到这样的列，就会创建一个隐藏的列（rowid）做为主键，这会增加很多 MySQL 的工作，所以建议我们在创建 InnoDB 表时一定要设置主键。

整型的字段做为主键，一方面在数据比较时不需要进行转换，另一方面存储也比较节省空间。那为什么要强调主键自增呢？如果主键 id 是无序的，那么很有可能新插入的值会导致当前节点分裂，此时 MySQL 不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过 OPTIMIZE TABLE 来重建表并优化填充页面。反之，如果每次插入有序，那就会在当前页后面连续写入，写不下就会重新分配一个节点，内存都是连续的，这样效率自然也就最高了。

非主键索引的叶子节点存储主键值而非全部数据，主要也是为了一致性和节省空间。如果二级索引储存的也是数据，那么每次插入 MySQL 都不得不更新每棵索引树，这样就加剧了新增编辑时的性能损耗，并且这样一来空间利用率也不高，必然产生了大量冗余数据。

## 5 联合索引底层数据结构又是怎样的 ##

联合索引又叫复合索引，例如下表：

CREATE TABLE `test` (
    `id` bigint NOT NULL AUTO_INCREMENT,
    `name` varchar(24) NOT NULL,
    `age` int NOT NULL,
    `position` varchar(32) NOT NULL,
    `address` varchar(128) NOT NULL,
    `birthday` date NOT NULL,
    PRIMARY KEY (`id`),
    UNIQUE KEY `idx_name_age_position` (`name`,`age`,`position`) USING BTREE
    ) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

如下索引就是一个联合索引。

`idx_name_age_position` (`name`,`age`,`position`) USING BTREE

联合索引底层数据结构长什么样？

![c7765814a43195285b82e5e2afd5b525.png][]

比较相等时，先比较第一列的值，如果相等，再继续比较第二列，以此类推。

了解了联合索引的存储结构，我们就知道了索引最左前缀优化原则是怎么回事了，在使用联合索引时，对于索引列的定义顺序将会影响到最终查询时索引的使用情况。例如联合索引（name,age,position），MySQL 会从最左边的列优先匹配，如果最左边的带头大哥 name 没有使用到，在未使用覆盖索引的情况下，就只能全表扫描。

联合底层数据结构思考：MySQL 会优先以联合索引第一列匹配，此后才会匹配下一列，如果不指定第一列匹配的值，也就无法得知下一步查询哪个节点。

## 6 总结 ##

索引本质上是一种排好序的数据结构，了解了 MySQL 索引的底层数据结构及存储原理，可以帮助我们更好地进行 SQL 优化。其实数据库索引调优是一项技术活，不能仅仅靠理论，因为实际情况千变万化，而且 MySQL 本身存在很复杂的机制，如查询优化策略和各种引擎的实现差异等都会使情况变得更加复杂。但同时这些理论是索引调优的基础，只有在明白理论的基础上，才能对调优策略进行合理推断并了解其背后的机制，然后结合实践中不断的实验和摸索，从而真正达到高效使用 MySQL 索引的目的。

[cb4aa4d7259666cca3ee7d68a3b1d4aa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3b9b512e887a413eae7ed93cdaf03b29.png
[2b3e669a91009418f17de2dd0c0e6751.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/f6630bcecf294a33ae3d89a4b4915dac.png
[4deab7fd6b34cb43b2095af93daaacff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/086946cb3f6b49dfac1bb58124f1c8b8.png
[75ef63c5e2b64dba005adba7160ab89c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/69c660a6a5704d2eb0774fc2c5912a3d.png
[9b19b7e775e082d9012af56b7505a21e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/cfd44b9126064375a179330c4302b33b.png
[be41c6b8c4c66bb4f06df8d7a7120d24.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/a5a4c796dab0421ebc94af4dc604fa6b.png
[500b987a0b4982e76ff63b85fe602b37.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/083f0332b50e4481be1557c30fe1d953.png
[2ffaf36b09740ad5f00af13a4d08620e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/e82b958c483146ee910381b5c31121d5.png
[2f59406bea812bdb4e759c84c62cea0a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/ff54d7b57bda48678e5e68972f4a5025.png
[ec5fbb61a5d097bf415c09b9c962724d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/36daca09672a404c8d2b6663f09b6461.png
[1c6dc70a6b0426cddfbe00103bb7430c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/368b6b9d60d6419091508023a99f8293.png
[78d29e8c2adada9b6109edc898504e97.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/0af1bb36d4a943e6909a9405e8384efd.png
[88e8413f20917a7b931480f50e08dc9b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/d822827f113e442895ce53e6331ace57.png
[bc8fd8aed3e388290ab312a686904db1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/4c1bec2f5a6541fa907dc6fe3c153ea0.png
[c7765814a43195285b82e5e2afd5b525.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/1c16ec37cac74d14ad03cfa627a941ab.png