MySQL索引原理详解

kryiea2024年1月1日

索引

索引是数据的目录
索引和数据存储在存储引擎中

查询优化器可以使用索引来快速定位数据，而不必针对给定查询扫描表中的每一行
但是需要额外的写入和存储来维护索引

索引分类

按「数据结构」分类：B+tree索引、Hash索引、Full-text索引。
按「物理存储」分类：聚簇索引（主键索引）、二级索引（辅助索引）。
按「字段特性」分类：主键索引、唯一索引、普通索引、前缀索引。
按「字段个数」分类：单列索引、联合索引。
每一种存储引擎支持的索引类型不一定相同
MySQL 5.5 后 InnoDB 成为默认存储引擎，同时也支持选择 MyISAM、Memory 等引擎

按数据结构分类

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

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

索引数据结构

索引是提升查询速度的一种数据结构：在插入时对数据进行了排序，当然是会影响插入性能的。
InnoDB 存储引擎支持的索引有：B+树索引、全文索引、R 树索引
重点关注使用最广泛的 B+树索引

B+树索引结构

使用广泛

几乎所有关系型数据库都支持 B+索引，因为在海量数据基于磁盘存储效率足够优秀。

比广泛用于内存的数据结构：二叉树、哈希索引、红黑树、跳表....都优秀

B+树索引特点

基于磁盘的平衡树，但是树非常矮，通常是 3~4 层，能存放千万到上亿的排序数据
树矮，意味着访问效率高，从千万的数据里查询一条数据，只用 3~4 次 IO
容量

B+树组成

根节点：存放索引
中间节点（非叶子节点）：存放索引
叶子节点：存放实际数据（索引+记录）

在 InnoDB 中，B+树有些许变化

B+树的叶子节点之间使用双向链表连接，好处是能能往左往右遍历
B+树每一个节点内容是一个数据页，数据页存放了用户的记录以及各种信息，每个数据页默认大小16KB

B+树索引组织过程

所有 B+树都是从高度为 1 的树开始，随着数据插入，慢慢增加树的高度。
所有的数据在插入时就已经排好序，在叶子节点内用二分查找快速定位数据
随着索引记录变多，一个 16KB 的页无法存放那么多数据，就会发生 B+树的分裂，高度变为 2

随着高度增加，中间节点也会随之增加，其中根节点和中间节点（非叶子节点）存放：**索引键值对（索引键+指针），**两者在 InnoDB 存储引擎中占用 6 个字节索引键：就是排序的列指针：指向下一层的地址

单点查询

B 树单个索引查询最快是 O1，平均而言也会比 B+树稍快
但是 B 树的查询波动大，每个系欸但即存索引又存记录，可能在非叶子节点就能找到索引，有时候又需要到叶子节点才能找到索引
B+树的非叶子节点不存放实际数据，仅仅存放索引，在数据量相同的情况下，相比 B 树，B+树的非叶子节点能存放更多索引。因此 B+树可以比 B 树更加矮胖，磁盘 IO 次数更少

插入、删除效率

结论：B+ 树的插入和删除效率高

删除

B+ 树有大量的冗余节点，这样使得删除一个节点的时候，可以直接从叶子节点中删除，甚至可以不动非叶子节点，这样删除非常快。
删除 B+ 树 0004 节点的过程，因为非叶子节点有 0004 的冗余节点，所以在删除的时候，树形结构变化很小：

删除 B 树 0008 节点的过程，可能会导致树的复杂变化：

删除 B+ 树根节点的过程： B+ 树在删除根节点的时候，由于存在冗余的节点，所以不会发生复杂的树的变形

B 树则不同，B 树没有冗余节点，删除节点的时候非常复杂，比如删除根节点中的数据，可能涉及复杂的树的变形
删除 B 树根节点的过程：

插入

B+ 树的插入也是一样，有冗余节点，插入可能存在节点的分裂（如果节点饱和），但是最多只涉及树的一条路径。

