索引是帮助存储引擎快速获取数据的数据结构（类似书的目录），存储引擎就是如何存储数据、如何建立索引、如何更新、如何查询等技术的实现方法。MySQL 目前使用 InnoDB 作为默认的存储引擎。

索引分类

可以从四个角度来对索引进行分类：

• 按数据结构：B+ Tree 索引、Hash 索引、Full-text 索引
• 按物理存储：聚簇索引（主键索引）、二级索引（辅助索引）
• 按字段特性：主键索引、唯一索引、普通索引、前缀索引
• 按字段个数：单列索引、联合索引

从数据结构上来说，InnoDB 支持 B+ Tree 和 Full-text 索引，B+ Tree 索引也是 InnoDB 最常用的索引类型

以下所有内容描述均基于 InnoDB 引擎

B+ Tree

在创建表时，InnoDB 会根据不同场景选择不同的列作为索引：

• 如果指定了主键，则使用主键作为聚簇索引的索引键
• 如果没有指定主键，则选择第一个不包含 NULL 值的唯一列作为聚簇索引的索引键
• 以上都没有的情况，InnoDB 将自动生成一个隐式的自增 ID 列作为聚簇索引的索引键

其他索引都属于辅助索引/二级索引/非聚簇索引，创建的主键索引和二级索引默认情况下都使用 B+ Tree 索引

假设存在以下表结构：

1
2
3
4
5
6
7

CREATE TABLE `product`(
    `id` int(11) NOT NULL,
    `product_no` varchar(20) DEFAULT NULL,
    `name` varchar(255) DEFAULT NULL,
    `price` decimal(10, 2) DEFAULT NULL,
    PRIMARY KEY (`id`) USING BTREE
);

B+ Tree 是一种多叉树，非叶子节点只存放索引，只有叶子结点存储数据，并且每个节点中的数据都是按主键顺序存放的。

每一层父节点的索引值都会出现在下层节点的索引值中，因此在叶子节点中包含了所有的索引值信息

每个叶子节点都有两个指针，分别指向下一个叶子节点和上一个叶子节点，形成一个双向链表

通过主键索引查询

上述数据的主键索引结构如图所示：

假设我们通过以下语句查询数据：

1

select * from product where id = 5;

这条语句使用主键索引查询 id 为 5 的数据，查询过程中 B+ Tree 会自顶向下逐层进行查找：

• 将查询语句中的 5 与索引数据 (1, 10, 20) 进行比较，5 在 1 和 10 之间，索引找到第二层的索引数据 (1, 4, 7)
• 在第二层的索引数据 (1, 4, 7) 中进行比较，5 在 4 和 7 之间，索引找到第三层索引数据 (4, 5, 6)
• 在叶子结点的索引数据 (4, 5, 6)中进行查找，得到索引值为 5 的行数据

我们可以把每读取一个节点当做一次 IO 操作，那么上述查询过程一共经历了 3 个节点，也就是三次 IO 操作

B+ Tree 存储千万级的数据只需要 3-4 层高度就可以满足，意味着千万级的表查询目标数据最多需要 3-4 次磁盘 IO，因此 B+ Tree 的最大优势在于查询效率很高，因为即使在数据量很大的情况，查询一个数据的磁盘 IO 仍然能维持在 3-4 次

通过二级索引查询

主键索引与二级索引的 B+ Tree 的区别是：

• 主键索引的叶子节点存放的是实际数据，所有完整的行数据都存放在逐渐索引的叶子节点中
• 二级索引的叶子节点存放的是主键值

假设我们使用 product_no 字段建立二级错音，那么结构图如下：

其中非叶子节点的值是 product_no，叶子节点存放的是主键值

如果我使用以下语句查询商品:

1

select * from product where product_no = '0005';

会先通过 product_no 索引检索找到对应的叶子节点，获取到主键值，在通过主键索引查询到对应的叶子节点获取整行数据。

这个过程叫「回表」，也就是说需要查询两个索引才能获取到数据，如下图：

不过，当查询的数据已经包含在二级索引的叶子节点中的时候，就不用再查主键索引了，例如：

1

select id from product where product_no = '0005';

id 作为主键已经包含在 product_no 的叶子节点中，因此可以直接获取到数据。这种在二级索引就能查询到结果的过程叫做「覆盖索引」

为什么使用 B+ Tree 作为索引数据结构？

• 对比 B Tree
  • B+ Tree 只在叶子节点存储数据，而 B Tree 的非叶子节点也要存储数据，因此 B+ Tree 的单个节点数据量更小，在相同的磁盘 IO 下，能查询更多节点（前文提到获取一次节点就是一次磁盘 IO，实际是不准确的，仅为了方便理解）
  • B+ Tree 的叶子节点使用双链表连接，适合 MySQL 常见的基于范围的顺序查找
• 对比二叉树
  • 二叉树每个节点只能有两个子节点，因此同样的数据量查找需要更多次的磁盘 IO
• 对比 Hash
  • Hash 在做等值查询时的复杂度为 O(1)，但是不适合做范围查询

按字段特性的索引

