Mysql 索引原理

1、索引概念

索引是一种有序的存储结构，按照单个或者多个列的值进行排序，提升了搜索的效率。索引就是数据的目录

1.1、使用场景

索引使用场景：快速定位。

• 字段（列）值唯一
• 经常用于 WHERE查询的字段：提升查询速度
• 经常用于 GROUP BY 和 ORDER BY 的字段：建立索引后，记录有序

不使用索引的场景

• 没有 WHERE / GROUP by / ORDER by 的列
• 字段的区分度不高，key 大量重复，索引效率低
• 经常更新的字段：频繁重建索引，降低性能。
• 表数据量少

1.2、索引代价

• 占用空间：存储索引的数据结构
• 维护代价：创建索引和维护索引要耗费时间
• 降低 DML 效率：每次增删改查索引，需要动态维护 B+ 树的索引有序性

2、索引分类

按照不同的划分依据，可以将索引分成不同的类。

2.1、数据结构

按照数据结构分类

• B+ 树索引：叶子节点存放数据（索引 + 记录），非叶子节点只存放索引。
• hash 索引
• Full-Text 索引（全文索引）：工作中通常不会使用 mysql 提供的全文索引，而是使用 elasticsearch。

2.2、物理存储

数据与索引存储的关联性，即索引的存储顺序与数据的存储顺序是否相关。

• 聚集索引（聚簇索引）：叶子节点存储行数据，非叶子节点存储索引指针，索引与数据的存储顺序相关。
• 二级索引（辅助索引）：叶子结点存储的是索引指针，而不是行数据，索引与数据的存储顺序无关。

聚集索引（主键索引）的叶子节点存储数据（主键索引 + 记录），二级索引叶子节点存储主键值。

回表查询 & 覆盖索引

在查询二级索引的时候

• 回表查询：若查询的数据不在二级索引里，就会先检索二级索引，找到对应的叶子节点，获取到主键值后，然后再检索聚集索引。
• 覆盖索引：若查询的数据在二级索引里，不需要回表查询，减少 I/O 操作

因此，在SELECT语句中只列出需要的字段，使用索引覆盖，避免SELECT *的回表查询，增加磁盘 IO 次数

例如：查找索引，直接从辅助索引树获取要查询的数据，using index

EXPLAIN SELECT `id`, `name`, `cid` FROM `covering_index_t` WHERE `name` = '关羽';
1

map  
struct {
	string name;
	int id;
}
1
2
3
4
5

2.3、字段（列）属性

2.3.1、主键索引

建立在主键字段上的索引。非空唯一索引 ，一张表必须有且仅有一个主键。

PRIMARY KEY(key)
1

主键的选择

innoDB 表是组织索引表，主键对应聚集索引 B+ 树，所有的数据都存储其中。

• 若显示设置 PRIMARY KEY，则该设置的 key 为该表的主键
• 若没有显示设置，则从非空唯一索引中选择
  • 有一个非空唯一索引，则选择该索引为主键
  • 有多个非空唯一索引，则选择声明的第一个为主键
• 没有非空唯一索引，则自动生成一个 6 字节的 _rowid 作为主键

2.3.2、唯一索引

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

UNIQUE(key)
1

2.3.2、普通索引

建立在普通字段上的索引，允许出现相同的索引。

INDEX(key) 
KEY(key)
1
2

2.3.3、前缀索引

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

例：选择前缀长度的方法：索引区分度（不重复的索引值和数据表记录总数的比值）。

-- 根据不同的前缀长度的索引区分度，选择区分度最高的前缀
SELECT COUNT(DISTINCT LEFT(`sname`, 2)) / COUNT(*) AS sel2, 
COUNT(DISTINCT LEFT(`sname`, 3)) / COUNT(*) AS sel3,
COUNT(DISTINCT LEFT(`sname`, 4)) / COUNT(*) AS sel4,
COUNT(DISTINCT LEFT(`sname`, 5)) / COUNT(*) AS sel5
FROM `student`;

-- 添加前缀索引
ALTER TABLE `student` ADD KEY(name(4));
1
2
3
4
5
6
7
8
9

2.4、字段（列）个数

• 单列索引：单个字段组成的索引
• 组合索引：多个字段组成的索引

2.4.1、组合索引

* 最左匹配