而且 B+ 树会自平衡，不需要像更多复杂的算法，类似红黑树的旋转操作等。

范围查询

B+树所有叶子节点之间有一个链表进行连接，对范围查找非常有帮助

比如：想知道 12 月 1 日和 12 月 12 日之间的订单，这个时候可以先查找到 12 月 1 日所在的叶子节点，然后利用链表向右遍历，直到找到 12 月12 日的节点，这样就不需要从根节点查询了，进一步节省查询需要的时间。

聚集索引和二级索引B+树的区别

InnoDB 根据索引类型不同，分为聚索引和二级索引
表的数据都是存放在聚集索引的叶子节点，所以 InnoDB 引擎一定会为表创建一个聚集索引，只会保存一份，所以聚集索引只能有一个，二级索引能有多个

聚集索引

叶子节点：存放实际数据
所有完整的用户记录都存放在聚集索引的叶子节点

二级索引

叶子节点：存放主键值，不存放实际数据
二级索引 B+树：

回表

回表：如果查询语句使用了二级索引，会先在二级索引的 B+树找到主键值，再去聚集索引 B+树种获得实际数据行。需要查两个 B+树

索引覆盖

只查询 建立主键索引的列或二级索引的列 的数据都可以说是发生了索引覆盖，能在非叶子节点中直接获取数据，不需要再去访问实际的数据行（回表）， 也就是只需要查一个 B+树

核心概念就是通过索引就能满足查询需求，而不需要访问实际的数据行（回表操作）。
如果查询只涉及到建立主键索引或者二级索引的列，数据库引擎可以直接在索引的非叶子节点中获取所需数据，而无需额外的回表操作。
这样的查询过程可以在索引结构中完成，通常是在 B+ 树这样的索引结构中进行。

如果SELECT的列既包含索引列，也包含其他非索引列，那么就要看具体情况是否能实现索引覆盖。

GPT：索引覆盖要求所有查询需要的列都在索引中。如果非索引列也包含在SELECT语句中，数据库引擎可能需要访问实际的数据行来获取非索引列的值，这时就不再是纯粹的索引覆盖。

在某些情况下，数据库引擎可能会通过索引的叶子节点获取非索引列的值，这被称为“覆盖索引”（Covering Index）。覆盖索引是一种特殊的索引覆盖情况，允许通过索引直接满足查询需求，而不必访问实际的数据行。这种情况下，查询的性能仍然会受益于索引的使用。

总的来说，如果查询中包含了索引列和其他非索引列，要关注数据库引擎是否能够通过索引覆盖或者覆盖索引来提高查询性能。这通常取决于具体的数据库系统和查询优化器的实现。

索引存储

数据的 2 种存储方式

堆表
索引组织表（MySQL 使用，说白了就是指 B+树的节点内是数据页，索引即数据，数据即索引）

堆表

堆表中的数据无序存放， 数据的排序完全依赖于索引
都是二级索引，所有的查询都需要回表
Oracle、Microsoft SQL Server、PostgreSQL 早期默认支持的数据存储都是堆表结构

从图中你能看到，堆表的组织结构中，数据和索引分开存储。

索引是排序后的数据，而堆表中的数据是无序的，索引的叶子节点存放了数据在堆表中的地址，当堆表的数据发生改变，且位置发生了变更，所有索引中的地址都要更新，这非常影响性能

索引组织表

MySQL InnoDB 存储引擎就是这样的数据组织方式
Oracle、Microsoft SQL Server 后期也推出了支持索引组织表的存储方式。
据根据主键排序存放在索引中，主键索引也叫聚集索引（Clustered Index）。
在索引组织表中，数据即索引，索引即数据。

聚集索引

不需要回表

二级索引

优点：若行数据发生了变化，其他索引无需进行维护，除非主键发生了增删修改
麻烦：需要回表（二级索引通过主键索引进行再一次查询）

在“数据即索引，索引即数据”之上理解二级索引

二级索引：name。查询 name 的过程拆解