从字段特性的角度来看，索引分为主键索引、唯一索引、普通索引、前缀索引。

主键索引

主键索引就是建立在主键字段的索引，通常在创建表的时候一起创建，一张表最多只能有一个主键索引，索引列的值不允许有空值

唯一索引

唯一索引的索引列的值必须唯一，但是允许有空值

普通索引

既简历在普通字段的索引

前缀索引

指对字符类型字段的前几个字符建立的索引，而不是在整个字段上建立的索引。前缀索引可以建立在字段类型为 char、varchar、binary、varbinary 的列上

使用前缀索引的目的是减少索引占用的存储空间，提升查询效率

联合索引

通过将多个字段组合成一个索引，该索引就称为联合索引。

假设我们建立 (product_no, name) 的联合索引，结构图如下：

可以看到，联合索引的非叶子节点使用两个字段的值作为 Key 值，当在联合索引查询数据时，先按 product_no 字段比较，在 product_no 相同时再按 name 字段比较

因此，使用联合索引时，存在「最左匹配原则」，也就是按照最左字段优先的方式进行索引匹配。如果不遵循「最左匹配原则」进行查询，联合索引就会失效，查询时就无法利用到索引进行快速查询了

假设存在一个 (a, b, c) 联合索引，以下几种查询方式都可以匹配上联合索引：

• where a = 1;
• where a = 1 and b = 2;
• where a = 1 and b = 2 and c = 3;

需要注意的是，由于有查询优化器，因此 a 字段在 where 中的顺序并不重要，存在即可

如果是一下几种查询条件，由于不符合「最左匹配原则」，联合索引就会失效：

• where b=2；
• where c=3；
• where b=2 and c=3；

之所以会有这种情况出现，是由于 b, c 两个字段是局部有序的。也就是在 a 相同的范围内是有序的，而对于整个索引来说，b 和 c 是无序的

联合索引的范围查询

在进行范围查询时，会有一些特殊情况。

如上文所述，假设存在 (a, b, c) 联合索引，那么 b, c 两个字段只有在 a 相等的范围内是有序的。那么假设存在以下查询:

1

select * from t_table where a > 1 and b = 2;

此时对于 a > 1 这个范围来说，b, c 两个字段并不是有序的，因此在当前查询中，a 字段可以利用联合索引进行筛选，而 b 字段无法通过索引进行筛选。

如下示例：

1

select * from t_table where a >= 1 and b = 2;

此次查询相比上一个查询多了 a = 1 的筛选条件，因此在进行索引查找时，在 a = 1 的范围内，b 字段是可以通过联合索引进行筛选的。但是在 > 1 的区间范围内，b 字段无法通过索引进行筛选。

索引下推

从上文我们知道，(a, b, c) 联合索引，select * from t_table where a > 1 and b = 2 的时候只有 a 字段可以用到索引。那么在联合索引中找到第一个满足条件的主键值之后，还需要判断其他条件是否满足(b = 2)，此时需要在哪里判断呢？

• 在 MySQL 5.6 以前的版本，只能从查找到的记录开始一个个回表，从主键索引找到数据行，再比对 b 字段
• 在 MySQL 5.6 引入了「索引下推」优化，可以在联合索引遍历过程中，对联合索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数

当使用 explain 查看执行计划时，如果出现了 Extra 为 ‘Using index condition’，那么说明使用了索引下推的优化

索引的区分度

建立联合索引时的字段顺序，对索引效率也有很大影响。从上文的索引结构中我们可以知道，越靠前的字段，过滤效率越高。因此在建立联合索引时，要把区分度大的字段排在前边。

例如，性别字段由于只存在男/女两个值，因此区分度很小，不适合排在联合索引靠前的位置。因为无论使用哪个值做筛选，都能得到一半的数据。而在 MySQL 中还有一个查询优化器，如果优化器发现某个值出现在数据行中的百分比很高的时候（惯用的分界线为 30%），一般会忽略索引，进行全表扫描

联合索引排序

假设存在以下查询：

1

select * from order where status = 1 order by create_time asc;

此时推荐的索引方式是简历 (status, create_time) 的联合索引。由于索引的有序性，在查询时，可以在 status 筛选后直接得到按照 create_time 排好序的数据，提高了查询效率

什么时候需要/不需要创建索引？

使用所以可以有效提高查询速度，但同样也有缺点：

• 需要额外的物理空间存储索引数据
• 创建索引和维护索引都需要耗费时间，且小号的时间会随着数据量的增大而增大
• 由于维护索引需要耗费时间，因此会降低增删改操作的效率。每次的数据变更都会是 B+ Tree 为了维护索引有序性而进行动态调整

什么时候适用索引

• 字段有唯一限制的，例如手机号码、身份证件
• 经常要用于 Where 查询的字段
• 经常用于 Order By 和 Group By 的字段，这样查询时就不需要再去做一次排序了

什么时候不需要索引

