xiaolin coding 图解 MySQL笔记——索引篇

1. 什么是索引？

索引是数据的目录，帮助存储引擎快速获取数据的一种数据结构，所谓存储引擎，就是如何存储数据、如何为存储的数据建立索引和如何更新、查询数据等技术的实现方法。

2. 索引的分类

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

按数据结构分类

B+ Tree 索引类型是 MySQL 存储引擎采用最多的索引类型。在创建表时，InnoDB 存储引擎会根据不同的场景选择不同的列作为索引：

• 如果有主键，默认使用主键作为聚簇索引的索引键（key）;
• 如果没有主键，就选择第一个不包含 NULL 值的唯一列作为聚簇索引的索引键；
• 在上面两个都没有的情况下，InnoDB 将自动生成一个隐式自增 id 列作为聚簇索引的索引键；

其他索引都属于辅助索引，也被称为二级索引或非聚簇索引。创建的主键索引和二级索引默认使用的是 B+Tree 索引。

B+Tree 索引的示例

先创建一个商品表，id 为主键：

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
) CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;

B+Tree 是一种多叉树，非叶子节点只存放索引，叶子节点才存放数据，每一个叶子节点都有两个指针，分别指向下一个叶子节点和上一个叶子节点，形成一个双向链表。

比如说这条查询语句select * from product where id=5;，使用了主键索引查询 id 号为 5 的商品，所以会自顶向下逐层进行查找：

• 将 5 与根节点的索引数据（1，10，20）比较，然后找到第二层的索引数据（1，4，7），然后找到（4，5，6）查找最终找到 5。

数据库的索引和数据都是存储在硬盘的，我们可以把读取一个节点当作一次磁盘 I/O 操作。那么上面的整个查询过程一共经历了 3 个节点，也就是进行了 3 次 I/O 操作。

B+Tree 存储千万级的数据只需要 3-4 层高度就可以满足，意味着从千万级的表查询目标数据最多需要 3-4 次磁盘 I/O，所以B+Tree 相比于 B 树和二叉树来说，最大的优势在于查询效率很高，即使在数据量很大的情况，查询一个数据的磁盘 I/O 依然维持在 3-4 次

InnoDB 存储引擎页的大小可以存储大量的键值，所以深度为3的B+Tree索引可以维护海量的数据。

通过二级索引查询商品数据的过程

主键索引的 B+Tree 的叶子节点存放的是实际数据，而二级索引的 B+Tree 的叶子节点存放的是主键值，所以如果使用select * from product where product_no = '0002'来查询商品，会先检索二级索引中的 B+Tree 的索引值（product_no），找到对应的叶子节点，然后获取主键值，再通过主键索引的 B+Tree 树查询到对应的叶子节点，然后获取整行数据。这个过程叫【回表】，也就是说要查两个 B+Tree 才能查到数据。

不过，如果查询的数据是在二级索引的 B+Tree 的叶子节点里就能查询到，就不用再查主键索引，比如select id from product where product_no = '0002';

这种在二级索引的 B+Tree 就能查询到结果的过程就叫做【覆盖索引】，也就是只需要查一个 B+Tree 就能找到数据。

为什么 MySQL innoDB 选择 B+tree 作为索引的数据结构？

1. B+Tree vs B Tree
   B+Tree 只在叶子节点存储数据，而 B 树的非叶子节点也要存储数据，所以 B+Tree 的单个节点的数据量更小，在相同的磁盘 I/O 次数下，就能查询更多的节点。此外，B+Tree 叶子节点采用双链表连接，适合 MySQL 中常见的基于范围的顺序查找，B 树无法做到。B+Tree 叶子节点的双链表使得顺序查找范围查找更加高效，B树就是树结构没有链表结构