最左匹配规则：针对组合索引，从左到右依次进行索引的匹配，直到遇到范围查询(<, >, …)就停止匹配。

最左匹配：组合索引 (a, b, ...)是先按照 a 字段的值排序，当 a 的值相等的情况下再按 b 字段的值排序，… 。因此，对于索引 b 来说，当左边字段 a 缺失，组合索引失效；右边字段 c 缺失则没有影响。

-- 针对组合索引 (cid, name)
-- case 1: 匹配成功! 使用组合索引，组合索引从左到右先匹配 cid
EXPLAIN SELECT * FROM `covering_index_t` WHERE `cid` = '1001';

-- case 2: 匹配失败! 组合索引失效，这是因为组合索引先按 cid 排序，cid 相等的情况下再按 name 排序
-- 因此 name 是全局无序，局部相对有序。不遵循最左匹配原则
EXPLAIN SELECT * FROM `covering_index_t` WHERE `name` = '关羽';   

-- case 3: 匹配成功，使用组合索引，编译器自动优化顺序，因此 cid 字段的顺序并不重要
EXPLAIN SELECT * FROM `covering_index_t` WHERE `name` = '关羽' AND `cid` = '1001';
1
2
3
4
5
6
7
8
9
10

范围查询：范围查询字段可以组合索引，其后的字段无法使用组合索引。例如：a > 1 and b = 1，在 a > 1条件的索引记录范围内，b 字段是无序的，联合索引失效。

-- case 4: 范围查询。cid 字段使用组合索引查询，name 字段组合索引失败
-- 因为：在 cid > 1001 条件的索引记录范围内，name 字段是无序的
EXPLAIN SELECT * FROM `covering_index_t` WHERE `cid` > '1001' AND `name` = '关羽';

-- case 5:范围查询。cid, name 字段都使用组合索引查询
-- cid = 1 条件的索引记录范围内 name 字段使用组合索引查询；其他条件下 name 字段组合索引失败
-- 因为：cid = 1 的二级索引记录的范围里，b 字段的值是有序的
EXPLAIN SELECT * FROM `covering_index_t` WHERE `cid` >= '1001' AND `name` = '关羽';
1
2
3
4
5
6
7
8

* 索引下推

对于组合索引 (a, b)，当查询 a > 1 and b = 1的时候，根据最左匹配规则，只有 a 字段能使用索引。对于字段 b 来说，Mysql 5.6 版本前只能回表查询，回主键索引找到数据行，再对比 b 字段的值。Mysql 5.6 版本后支持索引下推，目的是减少回表次数，提升查询效率。

索引下推： 组合索引查询过程中直接过滤掉不满足条件的记录，减少回表次数。

Mysql 架构分为 server 层和存储引擎层

• 无索引下推， server 层向存储引擎层请求数据，在 server 层根据索引条件判断进行数据过滤。
• 有索引下推，将索引条件判断下推到存储引擎层中过滤数据，最终由存储引擎将数据汇总返回给 server 层

例如：查找索引 name，引擎层过滤数据 Using index condition。

EXPLAIN SELECT * FROM `covering_index_t` WHERE `name` = '关羽' AND `cid` > 1;
1

* 索引的区分度

不重复的索引值和数据表记录总数的比值。索引的区分度越高则查询效率越高，区分度高的索引可以在查找的时候过滤掉更多的行。在建立联合索引的时候，把区分度大的字段排在前面。
$$区分度=\frac{distinct(column)}{count(\ast )}$$

3、索引实现

3.1、数据页

记录是按行存储的，数据是按数据页读写的

数据页是 innoDB 磁盘管理的最小单位，默认 16 KB，对应 4 个物理磁盘页。可通过 innoDB_page_size 参数来修改。B+ 树的一个节点的大小就是该数据页的值。

数据页之间通过双向链表的形式组织起来，逻辑上连续，物理上不连续。数据页内包含用户记录，每个记录之间用单向链表的方式组织起来，为了加快在数据页内高效查询记录，设计了一个页目录，页目录存储各个槽（分组），且主键值是有序的，于是可以通过二分查找法的方式进行检索从而提高效率。

3.2、innoDB B+ 树

B+ 树是一种用于实现数据库索引的多路平衡搜索树。

• 减少磁盘 IO 次数（树高）：设计的初衷，对比二叉树
• 范围查询：叶子节点双向链表连接，对比 B 树和哈希。跳表也支持范围查询

