MySQL -- 索引指南

本文以MySQL InnoDB引擎为基础，讲解索引相关概念以及优化手段，很适合开发以及业务同学参考，避免工作中因为DB性能导致的一系列雪崩问题。

索引的组织结构

在InnoDB下，索引文件与数据文件是合并在一起的，想象一下，一颗树，非叶子节点都是索引文件，叶子节点都是数据文件，从而构成一张完整的表数据，因此还有一种专业说法叫索引组织表。该模式下索引文件即数据文件，数据文件即索引文件，但是为了提高查询速度，必然会在逻辑上分为索引与数据两部分内容，索引大多数时候都是存放在内存中，当一个查询在索引中定位数据后，会去磁盘中加载对应的数据内容，因此一定程度上磁盘IO的次数成为了提高索引性能的关键点。因此极力避免磁盘IO的次数，是索引设计的一个导向标。

索引的数据结构

在了解数据结构前，需要了解索引的目地在于检索，二分搜索则是一种很有效的检索方式，二分搜索在检索过程中会遇到哪些问题？

对于一颗普通的二叉树(34，22，89，5，23，77，91)，如下图所示，当树的深度为3时，其检索一个数最多需要三次比较。

如果树的深度变成了7，那么检索则需要七次比较，此时从对比角度，其性能退化成了链表。

为了解决树的深度太高的问题，出现了一种平衡二叉树，即每个节点的左子树对比右子树，节点高度差不能超过1，如下图所示，树的深度为5，节点数为31，对于动则几十万的数据表来说，平衡树仍然会导致树的深度很高。

为了解决上述问题，B树出现了，B树本质上可以理解为一颗平衡M叉树，M为每一个节点能够拥有的子节点数，M称为B树的阶。假设M为100，那么一个高度为3的B树，则大约可以容纳 100w的数据量，那么自然很适合存储索引，如下图所示，当要查找数据29时，第一步找到磁盘块1(17-35)，定位到P2，去磁盘块3(26，38)查找，定位到P2，去磁盘块8查找，找到数据。
B树在定位数据上已经很棒了，但是对于范围类查找磁盘IO次数难以控制，比如查询13-75之间的所有数据，则需要从根节点开始不停的搜索，直到找到两边边界位置。

B+树是在此基础的优化，与B树最大的不同有两点。1：其叶子节点只存放数据，非叶子节点存放索引。2：非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大 (或最小)，因此叶子节点之间使用双向链表连接。如下图所示结构。

1. 为什么非叶子节点不能存放数据？
该问题本质上是为什么不能使用B树的结构。这里借用 为什么 MySQL 使用 B+ 树 · Why’s THE Design? 中的描述图。

B树的非叶子节点中会存放数据，因此每一次查询都必须从根节点开始，因为每一个节点上都可能会有数据，因此对于范围类型查询就会很吃力，磁盘IO次数会增加不少。其次由于节点中包含数据，一般情况下数据比索引会大很多，因此也不适合全部存放到内存，索引本身就会消耗掉一些磁盘IO，而B+树则改进了这些缺点，更加优化了索引定位后，再获取数据这一策略。

2. 叶子节点为什么使用双向链表？
对于B+树，其叶子节点使用双向链表关联起来，假设查询条件where age > 5 and age < 9，其中age存在索引，那么根据age查询到9这个节点后，其可以利用索引的有序性，直接通过双向链表进行范围查询，而不需要再次从根节点出发。

索引的类型

聚集索引

在InnoDB中，聚集索引指的是主键所对应的B+树，之所以叫聚集，因为其是根据主键索引进行存储，索引即数据，数据即索引。
一张表只能有一个主键，一张表只能有一个聚集索引，因此聚集索引的选择就比较真贵，对无意义的id来管理聚集索引的方式应该有所排斥。

非聚集索引

在InnoDB中，主键以外的辅助索引为非聚集索引，也有说法叫次级索引，其特点是叶子节点会指向对应的主键索引，而不是直接指向数据，索引本身就是索引。因此当一个查询使用到了辅助索引，其本质上会查询两颗树，一是该辅助索引对应的B+树，找到主键后，再去主键索引对应的B+树去获取对应的数据。

