MySQL 索引原理及设计

索引一直是数据库中非常重要的概念，所以了解索引相关的知识是转入后端开发中必不可少的一环。这篇文章是我从开始做后端开发之后至今学习关于索引知识的一个总结，从原先很多概念的模糊和不理解到现在大致有一个比较清楚的认知，尽量会把关于索引的一些点以及为什么需要这么做给解释明白，包括使用 InnoDB 引擎的 MySQL 索引的相关概念，以及如何针对 InnoDB 进行索引的设计和使用，以及三星索引的概念，会从我所了解到的知识去解释为什么需要这样。

B+ Tree

在 InnoDB 中，索引使用的数据结构是 B+ Tree，这里的 B 是 Balance 的意思。B 类树的一个很鲜明的特点就是树的层数比较少，而每层的节点都非常多，树的每个叶子节点到根节点的距离都是相同的（这也是为什么叫 Balance Tree 的原因），另外，树的每一个节点都是一个数据页，这样每个节点只需要一次 IO 就可以全部读取。这样的结构保证了查询数据时能尽量少地进行磁盘 IO，同时保证 IO 的稳定性。

B+ Tree 和 B Tree 不同，B+ Tree 中，只能将数据存储在叶子结点中，内部节点将只包含指针，而 B Tree 可以将数据存储在内部的叶节点中。因此 B+ Tree 的关键优势是中间节点不包含数据，因此 B+ Tree 的大小远小于 B Tree，并且可以将更多数据存储到存储器中。另外，B+ Tree 的每一个叶子节点包含了到相邻的节点的链接，这样可以快速地进行范围遍历。

主索引和辅助索引

在 InnoDB 存储引擎中，每一个索引都对应一棵 B+ Tree，InnoDB 的索引主要分为主索引和辅助索引：

• 主索引：包含记录的文件按照某个 key 制定的顺序排序，这个 key 就是主索引，也就是主键，也被称为聚簇索引。因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚集索引。在 InnoDB 中，主索引的叶子节点存的是整行数据，这也意味着 InnoDB 中的表一定要有一个主索引；
• 辅助索引：某个 key 指定的顺序与文件记录的物理顺序不同，这个 key 就是辅助索引。InnoDB 中的辅助索引在叶子节点中并不存储实际的数据，只会包含主索引的值 。这就意味着如果使用辅助索引进行数据的查找，只能查到主索引，然后根据这个主索引再次扫描以下主索引的树，进行一次回表操作；

上面讲到，InnoDB 的表中要求必须有一个主键，那么可能有人会将身份证号这种唯一性的标识作为主索引，这样就大错特错了。刚刚说到主键也被称为聚簇索引，它是要按照顺序进行 排序 的，要求有聚簇性。如果将身份证号作为主键，不能保证每次插入的数据都是按照身份证号的顺序进行排列的，这就使得每次主键的插入都变得完全随机，可能导致每次插入一条数据都会引起页分裂的问题（这个话题在后面会讲到）。所以在表结构定义的时候，应该使用一个具有聚集性的 key 作为主键，如果真的没有的话，可以使用一个 AUTO INCREMENT 代理键作为主索引，这样可以保证数据行是顺序写入的。如果你真的完全没有定义主键，InnoDB 会选择一个唯一的非空索引代替，但是如果没有这样的索引，InnoDB 会隐式定义一个主键来作为聚集索引。

正因为 InnoDB 索引的这种结构，产生了一些限制：

1. 如果不是按照索引的最左列开始查找，则无法使用索引；
2. 不能跳过联合索引中的某些列；
3. 如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找；

以上几点也基本上代表常听到的“最左前缀”，我们通过几个例子来解释一下这个问题，可能有的情况举的例子不太恰当，但希望能说明白想说出的问题。假设我们有一个 users 表，表结构如下：

这个表中我们有 (name, age) 这个联合索引，这个索引的结果大概如下图所示：

在上面的叶子节点下，是先按照 name 排序（假设是按照字母表排序的），再按照 age 进行排序。

查询 1:

SELECT * FROM users WHERE name='张亮' AND age=17;

上述这种查询，根据 (name, age) 这个索引树来查找，找到 id 为 2 的索引数据符合条件，然后通过相邻的节点链接继续查找，发现下一个数据不符合条件，最终命中索引的就是 id 为 2 的这一条数据，因为是要查找行的所有数据，所以再根据 id 为 2 去主键索引树中继续回表查找，得到结果数据。

查询 2:

SELECT * FROM users WHERE name='张亮';

根据 (name, age) 这个索引树来查找，找到 id 为 2 的索引数据符合条件，然后通过相邻的节点链接继续查找，发现下一个数据也符合条件，继续根据节点链接查找，发现数据已经不符合条件了，于是命中索引的就是 id 为 2 和 3 的两条数据，然后继续根据这两个 id 值进行回表操作，得到结果数据。

查询 3:

SELECT * FROM users WHERE age=17;