面试题：innoDB B+ 树的特点

• 多路平衡搜索树
• 非叶子结点只存储索引信息，叶子节点存储具体数据信息（记录 + 索引）
• 所有的叶子节点都在同一层，且叶子节点间构成一个双向链表（范围查找）
• 非叶子节点只记录索引信息，叶子节点记录数据信息
• 节点的大小都是数据页的大小 (16KB) ，对应 4 个物理磁盘页 (4KB)

在 innoDB 中，B+ 树索引可以分为聚集索引和辅助索引。每个索引都对应着 1 个 B+ 树。

面试题：为什么 MySQL InnoDB 选择 B+ 树作为索引的数据结构？

• vs B 树
  • 查询节点更多：B+ 树只在叶子节点存储数据，而 B 树的非叶子节点也要存储数据，所以 B+ 树的节点数据量更小，在相同的磁盘 I/O 次数下，能查询更多的节点。
  • 范围查询：B +树叶子节点间构成一个双向链表，适合基于范围的顺序查找
• vs 二叉树：减少磁盘 I/O 次数（树高）。B+ 树磁盘 I/O 次数O(logdN)，二叉树磁盘 I/O 次数O(log2N)
• vs 哈希表：范围查询。哈希适合等值查询O(1)，不适合范围查询。

3.3、聚集索引

聚集索引 (clustered index)：按照每张表的主键构造一棵 B+ 树。由于数据页只能按照一棵 B+树排序，因此每张表只能拥有一个聚集索引。

数据页（叶子节点）存放整张表的行记录数据，并通过一个双向链表来链接。非数据页（非叶子节点）仅存放键值和指向数据页的偏移量。

在多数情况下，查询器能够在 B+ 树的叶子节点直接找到数据，优化器倾向于采用聚集索引。此外，由于定义了数据的逻辑顺序，聚集索引能够快速排序查找和范围查找。

聚集索引的数据页类似 C++ 中的 map

例：范围查找聚集索引 primary_key -> (18, 40)

3.4、二级索引

二级索引 (secondary index)，叶子节点不包含行记录的全部数据。叶子节点除了包含键值外，还包含了一个书签 bookmark，该书签存储了相应行数据的聚集索引的键值（主键）。

二级索引 的存在并不影响数据在聚集索引中的组织，因此每张表可以有多个二级索引 。当通过二级索引来寻找数据时，innoDB 引擎会遍历二级索引并通过叶子结点的指针获得指向主键索引的主键，然后通过主键索引来找到一个完整的行记录，也就是回表查询。

二级索引的叶子结点类似 C++ 中的 map ，之后回表查询 map，找到对应的行记录。

例：查找辅助索引 key = 33 的行记录

3.5、innoDB 内存结构

innoDB 存储引擎中，主键是行唯一的标识符，由于行记录的插入顺序是按照主键递增的顺序进行插入的，所以聚集索引（主键索引）的插入是顺序的。数据页的存放是按主键存放顺序，对于非聚集索引叶子节点的插入不再是顺序的，需要离散地访问非聚集索引页。

因此 B+ 树的特性决定了，聚集索引（主键索引）插入的顺序性和非聚集索引插入的离散型。

innoDB 对于非聚集索引的 DML 操作，不是每次直接插入到索引页，而是先判断插入的非聚集索引页（辅助索引页）是否在 buffer pool 中，若存在，则直接插入；若不在，则先放入 change buffer。然后通过定期对 change buffer 和 buffer pool 中辅助索引叶子节点的 merge 操作，将多个插入合并到一个操作（因为在同一非聚集索引页），这样就大大提升了对于非聚集索引插入的性能。

3.5.1、buffer pool

缓存数据页（聚集索引页和 DML 的非聚集索引页），降低磁盘 IO 次数，默认 128M。

通过自适应 hash 索引判断数据页是否在 buffer pool 中：

• 若存在，直接从 buffer pool 取出该数据页
• 若不在，该数据页以 mmap 的方式映射到 free list 标记的 buffer pool 中的空闲缓冲

buffer pool 缓存池通过三个链表来管理