SELECT id FROM idx\_name WHERE name = ?
SELECT \* FROM User WHERE id = \_id; -- 回表

插入数据：可以理解成对主键索引表、二级索引表进行了一个事务操作，要么都成功，要么都不成功

函数索引

联合索引

对回表频率高的查询，建立组合索引，走索引覆盖，减少磁盘 IO

单列索引查询暴露的性能问题

单列查询

前置条件：表只对 class 单列建立索引
查询条件：class = 3
排序条件：score
过程：需要先回表所有数据，建立临时表，依据 score 进行排序

using filesort 对查询性能的影响

对 score 排序，排序是在内存排序，还是外部文件排序，要看排序的数据量是否超过 sort_buffer_size 大小。

**内存排序：**将筛选出来的记录，存放到【内存临时表】，然后根据对应的字段进行【快速排序】
外部文件排序：内存放不下时，会把一部分排序的结果放在磁盘上，空出内存空间，继续排序，所以外部排序一般使用【归并排序】。可以这么简单理解，MySQL 将需要排序的数据分成 12 份，每一份单独排序后存在这些临时文件中，然后把这 12 个有序文件再合并成一个有序的大文件。

优化：建立联合索引

建立联合索引（class, score）

对表建立联合索引之后，执行计划如下：

能在联合索引 B+树中走索引覆盖（减少了回表），而且 score 字段还有局部排序（减轻了排序性能消耗）

联合索引最左匹配原则

原则

规则 1：MySQL 会从联合索引从最左边的索引列开始匹配查询条件，然后依次从从左到右的顺序匹配，如果查询条件没有使用到某个列，那么该列右边的所有列都无法使用走索引。
规则 2：当查询条件中使用了某个列，但是该列的值包含范围查询，范围查询的字段可以用到联合索引，但是在范围查询字段的后面的字段无法用到联合索引

规则 1

规则 2

联合索引（class，scroe） 
select \* from test where class > 2 and score = 80 
// class 能走索索引，score 不能走索引

B+树：

Class > 2 查询得到的记录：

可以看到，score 的记录并不是有序的，所以 score 无法走联合索引

--> 索引一定是有序的列

索引下推

没有索引下推的查询过程

有索引下推的查询过程

索引下推的优化

索引下推在 mysql 5.6 的优化机制，默认开启
如果条件判断字段在二级索引 B+树中，就会下推到 InnoDB 存储引擎层来过滤，过滤完的记录才会回表，相比没有索引下推，减少了回表次数

判断联合索引字段能不能走索引

联合索引（a,b,c），下面的查询语句会不会走索引？如果走具体是哪些字段能走？

select * from T where a=1 and b=2 and c=3;
select * from T where a=1 and b>2 and c=3;
select * from T where c=1 and a=2 and b=3;
select * from T where a=2 and c=3;
select * from T where b=2 and c=3;
select (a,b) from T where a=1 and b>2

答案：

遵循最左匹配原则，所以 abc 三个字段都可以走索引，查询方式是在联合索引找到主键值后，会回主键索引找完整的数据行。
根据最左匹配原则，范围查询后面的字段无法使用索引，所以 ab 可以走索引，c 无法走索引，不过 c 可以进行索引下推。
abc都能走索引，因为 where 查询条件字段的顺序并不会影响，MySQL 优化器会帮我们调整字段的查询顺序，所以也是符合最左匹配原则的。
a 能走索引，根据最左匹配原则，c 无法走索引，但是 c 可以被索引下推
根据最左匹配原则，bc都无法走索引。
a 和 b 都能走索引，查询方式是覆盖查询（索引覆盖），不需要回表

where a>1 and b = 2 and c <3怎么建立索引？

