Mysql 索引
Mysql 索引
索引是提高 MySQL 查询性能的一个重要途径,但过多的索引可能会导致过高的磁盘使用率以及过高的内存占用,从而影响应用程序的整体性能。应当尽量避免事后才想起添加索引,因为事后可能需要监控大量的 SQL 才能定位到问题所在,而且添加索引的时间肯定是远大于初始添加索引所需要的时间,可见索引的添加也是非常有技术含量的。
接下来将向你展示一系列创建高性能索引的策略,以及每条策略其背后的工作原理。但在此之前,先了解与索引相关的一些算法和数据结构,将有助于更好的理解后文的内容。
索引简介
“索引”是数据库为了提高查找效率的一种数据结构。
日常生活中,我们可以通过检索目录,来快速定位书本中的内容。索引和数据表,就好比目录和书,想要高效查询数据表,索引至关重要。在数据量小且负载较低时,不恰当的索引对于性能的影响可能还不明显;但随着数据量逐渐增大,性能则会急剧下降。因此,设置合理的索引是数据库查询性能优化的最有效手段。
索引的优缺点
B 树是最常见的索引,按照顺序存储数据,所以 Mysql 可以用来做 ORDER BY
和 GROUP BY
操作。因为数据是有序的,所以 B 树也就会将相关的列值都存储在一起。最后,因为索引中存储了实际的列值,所以某些查询只使用索引就能够完成全部查询。
✔️️️️ 索引的优点:
- 索引大大减少了服务器需要扫描的数据量,从而加快检索速度。
- 索引可以帮助服务器避免排序和临时表。
- 索引可以将随机 I/O 变为顺序 I/O。
- 支持行级锁的数据库,如 InnoDB 会在访问行的时候加锁。使用索引可以减少访问的行数,从而减少锁的竞争,提高并发。
- 唯一索引可以确保每一行数据的唯一性,通过使用索引,可以在查询的过程中使用优化隐藏器,提高系统的性能。
❌ 索引的缺点:
- 创建和维护索引要耗费时间,这会随着数据量的增加而增加。
- 索引需要占用额外的物理空间,除了数据表占数据空间之外,每一个索引还要占一定的物理空间,如果要建立组合索引那么需要的空间就会更大。
- 写操作(
INSERT
/UPDATE
/DELETE
)时很可能需要更新索引,导致数据库的写操作性能降低。
基于以上,可以归纳出索引的基本使用规则:
- 索引不是越多越好,不要为所有列都创建索引
- 要尽量避免冗余和重复索引
- 要考虑删除未使用的索引
- 尽量的扩展索引,不要新建索引
- 频繁作为
WHERE
过滤条件的列应该考虑添加索引
何时使用索引
✔️️️️ 什么情况适用索引?
- 字段的数值有唯一性的限制,如用户名。
- 频繁作为
WHERE
条件或JOIN
条件的字段,尤其在数据表大的情况下 - 频繁用于
GROUP BY
或ORDER BY
的字段。将该字段作为索引,查询时就无需再排序了,因为 B+ 树 - DISTINCT 字段需要创建索引。
❌ 什么情况不适用索引?
- 频繁写操作(
INSERT
/UPDATE
/DELETE
),也就意味着需要更新索引。 - 很少作为
WHERE
条件或JOIN
条件的字段,也就意味着索引会经常无法命中,没有意义,还增加空间开销。 - 非常小的表,对于非常小的表,大部分情况下简单的全表扫描更高效。
- 特大型的表,建立和使用索引的代价将随之增长。可以考虑使用分区技术或 Nosql。
索引的数据结构
在 Mysql 中,索引是在存储引擎层而不是服务器层实现的,所以,并没有统一的索引标准。不同存储引擎的索引的数据结构也不相同。下面是 Mysql 常用存储引擎对一些主要索引数据结构的支持:
索引数据结构/存储引擎 | InnoDB 引擎 | MyISAM 引擎 | Memory 引擎 |
---|---|---|---|
B+Tree 索引 | ✔️️️️️ | ✔️️️️️ | ✔️️️️️ |
Hash 索引 | ❌ | ❌ | ✔️️️️️ |
Full Text 索引 | ✔️️️️️ | ✔️️️️️ | ❌ |
下面,我们将逐一探讨各种可能作为索引的数据结构,了解其特性、利弊、应用场景。相信通过这样的对比,可以让读者更加明确 Mysql 中为什么选择某些数据结构作为索引,而放弃了另外一些数据结构,依据是什么。
有序数组
“数组”用连续的内存空间来存储数据,并且支持随机访问。
有序数组可以使用二分查找法,其时间复杂度为 O(log n)
,无论是等值查询还是范围查询,都非常高效。
但有序数组有两个重要限制:
- 数组的空间大小固定,如果要扩容只能采用复制数组的方式,比较低效。
- 插入、删除操作开销较大,时间复杂度为
O(n)
(要保证数组有序)。
这意味着,如果直接使用有序数组作为索引,为了保证数组有序,其更新操作代价高昂。正因为如此,几乎没有数据库会采用有序数组作为索引。
哈希索引
哈希表是一种以键 - 值(key-value)对形式存储数据的结构,我们只要输入待查找的值即 key,就可以找到其对应的值即 Value。
“哈希表”使用哈希函数组织数据,以支持快速插入和搜索的数据结构。哈希表的本质是一个数组,其思路是:使用哈希函数将 Key 转换为数组下标,利用数组的随机访问特性,使得我们能在 O(1)
的时间代价内完成检索。
有两种不同类型的哈希表:哈希集合 和 哈希映射。
- 哈希集合是集合数据结构的实现之一,用于存储非重复值。
- 哈希映射是映射数据结构的实现之一,用于存储键值对。
哈希索引基于哈希表实现,只适用于等值查询。对于每一行数据,哈希索引都会将所有的索引列计算一个哈希码(hashcode
),哈希码是一个较小的值。哈希索引将所有的哈希码存储在索引中,同时在哈希表中保存指向每个数据行的指针。
在 Mysql 中,只有 Memory 存储引擎显示支持哈希索引。
✔️️️️️ 哈希索引的优点:
- 因为索引数据结构紧凑,所以查询速度非常快。
❌ 哈希索引的缺点:
- 只支持等值比较查询 - 包括
=
、IN()
、<=>
。- 不支持范围查询,如
WHERE price > 100
。 - 不支持模糊查询,如
%
开头。
- 不支持范围查询,如
- 无法用于排序 - 因为 Hash 索引指向的数据是无序的,因此无法起到排序优化的作用。
- 不支持联合索引的最左侧原则 - 对于联合索引来说,Hash 索引在计算 Hash 值的时候是将索引键合并后再一起计算 Hash 值,所以不会针对每个索引单独计算 Hash 值。因此如果用到联合索引的一个或者几个索引时,联合索引无法被利用。例如:在数据列 (A,B) 上建立哈希索引,如果查询只有数据列 A,无法使用该索引。
- 不能用索引中的值来避免读取行 - 因为哈希索引只包含哈希值和行指针,不存储字段,所以不能使用索引中的值来避免读取行。不过,访问内存中的行的速度很快,所以大部分情况下这一点对性能影响不大。
- 哈希索引有可能出现哈希冲突
- 出现哈希冲突时,必须遍历链表中所有的行指针,逐行比较,直到找到符合条件的行。
- 如果哈希冲突多的话,维护索引的代价会很高。
提示:因为种种限制,所以哈希索引只适用于特定的场合。而一旦使用哈希索引,则它带来的性能提升会非常显著。
B+ 树索引
B 树是最常见的索引,按照顺序存储数据,所以 Mysql 可以用来做 ORDER BY
和 GROUP BY
操作。因为数据是有序的,所以 B 树也就会将相关的列值都存储在一起。最后,因为索引中存储了实际的列值,所以某些查询只使用索引就能够完成全部查询。
通常我们所说的索引是指 B-Tree 索引,它是目前关系型数据库中查找数据最为常用和有效的索引,大多数存储引擎都支持这种索引。使用 B-Tree 这个术语,是因为 MySQL 在CREATE TABLE
或其它语句中使用了这个关键字,但实际上不同的存储引擎可能使用不同的数据结构,比如 InnoDB 就是使用的 B+Tree。
B+Tree 中的 B 是指balance
,意为平衡。需要注意的是,B+树索引并不能找到一个给定键值的具体行,它找到的只是被查找数据行所在的页,接着数据库会把页读入到内存,再在内存中进行查找,最后得到要查找的数据。
二叉搜索树
二叉搜索树的特点是:每个节点的左儿子小于父节点,父节点又小于右儿子。其查询时间复杂度是 $$O(log(N))$$。
当然为了维持 $$O(log(N))$$ 的查询复杂度,你就需要保持这棵树是平衡二叉树。为了做这个保证,更新的时间复杂度也是 $$O(log(N))$$。
随着数据库中数据的增加,索引本身大小随之增加,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘 I/O 消耗,相对于内存存取,I/O 存取的消耗要高几个数量级。可以想象一下一棵几百万节点的二叉树的深度是多少?如果将这么大深度的一颗二叉树放磁盘上,每读取一个节点,需要一次磁盘的 I/O 读取,整个查找的耗时显然是不能够接受的。那么如何减少查找过程中的 I/O 存取次数?
一种行之有效的解决方法是减少树的深度,将二叉树变为 N 叉树(多路搜索树),而 B+ 树就是一种多路搜索树。
B+ 树
B+ 树索引适用于全键值查找、键值范围查找和键前缀查找,其中键前缀查找只适用于最左前缀查找。
理解 B+Tree 时,只需要理解其最重要的两个特征即可:
- 第一,所有的关键字(可以理解为数据)都存储在叶子节点,非叶子节点并不存储真正的数据,所有记录节点都是按键值大小顺序存放在同一层叶子节点上。
- 其次,所有的叶子节点由指针连接。如下图为简化了的 B+Tree。
聚簇索引和非聚簇索引
根据叶子节点的内容,索引类型分为主键索引和非主键索引。
- 主键索引又被称为“聚簇索引(clustered index)”,其叶子节点存的是整行数据。
- 聚簇表示数据行和相邻的键值紧凑地存储在一起,因为数据紧凑,所以访问快。
- 因为无法同时把数据行存放在两个不同的地方,所以一个表只能有一个聚簇索引。
- InnoDB 的聚簇索引实际是在同一个结构中保存了 B 树的索引和数据行。
- 非主键索引又被称为“二级索引(secondary index)”,其叶子节点存的是主键的值。数据存储在一个位置,索引存储在另一个位置,索引中包含指向数据存储位置的指针。可以有多个,小于 249 个。
聚簇索引和非聚簇索引的查询有什么区别
- 如果语句是
select * from T where ID=500
,即聚簇索引查询方式,则只需要搜索主键(ID)索引树; - 如果语句是
select * from T where k=5
,即非聚簇索引查询方式,则需要先搜索 k 索引树,得到 ID 的值为 500,再到 ID 索引树搜索一次。这个过程称为回表。
也就是说,基于非聚簇索引的查询需要多扫描一棵索引树。因此,我们在应用中应该尽量使用主键查询。
显然,主键长度越小,非聚簇索引的叶子节点就越小,非聚簇索引占用的空间也就越小。
在创建表时,InnoDB 存储引擎会根据不同的场景选择不同的列作为索引:
- 如果有主键,默认会使用主键作为聚簇索引的索引键(key);
- 如果没有主键,就选择第一个不包含 NULL 值的唯一列作为聚簇索引的索引键(key);
- 在上面两个都没有的情况下,InnoDB 将自动生成一个隐式自增 id 列作为聚簇索引的索引键(key);
自增主键是指自增列上定义的主键,在建表语句中一般是这么定义的: NOT NULL PRIMARY KEY AUTO_INCREMENT
。从性能和存储空间方面考量,自增主键往往是更合理的选择。有没有什么场景适合用业务字段直接做主键的呢?还是有的。比如,有些业务的场景需求是这样的:
- 只有一个索引;
- 该索引必须是唯一索引。
由于没有其他索引,所以也就不用考虑其他索引的叶子节点大小的问题。
这时候我们就要优先考虑上一段提到的“尽量使用主键查询”原则,直接将这个索引设置为主键,可以避免每次查询需要搜索两棵树。
全文索引
MyISAM 存储引擎支持全文索引,用于查找文本中的关键词,而不是直接比较是否相等。查找条件使用 MATCH AGAINST,而不是普通的 WHERE。
全文索引一般使用倒排索引实现,它记录着关键词到其所在文档的映射。
InnoDB 存储引擎在 MySQL 5.6.4 版本中也开始支持全文索引。
全文索引主要用来查找文本中的关键字,而不是直接与索引中的值相比较。
全文索引跟其它索引大不相同,它更像是一个搜索引擎,而不是简单的 WHERE 语句的参数匹配。全文索引配合 match against
操作使用,而不是一般的 WHERE 语句加 LIKE。它可以在 CREATE TABLE
,ALTER TABLE
,CREATE INDEX
使用,不过目前只有 char
、varchar
,text
列上可以创建全文索引。值得一提的是,在数据量较大时候,先将数据放入一个没有全局索引的表中,然后再用 CREATE INDEX
创建全文索引,要比先为一张表建立全文索引然后再将数据写入的速度快很多。
1 | CREATE TABLE `table` ( |
空间数据索引
MyISAM 存储引擎支持空间数据索引(R-Tree),可以用于地理数据存储。空间数据索引会从所有维度来索引数据,可以有效地使用任意维度来进行组合查询。
必须使用 GIS 相关的函数来维护数据。
索引的类型
主流的关系型数据库一般都支持以下索引类型:
主键索引
主键索引:一种特殊的唯一索引,不允许有空值。一个表只能有一个主键(在 InnoDB 中本质上即聚簇索引),一般是在建表的时候同时创建主键索引。
1 | CREATE TABLE `user` ( |
唯一索引
“唯一索引”确保索引中的值是唯一的,不允许有重复值,如果是组合索引,则列值的组合必须唯一。
在 MySQL 中,可以使用 CREATE UNIQUE INDEX
语句来创建唯一索引。
直接创建唯一索引:
1 | CREATE UNIQUE INDEX `uniq_name` ON `user`(`name`); |
创建表时,添加唯一索引示例:
1 | CREATE TABLE `user` ( |
修改表时,添加唯一索引示例:
1 | ALTER TABLE `user` |
普通索引
普通索引是最基本的索引,没有任何限制。
直接创建索引:
1 | CREATE INDEX `idx_name` ON `user`(`name`); |
创建表时,添加索引示例:
1 | CREATE TABLE `user` ( |
修改表时,添加索引示例:
1 | ALTER TABLE `user` |
前缀索引
有时候需要索引很长的字符列,这使得存储索引占用大量空间,且导致查询变慢。这种情况下,可以使用前缀索引。
“前缀索引”是指索引开始的部分字符。对于 BLOB
/TEXT
这种文本类型的列,必须使用前缀索引,因为数据库往往不允许索引这些列的完整长度。
✔️️️️ 前缀索引的优点是:
- 可以大大节约索引空间,从而提高索引效率。
❌ 前缀索引的缺点是:
- 会降低索引的区分度。
- 此外,**
order by
无法使用前缀索引,无法把前缀索引用作覆盖索引**。
使用前缀索引,定义好长度,就可以做到既节省空间,又不用额外增加太多的查询成本。
直接创建前缀索引:
1 | CREATE INDEX `idx_name` ON `user`(`name`(10)); |
创建表时,添加前缀索引示例:
1 | CREATE TABLE `user` ( |
修改表时,添加前缀索引示例:
1 | ALTER TABLE `user` |
那么,如何确定前缀索引合适的长度呢?
可以使用下面这个语句,算出这个列上有多少个不同的值:
1 | select count(distinct email) as L from SUser; |
然后,依次选取不同长度的前缀来看这个值,比如我们要看一下 4~7 个字节的前缀索引,可以用这个语句:
1 | select |
当然,使用前缀索引很可能会损失区分度,所以你需要预先设定一个可以接受的损失比例,比如 5%。然后,在返回的 L4~L7 中,找出不小于 L * 95% 的值,假设这里 L6、L7 都满足,你就可以选择前缀长度为 6。
索引优化策略
索引基本原则
- 索引不是越多越好,不要为所有列都创建索引。要考虑到索引的维护代价、空间占用和查询时回表的代价。索引一定是按需创建的,并且要尽可能确保足够轻量。一旦创建了多字段的联合索引,我们要考虑尽可能利用索引本身完成数据查询,减少回表的成本。
- 要尽量避免冗余和重复索引。
- 要考虑删除未使用的索引。
- 尽量的扩展索引,不要新建索引。
覆盖索引
覆盖索引是指:索引上的信息足够满足查询请求,不需要回表查询数据。
【示例】范围查询
1 | create table T ( |
需要执行几次树的搜索操作,会扫描多少行?
- 在 k 索引树上找到 k=3 的记录,取得 ID = 300;
- 再到 ID 索引树查到 ID=300 对应的 R3;
- 在 k 索引树取下一个值 k=5,取得 ID=500;
- 再回到 ID 索引树查到 ID=500 对应的 R4;
- 在 k 索引树取下一个值 k=6,不满足条件,循环结束。
在这个过程中,回到聚簇索引树搜索的过程,称为“回表”。可以看到,这个查询过程读了 k 索引树的 3 条记录(步骤 1、3 和 5),回表了两次(步骤 2 和 4)。
如果执行的语句是 select ID from T where k between 3 and 5
,这时只需要查 ID 的值,而 ID 的值已经在 k 索引树上了,因此可以直接提供查询结果,不需要回表。索引包含所有需要查询的字段的值,称为覆盖索引。
由于覆盖索引可以减少树的搜索次数,显著提升查询性能,所以使用覆盖索引是一个常用的性能优化手段。
最左匹配原则
不只是索引的全部定义,只要满足最左前缀,就可以利用索引来加速检索。这里的最左,可以是联合索引的最左 N 个字段,也可以是字符串索引的最左 M 个字符。
如果是联合索引,那么 key 也由多个列组成,同时,索引只能用于查找 key 是否存在(相等),遇到范围查询 (>
、<
、BETWEEN
、LIKE
) 就不能进一步匹配了,后续退化为线性查找。因此,列的排列顺序决定了可命中索引的列数。
应该将选择性高的列或基数大的列优先排在多列索引最前列。但有时,也需要考虑 WHERE
子句中的排序、分组和范围条件等因素,这些因素也会对查询性能造成较大影响。
“索引的选择性”是指不重复的索引值和记录总数的比值,最大值为 1,此时每个记录都有唯一的索引与其对应。索引的选择性越高,查询效率越高。如果存在多条命中前缀索引的情况,就需要依次扫描,直到最终找到正确记录。
例如下面显示的结果中 customer_id 的选择性比 staff_id 更高,因此最好把 customer_id 列放在多列索引的前面。
1 | SELECT COUNT(DISTINCT staff_id)/COUNT(*) AS staff_id_selectivity, |
1 | staff_id_selectivity: 0.0001 |
使用索引来排序
Mysql 有两种方式可以生成排序结果:通过排序操作;或者按索引顺序扫描。
索引最好既满足排序,又用于查找行。这样,就可以通过命中覆盖索引直接将结果查出来,也就不再需要排序了。
这样整个查询语句的执行流程就变成了:
- 从索引 (city,name,age) 找到第一个满足 city=’杭州’条件的记录,取出其中的 city、name 和 age 这三个字段的值,作为结果集的一部分直接返回;
- 从索引 (city,name,age) 取下一个记录,同样取出这三个字段的值,作为结果集的一部分直接返回;
- 重复执行步骤 2,直到查到第 1000 条记录,或者是不满足 city=’杭州’条件时循环结束。
= 和 in 可以乱序
不需要考虑 =
、IN
等的顺序,Mysql 会自动优化这些条件的顺序,以匹配尽可能多的索引列。
【示例】如有索引 (a, b, c, d),查询条件 c > 3 and b = 2 and a = 1 and d < 4
与 a = 1 and c > 3 and b = 2 and d < 4
等顺序都是可以的,MySQL 会自动优化为 a = 1 and b = 2 and c > 3 and d < 4,依次命中 a、b、c、d。
索引失效的场景
创建了索引,并非一定有效。比如不满足前缀索引、最左前缀匹配原则、查询条件涉及函数计算等情况都无法使用索引。此外,即使 SQL 本身符合索引的使用条件,MySQL 也会通过评估各种查询方式的代价,来决定是否走索引,以及走哪个索引。
对索引使用左模糊匹配
使用左或者左右模糊匹配的时候,也就是 like %xx
或者 like %xx%
这两种方式都会造成索引失效。这是因为:B+ 树索引是按照“索引值”有序存储的,只能根据前缀进行比较。
对索引使用函数或表达式
查询语句中,如果对索引字段使用“函数”或“表达式”,会导致索引失效。
因为索引树存储的是索引字段的原始值,因此无法索引经过函数计算或表达式计算后的值。
❌ 错误示例:
1 | SELECT actor_id FROM actor WHERE actor_id + 1 = 5; |
对索引隐式类型转换
查询语句中,如果对索引字段进行隐式类型转换,会导致索引失效。由于隐式类型转换是通过 CAST
函数实现的,等同于对索引列使用了函数,所以会导致索引失效。
联合索引不遵循最左匹配原则
联合索引如果不遵循最左匹配原则,就会导致索引失效。原因是,在联合索引的情况下,数据是按照索引第一列排序,第一列数据相同时才会按照第二列排序。
索引列判空
索引列与 NULL
或者 NOT NULL
进行判断的时候也会失效。这是因为索引并不存储空值,所以最好在设计数据表的时候就将字段设置为 NOT NULL
约束,比如你可以将 INT 类型的字段,默认值设置为 0。将字符类型的默认值设置为空字符串 (’’)。
WHERE 子句中的 OR 前后条件存在非索引列
在 WHERE 子句中,如果在 OR 前的条件列是索引列,而在 OR 后的条件列不是索引列,那么索引会失效。
比如下面的 SQL 语句,comment_id 是主键,而 comment_text 没有进行索引,因为 OR 的含义就是两个只要满足一个即可,因此只有一个条件列进行了索引是没有意义的,只要有条件列没有进行索引,就会进行全表扫描,因此索引的条件列也会失效:
1 | EXPLAIN SELECT comment_id, user_id, comment_text FROM product_comment WHERE comment_id = 900001 OR comment_text = '462eed7ac6e791292a79' |
运行结果:
1 | +----+-------------+-----------------+------------+------+---------------+------+---------+------+--------+----------+-------------+ |
如果我们把 comment_text 创建了索引会是怎样的呢?
1 | +----+-------------+-----------------+------------+-------------+----------------------+----------------------+---------+------+------+----------+------------------------------------------------+ |
你能看到这里使用到了 index merge,简单来说 index merge 就是对 comment_id 和 comment_text 分别进行了扫描,然后将这两个结果集进行了合并。这样做的好处就是避免了全表扫描。