• free list：组织 buffer pool 中未使用的缓冲。
• lru list：组织 buffer pool 中的冷热缓冲，加载数据页到 buffer pool 的同时更新 lru list。热数据前移，冷数据后移。当 buffer pool 需要淘汰缓冲时，移除 lru list 末端尾结点，同时移除该结点对应的 buffer pool 中的数据页。
• flush list：组织 buffer pool 中的脏页。被修改的数据，先修改 buffer pool 中的缓冲，同时 flush list 标识被修改的数据页，等待其他 IO 线程定时异步刷盘。

3.5.2、change buffer

change buffer 用于缓存辅助索引（非唯一）的 DML 数据，数据将会定期异步 merge 到磁盘中。

change buffer 的使用条件

• 辅助索引 (secondary index)
• 非唯一 (unique)

辅助索引不能是唯一的。因为在插入缓冲时，数据库并不会去查找索引页来判断插入记录的唯一性。如果去查找又会有离散读取的情况，那么 change buffer 就失去了意义。

见本节图中的英文注释：change buffer 缓存辅助索引页的数据变更，定期合并到 buffer pool 中的辅助索引叶子节点，再由 buffer pool 定期异步刷盘。

4、* 索引失效

判断：是否需要 for 循环依次比较

• 左模糊匹配：LIKE , %

• 索引参与运算：对索引列做了计算、函数、类型转换等操作

• WHERE子句：or 非索引， in 子查询

例：索引失效

DROP TABLE IF EXISTS `index_failure_t`;
CREATE TABLE `index_failure_t` (
	`id` INT(11) NOT NULL AUTO_INCREMENT,
	`name` VARCHAR(255) DEFAULT NULL,
	`cid` INT(11) DEFAULT NULL,
	`score` SMALLINT DEFAULT 0,
	`phonenumber` VARCHAR(20),
	PRIMARY KEY (`id`),
	KEY `name_idx` (`name`, `cid`), -- 尽量使用联合索引
	KEY `phone_idx` (`cid`)
) ENGINE = innoDB AUTO_INCREMENT=0 DEFAULT CHARSET = utf8;

INSERT INTO `index_failure_t` (`name`, `cid`, `age`, `score`, `phonenumber`) 
VALUES
	('关羽', 1001, 98, '15801100142'),
	('张飞', 1002, 95, '15801101135'),
	('赵云', 1003, 96, '15801100111');

-- 1、左模糊匹配
EXPLAIN SELECT * FROM `index_failure_t` WHERE name LIKE '%云'; -- 索引失效
EXPLAIN SELECT * FROM `index_failure_t` WHERE name LIKE '关%'; -- 右模糊匹配，索引成功

-- 2、索引参与运算
EXPLAIN SELECT * FROM `index_failure_t` WHERE LENGTH(name) = 9; -- 索引失效
EXPLAIN SELECT * FROM `index_failure_t` WHERE `id` + 1 = 3;	    -- 索引失效
EXPLAIN SELECT * FROM `index_failure_t` WHERE `id` = 3 - 1;	    
--  隐式转换：mysql 遇到字符串和数字比较时，会自动将字符串转换为数字
EXPLAIN SELECT * FROM `index_failure_t` WHERE `phonenumber` = 15801100142; -- 索引失效
-- 等价于：EXPLAIN SELECT * FROM `index_failure_t` WHERE CAST(`phonenumber` AS SIGNED INT) = 15801100142; 

-- 3、where: or 非索引 | in 子查询
EXPLAIN SELECT * FROM `index_failure_t` WHERE `id` = '1001' or score = 95; -- 索引失效
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

5、* 索引优化

5.1、索引原则

• 查询频次较高且数据量较大的表建立索引，索引选择使用频次较高，过滤效果好的列或者组合。
• 使用短索引
• 尽量选择区分度高的列作为索引，列的重复值越少越好
• 前缀索引优化：对于很长的动态字符串，减小索引字段大小，提高查询速度。
• 覆盖索引优化：尽量扩展索引，避免回表查询；SELECT尽量只列出需要的字段。
• 主键索引自增：插入新纪录，追加操作，不需要重新移动数据。
• 索引列设置非空
• 防止索引失效

5.2、SQL 优化

找到 sql 语句

• show processlist

• 开启慢查询日志

分析 sql 语句

• 索引 where, group by, order by

• sql 语句： in 优化成联合查询

• 工作当中不要使用 age 字段，存储生日年月日