创建(abc)、(acb)、(ab)、(ac)联合索引，只有 a 能索引
创建(cab)、(cba)、(ca)、(cb)联合索引，只有 c 能索引
创建(ba)联合索引，b 和 a 都能走索引
创建(bc)联合索引，b 和 c 都能走索引
创建 (bac) 联合索引，b 和 a 都能走索引，但比 (ba)联合索引多了一个好处，c 字段能索引下推，会减少回表的次数；
创建 (bca) 联合索引，b 和 c 都能走索引，但比 (bc)联合索引多了一个好处，a 字段能索引下推，会减少回表的次数；

where a>100 and b=100 and c=123 order by d 怎么建立联合索引？

如果是 bcad 联合索引的话，虽然 bca 能走索引，但是排序 d 无法利用索引（因为 a 范围查询了，而 d 是局部有序性），会发生 file sort。不过起码能索引下推。。
如果 bcda 联合索引，d 不仅能利用索引有序性（全局有序性，因为范围查询 a 排在最右边），避免 file sort，a 虽然都不了索引，但是可以索引下推，所以建立(bcda)联合索引会比较好。

select * from t where a > 1 and b = 100 or c = 99 怎么优化？

前置知识：联合索引用了 or，索引就会失效。or 左右两边都是独立索引才能走索引。
优化：建立（b，a）联合索引 + c 单列索引

索引失效

索引失效会导致全表扫描

对索引使用左/左右模糊匹配

当使用左、左右模糊匹配会导致索引失效：like %xx、like %xx%
右模糊匹配不会导致索引失效：like x%

因为索引 B+树，是按照索引值有序排列存储的，只能根据前缀进行比较

name like '%好'vsname like '好%'

name like '%好' ：因为查询的结果可能是「你好、不好、很好」等之类的，所以不知道从哪个索引值开始比较，于是就只能通过全表扫描的方式来查询
name like '好%'：第一个字“好”已经确定，能与其他索引比较拼音大小，进而不会导致索引失效

对索引使用函数

索引保存的是索引字段的原始值，而不是经过函数计算后的值，自然没法走索引

怎么优化

建立一个函数索引

对索引进行表达式计算

索引保存的是索引字段的原始值，而不是经过 id + 1 计算后的值，自然没法走索引

explain select \* from t\_user where id + 1 = 10;

优化

改成 id = 10 - 1，就可以走索引了

又不是很优化

在对索引进行简单的表达式计算，在特殊处理后，可以做到索引扫描，但是 mysql 没有主动实现，只能是用户自行处理。

可能原因：表达式计算的情况多种多样，每种都考虑的话，代码可能臃肿。。

对索引隐式类型转换

索引字段是字符串类型，在条件查询中，输入的是整型，会走全表扫描
索引字段是整型，在条件查询中，输入的是字符串类型，会走索引

MySQL 数据类型转换规则

遇到字符串和数字比较时，会自动把字符串转为数字，然后在进行比较

例子：select “10” > 9

如果规则是 MySQL 会将自动「字符串」转换成「数字」，就相当于 select 10 > 9，这个就是数字比较，所以结果应该是 1；
如果规则是 MySQL 会将自动「数字」转换成「字符串」，就相当于 select "10" > "9"，这个是字符串比较，字符串比较大小是逐位从高位到低位逐个比较（按ascii码）那么"10"字符串相当于 “1”和“0”字符的组合，所以先是拿 “1” 字符和 “9” 字符比较，因为 “1” 字符比 “9” 字符小，所以结果应该是 0。

结果：

转换的过程是使用了函数

既然是使用函数，自然会索引失效

相当于：

select \* from t\_user where CAST(phone AS signed int) = 1300000001;

联合索引非最左匹配

联合索引的最左匹配原则

对主键字段建立的索引叫做聚簇索引，对普通字段建立的索引叫做二级索引。

那么多个普通字段组合在一起创建的索引就叫做联合索引，也叫组合索引。

创建联合索引时，我们需要注意创建时的顺序问题，因为联合索引 (a, b, c) 和 (c, b, a) 在使用的时候会存在差别。

联合索引要能正确使用需要遵循最左匹配原则，也就是按照最左优先的方式进行索引的匹配。

