关于mysql:深入理解MySQL索引底层数据结构

1 引言

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

2 索引数据结构比照

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

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

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

Hash 表
通过索引的 key 进行一次 hash 计算，就能够疾速获取磁盘文件指针，对于指定索引查找文件十分快，然而对于范畴查找没法反对，有时候也会呈现 Hash 抵触的状况。

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

但如果是一个依照程序递增的值，例如为 col1 建设索引，不再适宜应用二叉树建设索引，因为此时应用二叉树建设索引将会变成一个链式索引，此时的索引构造如下图所示，如果查找 6 节点须要 6 次遍历能力找到。

红黑树
红黑树是一种二叉均衡树，能够进步查问效率，此时若再查找 6 节点只须要遍历 3 次就能找到了。但红黑树也有毛病，当存储大数据量时，树的高度就会变的不可控，数量越大，树的高度越高，查问的效率将会大大降低。

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

B+Tree
B+Tree 是 B -Tree 的变种，所具备的特点：1 非叶子节点不存储 data，只存储索引(冗余)，能够放更多的索引；2 叶子节点蕴含所有索引字段；3 叶子节点用指针连贯，进步区间拜访的性能。

与红黑树相比，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 效率。

从执行后果，能够看到大小为 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 千万。

所以，通过剖析，咱们能够得出，B+Tree 构造的表能够包容千万数据量的查问。而且一般来说，MySQL 会把 B+Tree 根节点放在内存中，那只须要两次磁盘 IO 就行。

4 存储引擎索引实现

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

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

MyISAM 索引文件和数据文件是拆散的(非汇集)，并且主键索引和辅助索引（二级索引）的贮存形式是一样的。

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

这里思考几个问题：

• 为什么倡议 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

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

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

理解了联结索引的存储构造，咱们就晓得了索引最左前缀优化准则是怎么回事了，在应用联结索引时，对于索引列的定义程序将会影响到最终查问时索引的应用状况。例如联结索引（name,age,position），MySQL 会从最右边的列优先匹配，如果最右边的带头大哥 name 没有应用到，在未应用笼罩索引的状况下，就只能全表扫描。

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

6 总结

索引实质上是一种排好序的数据结构，理解了 MySQL 索引的底层数据结构及存储原理，能够帮忙咱们更好地进行 SQL 优化。其实数据库索引调优是一项技术活，不能仅仅靠实践，因为理论状况变幻无穷，而且 MySQL 自身存在很简单的机制，如查问优化策略和各种引擎的实现差别等都会使状况变得更加简单。但同时这些实践是索引调优的根底，只有在明确实践的根底上，能力对调优策略进行正当推断并理解其背地的机制，而后联合实际中一直的试验和摸索，从而真正达到高效应用 MySQL 索引的目标。

最初，如果大家想再复习一下数据结构的常识，这个数据结构网站（https://www.cs.usfca.edu/~galles/visualization/Algorithms.html）不可错过，能够很好地帮忙咱们演示数据结构的存储过程。

作者：京东物流 于朔