根据“最左前缀”原则，并不存在 age 为前缀的索引，所以这个查询无法使用 (name, age) 这个索引树进行数据查找，得去主索引中进行全表扫描，这无非是非常慢的。所以如果想让这个查询命中索引，得单独为 age 添加索引或者添加 age 为前缀的联合索引。或者，这类情况还有一种方法，就是给跳过的索引列使用 IN 的查询方式让其发生“最左前缀”匹配，但是在这里 name 这个字段不适合用 IN 这种查询方法。

查询 4:

SELECT * FROM users WHERE name like '张%' AND age=37;

根据“最左前缀”原则，这条查询还是可以用得上 name 的索引，但是用不了 age 这个索引。所以类似前缀字符串、范围查询都可以命中索引，但是前缀字符串或范围查询后面的列就无法使用索引了。对于此种情况，MySQL 5.6 版本增加了 Index Condition Pushdown 技术，如果查询中 where 语句可以使用索引中已有的字段（比如这里就是 name，age），在遍历索引时对这些字段先做判断直接过滤掉不满足条件的值，减少引擎层访问表的次数和 MySQL Server 层访问存储引擎的次数。但是这种技术跟“最左前缀”并无冲突，只是做了数据过滤的优化。

查询 5:

SELECT * FROM users WHERE name=12345;

这个查询其实放在这里不合适，但是我想借着这个例子说明两个问题。首先 name 是 varchar 类型，但这个查询语句中将其与数字类型做比较，这时候会触发 MySQL 的隐式类型转换，将字符串转换成数字进行比较，也就是说上述的语句相当于：

SELECT * FROM users WHERE CAST(name AS int)=12345;

也就是说，在这个查询中对索引字段做了函数操作，而这样的话会破坏索引值的有序性，于是不会命中索引，转而进行全表扫描。

查询 6:

SELECT age FROM users WHERE name='张妹';

这种情况类似与查询 2 中所举的例子，查处 id 为 4 的值，但是这个查询的结果要求只返回 age，而 age 的值是包含在索引中的，这样就可以直接返回而不用再进行回表查询了。如果一个索引包含所有需要查询的字段的值，则为覆盖索引，使用覆盖索引不需要进行回表操作，能增加数据查询效率。

ORDER BY 如何使用索引

有的时候，我们的查询语句会使用 ORDER BY 语句来得到我们想要的排序后的结果，这时候索引还是会发挥其作用的，因为索引树的叶子结点就是按照排列顺序进行组织的。所以 MySQL 可以使用同一个索引既满足排序又用于查找行，所以一个索引如果能同时满足这两点是最好的。但是要注意的是，只有当索引的列顺序和 ORDER BY 子句顺序完全一致，并且所有列的排序方向都一样，才能够使用索引来对结果进行排序。

......待补充，MySQL 的 ORDER BY 是如何工作的？

如何更好的创建索引

综合以上所说的知识，我们总结一下如何创建高性能的索引，这里就涉及到一个“三星索引”的概念。怎样才算是一个三星索引？

• 满足第一颗星：取出 WHERE 语句后的所有等值条件列，将这些列作为索引最开始的列，顺序的话根据 MySQL 最左前缀法则进行权衡，将选择性高的放在前面（或者根据业务情况自行判断），这样可以保证每次命中的索引片较小；
• 满足第二颗星：将 ORDER BY 列加入到索引中，不改变这些列的顺序，不考虑第一颗星已经出现的列；
• 满足第三颗星：将查询语句中剩余的列加到索引中去，达到覆盖索引的效果。

......待补充，三星索引的例子

页分裂

前面说到，InnoDB 中数据是存储在数据页中的，而数据是按照索引的顺序插入到数据页中的，所以数据是紧凑排序的，但如果随机对数据进行插入，就有可能导致数据页分裂的问题。

假设一个数据页只能存储 3 条数据，且已经有 3 条数据（100， 200， 300）了，这时候想插入一条 150 的数据，就会再申请一个新的数据页，100，150 两条数据存放在原来的数据页中，200 和 300 存放在新的数据页中，这样可能会存在数据页利用率不高的问题。

不仅仅是插入数据会导致上述问题，删除数据也会。这里要注意，如果删除掉了一个数据页中的某条数据，这条数据所留下的位置并不会缩小而是等待复用，如果是一整个页的数据被删除了，那这个页也是出于被复用状态。如果相邻的两个数据页的利用率很小，系统会把这两个页的数据合到其中一个页上，另一个页就处于可被复用的状态。所以通过 delete 删除数据并不会回收表空间。

为了解决频繁删除数据导致的没有回收表空间的问题，可以通过重建表来解决，比如以下命令：

alter table table_name engin=InnoDB;

这个命令的流程基本上是：

1. 新建一个临时表，结果同原表相同；
2. 按照主键 ID 递增的顺序将数据从原表读出插入到新表中；
3. 用新的表替换旧表，删除旧表；

所以我们使用 AUTO INCREMENT 主键的插入数据模式，正符合了递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。