索引的优化

阐述上述结构的最终目地是为了优化，而优化更多的是从开发者角度建立合适的表结构以及索引，写出走合理索引的SQL。

选择合适的主键

当表未指定主键时，MySQL会自动生成6字节的rowId作为主键，一般业务上不会采取这种方式，即使没主键也会指定一个自增id作为主键来管理。当表存在主键时，该主键则是维持聚集索引的key，因此需要考虑以下问题：

• 有序性，减少B+树的调整。
• 大小控制，因为非聚集索引会指向主键索引，因此会造成非聚集索引的内存占用量增加。

选择合适的列建立索引

索引的选择与具体的业务息息相关，比如用户表一般都是根据手机号以及邮箱查询，那么就不适合在name上建立索引，索引字段的选择一般参考以下几个因素：

• 区分度要高，例如sex与phone两列相比，sex的区分度太低，此时及时条件走了索引，仍然会命中大量数据，然后进一步筛选。
• 有序，索引具有有序性，每次写入或者删除数据时，会涉及B+树的调整，因此当表的写入量很大时，需要考虑这一步的消耗
• 长度合适，索引可以认为是全部放到内存中的，因此合适的大小能够减少大量的内存消耗，针对超长字符串可以选择指定索引前缀长度等方式进行优化。

编写走索引的SQL

如何编写走索引的SQL，该问题需要了解MySQL针对索引所定制的一些规则，比如最左前缀匹配规则，索引失效场景规则，以及一些常见查询索引解决方案。该部分情况比较复杂，因此下面简单列一下，了解大概规则后，最佳做法是使用explan关键词进行分析，针对分析结果进行SQL或者索引的调整。

• 对索引进行表达式计算，那么索引会失效，因为需要把索引字段值全部取出来做比较后才能排除。
• 对索引使用函数，那么索引会失效，与上述同理。
• or查询左右两边只有一边能使用到索引。or查询本质上是两边都满足才会使用到索引，因此只有一遍走索引时，当不满足，另一边仍然会全表扫描
• Like查询以%或者中间存在%，由索引结构可知，索引判断只能从头开始匹配，无法从中间或者结尾匹配
• 使用NULL或者NOT NULL比较，索引列不存储空值，因此该比较会造成索引失效。
• 联合索引最左前缀规则

还有一些可以很好的从应用层解决的问题，比如一张用户黑名单表,使用 身份证 + 手机号作为唯一约束,那么索引该怎么设计才能提高查询效率？这种场景设计比较多，比如直接建立自增id主键，然后身份证+手机号联合索引，如果更新不频繁还可以通过md5方式，取一个hash后作为主键，然而这种场景下应用层完全可以使用布隆过滤器进行预先过滤，布隆过滤器中不存在的则一定不存在，大大会减少DB查询量，因此设计索引时需要关注具体业务场景，不能只看索引。

三星索引法

三星索引法是《数据库索引设计与优化》提出的一种建立合理索引的措施，具体如下：

• 一星索引：取出所有等值谓词的列，作为索引的开头，目的是减少扫描数据数量
• 二星索引：将order by中的列加入到索引当中，目的是避免文件排序增加磁盘IO
• 三星索引：将查询语句剩余的列加入到索引当中，目的是走覆盖索引，避免磁盘IO
  以select id, name, age from user where name='link' order by age desc为例，索引(name, age, id) 是一个三星索引，而索引(name) 不是一个三星索引，然而在业务中往往索引(name)就能够满足该查询，从而减少内存消耗，因此三星索引可以作为一个索引好不好的参考，而具体业务场景下没必要过分追求三星索引。

参考

为什么 MySQL 使用 B+ 树 · Why’s THE Design?
极客时间 – SQL必知必会
MySQL 索引设计概要

• 版权声明: 感谢您的阅读，本文由屈定's Blog版权所有。如若转载，请注明出处。
• 文章标题: MySQL -- 索引指南
• 文章链接: https://mrdear.cn/posts/mysql-index-guide.html