2. B+Tree vs 二叉树
   对于有 N 个叶子节点的 B+Tree，其搜索复杂度为$O(lo{g}_{d}N)$`，其中 d 表示节点允许的最大子节点个数为 d 个。而二叉树的搜索复杂度为$O(lo{g}_{2}N)$，这已经比 B+Tree 高出不少。
3. B+Tree vs Hash
   Hash 适合等值查询，搜索复杂度为O(1)，不适合做范围查询。

按物理存储分类

聚簇索引是指数据行的物理存储顺序与索引顺序是相同的，这意味着，索引键值相近的数据行在磁盘上也是相邻存储的，从而实现了数据的聚集，如果表中定义了主键，主键索引的唯一性就是聚簇索引。

辅助索引是指需要回表，也就是二级索引，不需要回表的覆盖索引可以看成提供了聚簇索引的查询性能。

按字段特性分类

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

CREATE TABLE table_name (
	...
	PRIMARY KEY (index_column_1) USING BTREE
)

• 唯一索引，建立在 UNIQUE 字段上的索引，一张表可以有多个唯一索引，索引列的值必须唯一，允许为空。

建表时创建唯一索引
CREATE TABLE table_name (
	...
	UNIQUE KEY(index_column_1,index_column_2,...)
);

建表后创建唯一索引
CREATE UNIQUE INDEX index_name
ON table_name(index_column_1, index_column_2,...);

• 普通索引，建立在普通字段的索引，既不要求字段为主键，也不要求字段为 UNIQUE。

建表时创建普通索引
CREATE TABLE table_name (
	...
	INDEX(index_column_1,index_column_2,...)
);

建表后创建普通索引
CREATE INDEX index_name
ON table_name(index_column_1, index_column_2,...);

• 前缀索引，是指对字符类型字段的前几个字符建立的索引，而不是在整个字段上建立的索引，前缀索引可以建立在字段类型为 char、varchar、binary、varbinary 的列上。使用前缀索引的目的是为了减少索引占用的存储空间，提升查询效率。

建表时创建前缀索引
CREATE TABLE table_name (
	column_list,
	INDEX(column_name(length))
);

建表后创建前缀索引
CREATE INDEX index_name
ON table_name(column_name(length));

按字段个数分类

• 单列索引，建立在单列上的索引
• 联合索引，建立在多列上的索引，比如，将商品表中的 product_no 和 name 字段组合成联合索引(product_no, name)，创建联合索引的方式如下：

CREATE INDEX index_product_no_name ON product(product_no, name);

联合索引的非叶子节点用两个字段的值作为 B+Tree 的 key 值。当在联合索引查询数据时，先按 product_no 字段比较，在 product_no 相同的情况下再按 name 字段比较。

因此，使用联合索引时，存在最左匹配原则，比如如果有 (a, b, c) 的联合索引，那么以下这几种就可以匹配上联合索引：

• where a=1;
• where a=1 and b=2 and c=3;
• where b=2 and a=1（查询优化器使得 a 字段在 where 子句的顺序并不重要）

而以下这几种不符合最左匹配原则，所以无法匹配上联合索引：

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

b 和 c 是全局无序，局部相对有序的，因为联合索引是先按 a 排序，然后依次排序。

联合索引范围查询

联合索引的最左匹配原则会一直向右匹配直到遇到【范围查询】就会停止匹配。也就是范围查询的字段可以用到联合索引，但是在范围查询字段后面的字段无法用到联合索引。

• 比如，select * from t_table where a > 1 and b = 2，联合索引（a, b）是先按照 a 字段的值排序的，所以 a > 1 条件的二级索引记录肯定相邻，用得上索引，但在符合 a > 1 条件的二级索引记录的范围里，b 字段的值是无序的，所以 b = 2 条件用不上索引。

• 而，select * from t_table where a >= 1 and b = 2里，a >= 1 里的 a = 1 里的 b 字段的值有序，所以这条查询语句 a 和 b 字段都用到了联合索引进行索引查询。

• select * from t_table where a between 2 and 8 and b = 2，between 在 mysql 中包含了边界值，相当于 >= 和 <=，所以都用到了联合索引。

• select * from t_user where name like 'j%' and age = 22，虽然在符合前缀 ‘j’ 的 name 字段的二级索引记录的范围， age 是无序的，但是对于符合 name = j 的二级索引记录的范围，age 是有序的，所以都用到了联合索引。
  
  综上所述，联合索引的最左匹配原则在遇到范围匹配的时候，就会停止匹配，在范围查询字段的后面的字段无法用到联合索引，但是，对于 >=，<=，BETWEEN，like 前缀匹配的范围查询，并不会停止匹配。

索引下推

对于联合索引，MySQL 5.6 之前，需要回表，但是在引入索引下推优化后，可以在联合索引遍历过程中，对联合索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数

当查询语句的执行计划里，出现了 Extra 为 Using index condition，说明使用了索引下推的优化。

索引区分度

建立联合索引时的字段顺序对索引效率有很大的影响，要把区分度大的字段排在前面，这样区分度大的字段越有可能被更多的 SQL 使用到。

区分度 = distinct(column) / count(*)

联合索引进行排序

针对这条语句：
select * from order where status = 1 order by create_time asc
给 status 和 create_time 列建立一个联合索引比单独给 status 建立一个索引要好，因为这样可以避免 MySQL 数据库发生文件排序，因为根据 status 筛选后的数据就是按照 create_time 排好序的（降序排列也可以优化）。

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

索引最大的好处是优化查询速度，但是缺点是需要占用物理空间；创建索引和维护索引要耗费时间；会降低表的增删改的效率，因为每次增删改索引，B+树会为了维护索引有序性，都需要进行动态维护。

什么时候适用索引？

• 字段有唯一性限制的，比如商品编码；
• 经常用于 WHERE 查询条件的字段，这样能够提高整个表的查询速度
• 经常用于 GROUP BY 和 ORDER BY 的字段，这样在查询的时候就不需要再做一次排序了。

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

• WHERE 条件，GROUP BY，ORDER BY 里用不到的字段，起不到快速定位的价值；
• 字段中存在大量重复数据，不需要创建索引；
• 表数据太少；
• 经常更新的字段，因为索引字段频繁修改需要维护，会影响数据库性能。

4. 有什么优化索引的方法？

前缀索引优化

减小索引字段大小，但是有一定局限性，例如 order by 无法使用前缀索引，无法把前缀索引用于覆盖索引。

覆盖索引优化

好处是可以直接从二级索引查询中得到记录，不需要通过聚簇索引查询获得，避免回表，比如查询商品的价格、名称时，可以建立联合索引【商品ID、名称、价格】，这样减少了大量的回表 I/O 操作。

主键索引最好是自增的

如果使用自增主键，那么每次插入的新数据就会按顺序添加到当前索引节点的位置，不需要移动已有的数据，每次插入一条新记录，都是追加操作，不需要重新移动数据。

如果使用非自增主键，由于每次插入主键的索引值都是随机的，因此插入主键时，甚至需要从一个页面复制数据到另外一个页面，这被称为页分裂，这可能会造成大量的内存碎片，导致索引结构不紧凑，从而影响查询效率。

索引最好设置为 NOT NULL

索引列存在 NULL 会导致优化器在做索引选择的时候更加复杂，更加难以优化，而且 NULL 值无意义，会占用物理空间。

防止索引失效

发生索引失效的典型场景：

• 使用左或者左右模糊匹配，like%xx或者like %xx%
• 当再查询操作中对索引列做了计算、函数、类型转换
• 联合索引需要遵循最左匹配
• 在 WHERE 子句中，如果在 OR 前的条件列是索引列，而 OR 后的不是，索引会失效。

查看执行计划判断查询语句是否使用了索引

对于执行计划，参数有：

• possible_keys 字段表示可能用到的索引

• key 字段表示实际用的索引

• key_len 表示索引的长度

• rows 表示扫描的数据行数

• type 表示数据扫描类型，描述找到了所需数据时使用的扫描方式是什么，常见的扫描类型的执行效率从低到高的顺序为：

• All（全表扫描）

• index（全索引扫描）

• range（索引范围扫描）

• ref（非唯一索引扫描）

• eq_ref（唯一索引扫描）

• const（结果只有一条的主键或唯一索引扫描），const 是与常量进行比较，查询效率更快，eq_ref 通常用于多表联查，比如关联条件是两张表的 user_id，且 user_id 是唯一索引。

extra 显示的有几个重要的参考指标：

• Using filesort：文件排序，效率是很低的，因此尽量避免这种问题
• Using temporary：使用了临时表保存中间结果
• Using index：使用了覆盖索引，避免了回表操作。