背景
前阶段学习、面试中，反复遇到 MySQL InnoDB 存储引擎索引部分的内容。据说只有给别人讲懂才是真的懂，这里本文将学习所得总结分享如下。
本文以讲解原理为主，以讲解索引部分为主。
前序知识
本文面向读者不是零基础，需要读者至少有以下知识基础：
- 基本的数据结构基础：掌握链表、二分法、B+ 树等
- 数据库基础，基本的数据库操作，基本的 SQL 语句
InnoDB 索引原理
InnoDB 存储策略
为了更好地理解本文内容，这里会对一些关键的基础知识进行补充介绍。如果对该部分内容比较熟悉，可以略过本部分。
InnoDB 页
页，是内存与磁盘交互的最小数据单位，有多种页类型。
每页的默认大小为 16KB ，这个大小在初始化时指定，指定后不能修改。
行格式 COMPACT
一条记录在数据库中存储的方式。
MySQL 5.7 以后默认采用的行格式（DYNAMIC）与 COMPACT 类似，但在溢出页（数据列太大，一页装不下时的处理办法）的处理上有所不同。
简化的 COMPACT 行格式示意图
其中，记录头中包含下列关键信息（部分）：
- n_owned: 一个数据页（索引页）可能包含很多条记录，为了加快在页内的查询速度，这些记录做了分组。而 n_owned 即表示当前分组内包含的记录条数。
- next_record: 每个数据页（索引页）中包含多条记录，页内的这些记录形成了一条单向链表，该字段表示当前记录指向下一条记录的指针。
此外，每条记录还包含自动生成的隐藏列，通常用于处理事务以及回滚。其中，row_id 列不一定生成。InnoDB 主键生成策略中，优先使用用户定义的主键作为主键，如果没有，则选取一个不允许为空的 UNIQUE 键作为主键，如果均不存在，则默认添加该隐藏列（row_id）作为主键。
InnoDB 数据页（索引页）结构
多条记录会存放到一个数据页（索引页）中保存到磁盘，读取数据时以数据页为单位。多个数据页之间通过指针连接形成双向链表，链表的每个节点在磁盘中的存储是离散的，但是相邻的数据页会尽量集中在一起。
简化的数据页（索引页）示意图
图中的部分解释如下
- 头部信息：存放一些页面、文件的状态信息，同时存储前一页、后一页的指针。
- 记录数据：存放实际的记录，即满足行格式的真实数据。
- 页目录：为加快在一个数据页内查询数据建立的页目录。页目录中保存本页中被选为 “组长” 记录的指针。（个人理解类似跳表中的索引）
- 页尾信息：保存部分头部信息的冗余，用于防止数据在传输一半时丢失，起到校验作用。
B+ 树索引结构
为解释方便，我们假设这样一个表（tab_demo）
简介
在这里，我们忽略掉实现的细节，只看 B+ 树索引的基本结构。
聚簇索引：如图所示，非叶子节点存储的都是索引，因为只存储索引数据，所以通常一页能存储大量的索引数据。叶子节点存储实际数据，这样的 B+ 树也叫聚簇索引。
二级索引：叶子节点存储主键值的 B+ 树。比如我们创建了 ind_1 索引，这会为其创建一棵 B+ 树，这棵索引树采用的排序依据是 key1 字段，而叶子节点存储的实际数据为主键。这样在查找时，首先查找二级索引得到主键，再到聚簇索引中查询实际数据。这个二次查找的过程也叫回表。
联合索引：使用多个列作为索引时，创建的 B+ 树称为联合索引，采用创建索引的多个列作为排序依据。
索引的使用
通过以上内容，不难发现，索引能有效提高查询速度，如果没有索引，我们的查询只能通过全表扫描来进行。
但是，索引并不是越多越好，维护索引也需要很大的开销：
- 空间成本：每创建一棵 B+ 树（即索引），都需要创建很多页来保存索引信息，在数据量比较大的情况下，空间开销将会很大
- 时间成本：维护索引的消耗，如数据页的分裂、回收等操作，通常我们无法保证插入的数据对所有的索引来说都是有序的，这会导致 B+ 树的频繁调整；此外索引太多时，在执行查询前要分析各个索引的查询成本以选择最低成本的索引。
扫描区间
在索引列与常数产生关系时（比如：IN, !=, <, > 等）即可产生扫描区间，默认的扫描区间为 (-∞, +∞) ，表示全表扫描。
使用 LIKE 语句时，只有在匹配完整字符串或者匹配前缀时索引才生效。匹配时，逐字符进行匹配。
比如：WHERE key2 LIKE '%dd' 不会使用索引，而 WHERE key2 LIKE 'dd%' 可以使用索引
使用 AND、OR 连接多个条件时，每个条件都会形成自己的扫描区间，通过集合的交并运算得到最终的扫描区间。
联合索引的时候，生成的扫描区间与索引列的顺序有关，建立索引时，越靠左的索引列在排序时优先级越高。
举例如下：
-
语句：
SELECT * FROM tab_demo WHERE key1 > 23 AND key1 < 77扫描区间为 key1 的(23,77) -
语句:
SELECT * FROM tab_demo WHERE key2 > 'bb' AND key3 > 'aaa'字符串是可以比较的，这条语句的扫描区间为 key2, key3 的((bb, aaa), +∞) -
语句:
SELECT * FROM tab_demo WHERE key2 > 'bb' OR key3 > 'aaa'这条语句的扫描区间为(-∞, +∞)因为使用 ind_2 索引时，key2 字段有索引，扫描区间为 (bb, +∞)，而 key3 字段无法使用索引，因为 OR 运算，无法确保满足 key2 > 'bb' 的数据都满足条件，而对于 key3 字段，没有单独的索引，所以扫描区间为(-∞, +∞)，取并集后还是(-∞, +∞)。
使用索引的排序、分组
使用 ORDER BY（或 GROUP BY） 时，ORDER BY 子句后的排序列必须按照索引的顺序列出，否则无法使用索引。
索引失效的情况：
- ASC, DESC 混用的情况：只有在顺序相同的时候才生效，逆序也可以（记录在索引页中是单链表，但是有页目录的存在，使得查找之前的记录并不复杂，但很显然，比顺序麻烦）。在 MySQL8 中引入的 Descending Index 对混用的特性做了支持
- 排序使用的列不属于同一索引
- 排序使用的列在索引中的顺序不连续
- 形成扫描区间的索引列与排序列不同
- 对排序列进行了修饰，如调用了函数等
覆盖索引
在业务需求允许范围内，如果查询的字段可以被使用的索引完全包含，则可以使用二级索引时，可以完全避免回表的过程。
比如语句：SELECT key2, id FROM tab_demo WHERE key2 > 'abc' 在扫描完区间 (abc, +∞) 后即可得到需要的解集，无需回表。
更有效地利用索引
回表的代价很大，通过二级索引得到的主键是乱序的，每个主键都需要一次回表操作，因此消耗较大。如果需要回表的数据过多，有时不如全表扫描的效率高，此时查询优化器就会放弃使用二级索引。通常可以使用 LIMIT 子句控制返回的数据条数。
建立、使用索引时，应该尽量遵循下列约定：
- 只为用于搜索、排序、分组的列创建索引
- 值大量重复的列不适合建立索引，会导致筛选效果太弱从而造成大量的回表操作
- 尽可能使用小类型的列，这样索引会占用更少的内存。比如整数类型中 TINYINT, MEDIUMINT, INT, BIGINT 的类型依次增大
- 为索引列建立前缀索引，字符串类型的键如果完全保存可能会占用较大内存，可以通过只保存前缀来优化。
- 尽可能使用覆盖索引，即在查询语句中声明需要查询的字段为包含在索引中的列，这样可以完全避免回表。
- 尽量保证插入数据时，主键的增长顺序不变，忽大忽小会造成 B+ 树的频繁大规模调整
- 避免冗余、重复索引
以下情况时，不推荐建立索引
- 表记录太少
- 经常删改的表或字段
- where 条件里用不到的字段
- 过滤性不好的字段
主要参考
本文内容均为博主手动输出（包括图），没有盲目拷贝，但是肯定有参考，毕竟 MySQL 不是咱写的，主要参考以下内容：