比如，如果创建了一个 (a, b, c) 联合索引，如果查询条件是以下这几种，就可以匹配上联合索引：

where a=1；
where a=1 and b=2 and c=3；
where a=1 and b=2；

需要注意的是，因为有查询优化器，所以 a 字段在 where 子句的顺序并不重要。

但是，如果查询条件是以下这几种，因为不符合最左匹配原则，所以就无法匹配上联合索引，联合索引就会失效:

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

索引截断

有一个比较特殊的查询条件：where a = 1 and c = 3 ，符合最左匹配吗？

这种其实严格意义上来说是属于索引截断，不同版本处理方式也不一样。

MySQL 5.5 的话，前面 a 会走索引，在联合索引找到主键值后，开始回表，到主键索引读取数据行，Server 层从存储引擎层获取到数据行后，然后在 Server 层再比对 c 字段的值。

索引下推

从 MySQL 5.6 之后，有一个索引下推功能，可以在存储引擎层进行索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，再返还给 Server 层，从而减少回表次数。

索引下推的大概原理是：截断的字段不会在 Server 层进行条件判断，而是会被下推到「存储引擎层」进行条件判断（因为 c 字段的值是在 (a, b, c) 联合索引里的），然后过滤出符合条件的数据后再返回给 Server 层。由于在引擎层就过滤掉大量的数据，无需再回表读取数据来进行判断，减少回表次数，从而提升了性能。

比如下面这条 where a = 1 and c = 0 语句，我们可以从执行计划中的 Extra=Using index condition 使用了索引下推功能。

为什么联合索引不遵循最左匹配原则就会失效？

原因是，在联合索引的情况下，数据是按照索引第一列排序，第一列数据相同时才会按照第二列排序。

也就是说，如果我们想使用联合索引中尽可能多的列，查询条件中的各个列必须是联合索引中从最左边开始连续的列。如果我们仅仅按照第二列搜索，肯定无法走索引。

where 子句的 or

在 WHERE 子句中，如果在 OR 前的条件列是索引列，而在 OR 后的条件列不是索引列，那么索引会失效。

举个例子，比如下面的查询语句，id 是主键，age 是普通列，从执行计划的结果看，是走了全表扫描。

select \* from t\_user where id = 1 or age = 18;

这是因为 OR 的含义就是两个只要满足一个即可，因此只有一个条件列是索引列是没有意义的，只要有条件列不是索引列，就会进行全表扫描。

要解决办法很简单，将 age 字段设置为索引即可。

可以看到 type=index merge， index merge 的意思就是对 id 和 age 分别进行了扫描，然后将这两个结果集进行了合并，这样做的好处就是避免了全表扫描。

索引选择

如何选择索引 - 优化器

确定执行计划

B+树只是一种存储的数据结构，具体怎么使用，还要依赖数据库的优化器，优化器决定了具体的索引选择，生成执行计划。

CBO：基于成本的优化器

nysql 的优化器的选择基于成本 cost，哪个索引的成本的成本越低，优先使用哪个。

Cost = Server Cost + Engine Cost = CPU Cost + IO Cost

Server：负责 sql 语句的执行过程

Engine：负责具体的存储数据

记录成本的表

server_cost
engine_cost

具体内容

含义

**表 server_cost：**记录了 Server 层优化器各种操作的成本，这里面包括了所有 CPU Cost，其具体含义如下：

disk_temptable_create_cost：创建磁盘临时表的成本，默认为20。
disk_temptable_row_cost：磁盘临时表中每条记录的成本，默认为0.5。
key_compare_cost：索引键值比较的成本，默认为0.05，成本最小。
memory_temptable_create_cost：创建内存临时表的成本：默认为1。
memory_temptable_row_cost：内存临时表中每条记录的成本，默认为0.1。
row_evaluate_cost：记录间的比较成本，默认为0.1。

**表 engine_cost：**记录了存储引擎层各种操作的成本，这里包含了所有的 IO Cost，具体含义如下：