• Where、Group By、Order By 中用不到的字段。
• 存在大量重复数据、区分度低的字段。例如性别
• 表中数据太少的时候，一般不需要索引
• 经常更新的字段不用创建索引。例如不要对用户积分、余额等建立索引。每次索引字段的变动都会导致 B+ Tree 动态调整，这个过程会影像数据库性能

索引优化方法

前缀索引优化

使用前缀索引可以减小索引字段的大小，可以增加一个索引页中存储的索引值，提高查询速度。但有一定的局限性：

• Order By 无法使用前缀索引
• 无法把前桌索引用作覆盖索引

覆盖索引优化

通过覆盖索引可以避免回表的操作

主键索引最好自增

InnoDB 创建主键索引时默认为聚簇索引，数据存放在叶子节点上。同一个叶子节点内部的数据是按照主键顺序存放的，因此每次有新数据插入时，数据库会根据主键将其插入对应的叶子节点中

如果我们使用自增主键，那么每次插入的新数据就会按顺序添加到当前索引节点的位置，不需要移动已有数据，因为每次插入都是追加操作。当页面写满，就会自动开辟一个新页面，效率非常高

如果使用非自增主键，每次插入的索引值是随机的，因此插入数据时，可能会插入到现有的数据页中间的某个位置。这就不得不移动其他数据来满足新数据的插入，甚至需要从一个页面复制数据到另一个页面。我们通常把这种情况称为「页分裂」。也分裂还可能会造成大量的内存碎片，导致索引结构不紧凑，从而影响查询效率

因此，如果没有特殊的业务需求，都建议使用自增字段作为主键

另外，主键字段的长度不建议太大，因为主键字段长度越小，意味着二级索引的叶子节点越小，这样二级索引占用的空间也越小

索引字段最好 NOT NULL

• 索引列存在 NULL 值时会导致优化器在做索引选择的时候更加复杂，更加难以优化。因为可为 NULL 的列会使索引、索引统计和值比较都更复杂。例如进行索引统计时，count 会省略值为 NULL 的行
• NULL 是一个无意义值，但它实际会占用物理空间。在 Innodb 中，如果表中存在允许为 NULL 的字段，那么行格式中至少会用 1 字节的空间存储 NULL 值列表

防止索引失效

SQL 语句中使用了索引字段，并不意味着查询的时候会用到索引

左侧存在模糊匹配时

like %xx 或者 like %xx% 这两种查询都会造成索引失效。因为 B+ Tree 是按照索引值来有序排列存储的，只能按照前缀进行比较。因此如果左侧无法确认，则无法使用索引

对索引列使用函数

例如 where length(name) = 6 这样的查询，由于索引存储的是字段原始值，而不是函数计算后的值，因此这个查询无法使用索引

不过在 MySQL 8.0 版本之后，可以选择针对函数计算后的值单独建立一个索引，这样就可以通过扫描索引来查询数据

对索引列进行表达式计算

例如 where id + 1 = 10，与使用函数的情况类似，无法使用计算后的值来扫描索引

对索引列数据隐式类型转换

如果索引字段是字符串类型，但是在条件查询时输入的是整型，则这个查询会走全表扫描

联合索引不符合最左匹配

上文已述

Or 条件中存在非索引字段

在 Where 中，如果 Or 前的条件是索引列，后的不是索引列，那么索引会失效

执行计划解释

• possible_keys 表示可能用到的索引
• key 表示实际用到的索引，如果为 NULL，表示没有使用索引
• key_len 表示索引长度
• rows 表示扫描的数据行数
• type 表示数据扫描类型

执行计划 type

常见扫描类型的执行效率从低到高排序如下：

• ALL 全表扫描
• index 全索引扫描
• range 索引范围扫描
• ref 非唯一索引扫描
• eq_ref 唯一索引扫描
• const 结果只有一条的主键或唯一索引扫描

其中 all 是最坏情况，因为扫描了整张表的数据。

index 和 all 差不多，只不过 index 对索引表进行了全扫描。好处是不再需要对数据排序，但开销依然很大

range 表示使用了索引范围扫描，一般在 Where 中使用 > < in between 等只检索给定范围的行，属于范围查找

ref 表示采用了非唯一索引，或是唯一索引的非唯一前缀，返回的数据可能是多条。

eq_ref 是使用主键或唯一索引时产生的访问方式，通常使用在多表联查中。例如对两张表进行联查，关联条件是两张表的 user_id 相等，且 user_id 是唯一索引，那么使用 explain 查看执行计划时，type 值就会显示 eq_ref

const 类型表示使用了主键或唯一索引与常量值进行了比较，例如 where id = 1

执行计划 extra

• Using filesort：当查询语句中包含 group by 操作，并且无法利用索引完成排序操作的时候，就不得不选择响应的排序算法进行排序，甚至可能会通过文件排序，效率是很低的，要尽力避免
• Using remporary：使用了临时表保存中间结果，MySQL 在对查询结果排序时使用临时表，常见于 Order By 和 Group By。效率比较低，需要避免
• Using index：所需数据在索引中即可获得，不需再回表取数据，也就是使用了覆盖索引，效率不错

总结

参考

• https://xiaolincoding.com/mysql/index/index_interview.html