io_block_read_cost：从磁盘读取一个页的成本，默认值为1。
memory_block_read_cost：从内存读取一个页的成本，默认值为0.25

也就是说， MySQL 优化器认为从磁盘读取的开销是内存开销的 4 倍。

索引应用

索引优劣分析

优势

整个数据库中，数据表的查询速度直线提升，数据量越大时效果越明显。
通过创建唯一索引，可以确保数据表中的数据唯一性，无需额外建立唯一约束。
在使用分组和排序时，同样可以显著减少SQL查询的分组和排序的时间。
连表查询时，基于主外键字段上建立索引，可以带来十分明显的性能提升。
索引默认是B+Tree有序结构，基于索引字段做范围查询时，效率会明显提高。
从MySQL整体架构而言，减少了查询SQL的执行时间，提高了数据库整体吞吐量。

劣势

建立索引会生成本地磁盘文件，需要额外的空间存储索引数据，磁盘占用率会变高。
写入数据时，需要额外维护索引结构，增、删、改数据时，都需要额外操作索引。
写入数据时维护索引需要额外的时间开销，执行写SQL时效率会降低，性能会下降

索引陷阱

主键索引陷阱

陷阱：uuid 作为主键

理解：uuid 能保证全局 id 唯一性，但是 B+树有序的，uuid 确实无序的随机值， uuid 会导致每次插入都需要调整树结构

联合索引陷阱

陷阱：索引截断

理解：违反联合索引最左前缀原则

前缀索引陷阱

特点：是短小精悍，我们可以利用一个字段的前N个字符创建索引，以这种形式创建的索引也被称之为前缀索引，相较于使用一个完整字段创建索引，前缀索引能够更加节省存储空间，当数据越多时，带来的优势越明显

陷阱：没存储字段的完整值，无法使用分组、排序等 sql

全文索引陷阱

特点：性能比like%快 n 倍

陷阱：

由于全文索引是基于分词实现的，所以对一个字段建立全文索引后，MySQL会对该字段做分词处理，这些分词结果也会被存储在全文索引中，因此全文索引的文件会额外的大
由于全文索引对每个字段值都会做分词，因此当修改字段值后，分词是需要时间的，所以修改字段数据后不会立马自动更新全文索引，此时需要自行写存储过程，并调用它手动更新全文索引中的数据。
全文索引最大的硬伤在于对中文支持不够友好，类似于英文可以直接通过符号、空格来分词，但中文呢？一个词语来形容就是博大精深，无法精准的对一段文字做分词，因此全文索引在检索中文时，存在些许精准度问题。

解决：项目规模大，可用尝试引入 Elastic Search、Solr、MeiliSearch 等搜索引擎

唯一索引陷阱

唯一索引查询数据时，会比普通索引快上一截，但插入数据时就不同了，因为要确保数据不重复，所以插入前会检查一遍表中是否存在相同的数据。但普通索引则不需要考虑这个问题，因此普通索引的数据插入会快一些。

哈希索引陷阱

哈希结构的致命问题在于无序，也就是无法基于哈希索引的字段做排序、分组等工作。

索引建立原则

表中哪个字段建立一个索引能带来最大的性能收益？

经常频繁用作查询条件的字段应酌情考虑为其创建索引。
表的主外键或连表字段，必须建立索引，因为能很大程度提升连表查询的性能。
建立索引的字段，一般值的区分性要足够高，这样才能提高索引的检索效率。
建立索引的字段，值不应该过长，如果较长的字段要建立索引，可以选择前缀索引。
建立联合索引，应当遵循最左前缀原则，将多个字段之间按优先级顺序组合。
经常根据范围取值、排序、分组的字段应建立索引，因为索引有序，能加快排序时间。
对于唯一索引，如果确认不会利用该字段排序，那可以将结构改为Hash结构。
尽量使用联合索引代替单值索引，联合索引比多个单值索引查询效率要高。