乐趣区

关于mysql:我所理解的MySQL二索引

你好,有幸相见。

从九月开始,我决定发动「每周一博」的指标:每周至多公布一篇博客,能够是各种源码剖析研读,也能够是记录工作中遇到的难题。

在通过了一段时间漫无目的的学习之后,我发现那样用途如同不大,看过的货色过段时间就忘了,而且也没有做什么笔记。

“凡所学,必有所输入。”我认为这才是最适宜我的学习形式,这也是「每周一博」流动的来由,敌人们,如果你也感觉常常会遗记以前看过的货色,一起退出这个流动吧。

本来应该是九月的第五篇博客,最终实现于十月的第一周,同时这也是 MySQL 系列的第二篇。

  • 本文首发于集体博客: javageekers.club
  • 本文收录于集体语雀知识库: 我所了解的后端技术

MySQL 系列的第二篇,次要探讨 MySQL 中对于索引的一些问题,包含索引品种、数据模型、索引执行流程、最左前缀准则、索引生效状况以及索引下推等内容。

最早晓得索引应该是在大二的数据库原理这门课中,当一个查问语句十分慢时,能够通过为某些字段增加索引来 进步查问效率

还有一个十分经典的例子:咱们能够把数据库设想成字典,把索引设想成目录,当咱们借助字典的目录来查问一个字的时候,就能体现出索引的作用了。

1. 索引品种

在 MySQL 中,从索引的逻辑或者说字段个性来辨别,索引大抵分为以下几个品种:一般索引、惟一索引、主键索引、联结索引和前缀索引。

  • 一般索引:最根底的索引,没有任何限度。
  • 惟一索引:索引列的值必须惟一。
  • 主键索引:非凡的惟一索引,作为主键它的值不能为空。
  • 联结索引:联结索引就是索引列为多个字段的一般索引,须要思考 最左前缀准则
  • 前缀索引:对字符类型的前几个字符或二进制类型的前几个字节建设索引。

还有另外一种从物理存储上来辨别的索引分类:聚簇索引和非聚簇索引。

  • 聚簇索引:索引程序与数据存储程序统一,其叶子节点存储的是数据行。
  • 非聚簇索引:非聚簇索引的叶子节点存储的是聚簇索引的值,同时它是基于聚簇索引创立的。

简略来说,所谓的聚簇索引就是索引 key 与数据行在一起,而非聚簇索引的索引 key 对应的值是聚簇索引的值。

2. 索引的数据结构

常见的用于实现索引的数据结构有哈希表、有序数组和搜寻树。

2.1 哈希索引

哈希表是一个以 key-value 模式来存储数据的容器,和 HashMap 一样,哈希索引也会将 key 通过特定的哈希函数计算失去索引值,而后在数组的相应地位寄存 key 对应的 value,如果有两个 key 通过哈希函数计算失去的索引值雷同(产生哈希抵触),那么数组的这个地位就会变成一个链表,寄存所有哈希值雷同的 value。

所以在个别状况下,哈希表进行等值查问的工夫复杂度能够达到 O(1),然而在产生哈希抵触的状况下,还须要额定遍历链表中的所有值,才可能找到符合条件的数据。

另外,思考到通过哈希函数计算失去的索引是不法则的——哈希表心愿所有的 key 可能失去充沛散列,这样能力让 key 均匀分布,不节约空间——即哈希表的 key 是非程序的,所以应用哈希表来进行区间查问时很慢的,排序也是同样的情理。

所以,哈希表仅实用于等值查问。

2.2 有序数组

有序数组顾名思义是一个依照 key 的程序进行排列的数组,它进行等值查问的工夫复杂度应用二分查问能够达到 O(logN),这与哈希表相比逊色不少。

然而通过有序数组进行范畴查问的效率较高:首先通过二分查问找到最小值(或最大值),而后反向遍历,直到另一个边界。

至于排序,有序数组原本就是有序的,人造曾经排好序了,当然排序字段不是索引字段就另说了。

然而有序数组有一个毛病,因为数组元素是间断且有序的,如果此时插入新的数据行,为了维持有序数组的有序性,须要将比此元素 key 大的元素都往后挪动一个单位,给他腾出一个中央插入。而这种保护索引的形式的代价是很大的。

所以,有序数组适宜存储衣服初始化过后就不再更新的数据。

2.3 搜寻树

理解过数据结构的人应该会晓得,搜寻树是一个查问工夫复杂度为 O(logN),更新的工夫复杂度也是 O(logN)的数据结构。所以搜寻树相较于哈希表和有序数组来说兼顾查问与更新两方面。也正是因为这个起因,在 MySQL 中最罕用的数据模型就是搜寻树。

而思考到索引是寄存在磁盘中的,如果搜寻树是一棵二叉树,那么它的子节点只能有左右两个,在数据比价多的状况下,这棵二叉树的树高可能会十分高,当 MySQL 进行查问的时候,可能因为树高导致磁盘 I / O 次数过多,查问效率变慢。

2.4 全文索引

除此之外,还有一种全文索引,它通过建设 倒排索引,解决了判断字段是否蕴含的问题。

倒排索引是用来存储在全文搜寻下某个单词在一个文档或者一组文档中的存储地位的映射,通过倒排索引能够依据单词疾速获取蕴含这个单词的文档列表。

当通过关键词进行检索的时候,全文索引就会派上用场。

3. InnoDB 中的 BTree 索引

3.1 B+ 树

这是一棵比较简单的 B + 树。

图片起源: Data Structure Visualizations

从下面这张示例图也能够看到,这棵 B + 树最上面的叶子节点存储了所有的元素,并且是按顺序存储的,而非叶子节点仅存储索引列的值。

3.2 图解 BTree 索引

在 InnoDB 中,基于 BTree 的索引模型的最为罕用的,上面以一个理论的例子来图解 InnoDB 中 BTree 索引的构造。

CREATE TABLE `user`  (`id` int(11) NOT NULL,
  `name` varchar(36) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  INDEX `nameIndex`(`name`) USING BTREE
) ENGINE = InnoDB;

-- 插入数据
insert into user1(id,name,age) values (1,'one',21),(2,'two',22),(3,'three',23),(4,'four',24),(5,'five',25);

在这张表中只有两个字段:主键 id 和 name 字段,同时建设了一个以 name 字段为索引列的 BTree 索引。

以主键 id 字段的为索引的索引,又叫主键索引,它的索引树结构是:索引树的非叶子阶段寄存的都是主键 id 的值,叶子节点寄存的值是 该主键 id 对应的整个数据行,如下图所示:

也正因为主键索引的叶子节点存储的是该主键 id 对应的整个数据行,主键索引又被称为聚簇索引。

而以 name 字段为列的索引树,非叶子节点寄存的同样是索引列的值,而其叶子阶段寄存的值是 主键 id 的值,如下图所示。

3.3 索引的执行流程

首先来看上面这句 SQL,查问 user 表中 id=1 的数据行。

select * from user where id=1;

这句 SQL 的执行流程很简略,存储引擎会走主键 id 的索引树,当找到 id=1 时,就会把索引树上 id=1 的数据行返回(因为主键值是惟一的,所以找到命中指标就会进行搜寻,间接返回后果集)。

3.3.1 回表

接下来再看应用一般索引进行查问的状况,它的状况与主键索引略有不同。

select * from user where name='one';

下面这句 SQL 查问语句的流程是这样的:首先存储引擎会搜寻一般索引 name 列的索引树,当命中 name 等于 one 的记录后,存储引擎须要通过一个十分重要的步骤:回表

因为一般索引的索引树子节点寄存的是主键值,当查问语句须要查问除主键 id 及索引列之外的其余字段时,须要依据主键 id 的值再回到主键索引树中进行查问,失去主键 id 对应的整个数据行,而后从中获取客户端须要的字段后,才将这一行退出后果集。

随后存储引擎会持续搜寻索引树,直到遇到第一个不满足 name='one' 的记录才会进行搜寻,最初将所有命中的记录返回客户端。

咱们把 依据从一般索引查问到的主键 id 值,再在主键索引中查问整个数据行的过程 称之为回表。

当数据量非常宏大时,回表是一个非常耗时的过程,所以咱们应该尽量避免回表产生,这就引出了下一个问题:应用笼罩索引防止回表。

3.3.2 笼罩索引

不晓得你有没有留神到,在上一个回表的问题中有这样一句形容:“当查问语句须要查问除主键 id 及索引列之外的其余字段时 …”,在这种场景下须要通过回表来获取其余的查问字段。也就是说,如果查问语句须要查问的字段仅有主键 id 和索引列的字段时,是不是就不须要回表了?

上面来剖析一波这个过程,首先建设一个联结索引。

alter table user add index name_age ('name','age');

那么这棵索引树的结构图应该是上面这样:

联结索引索引树的子节点程序是依照申明索引时的字段来排序的,相似于 order by name, age,而它索引对应的值与一般索引一样是主键值。

select name,age from user where name='one';

下面这条 SQL 是查问所有 name='one' 记录的 name 和 age 字段,现实的执行打算应该是搜寻刚刚建设的联结索引。

与一般索引一样,存储引擎会搜寻联结索引,因为联结索引的程序是先依照 name 再依照 age 进行排序的,所以当找到第一个 name 不是 one 的索引时,才会进行搜寻。

而因为 SQL 语句查问的只是 name 和 age 字段,恰好存储引擎命中查问条件时失去的数据正是 name, age 和 id 字段,曾经蕴含了客户端须要的字段了,所以就不须要再回表了。

咱们把 只须要在一棵索引树上就能够失去查问语句所须要的所有字段 的索引成为笼罩索引,笼罩索引毋庸进行回表操作,速度会更快一些,所以咱们在进行 SQL 优化时能够思考应用笼罩索引来优化。

4. 最左前缀准则

下面所举的例子都是应用索引的状况,事实上在我的项目中简单的查问语句中,也可能存在不应用索引的状况。首先咱们要晓得,MySQL 在执行 SQL 语句的时候一张表只会抉择一棵索引树进行搜寻,所以个别在建设索引时须要尽可能笼罩所有的查问条件,建设联结索引。

而对于联结索引,MySQL 会遵循 最左前缀准则:查问条件与联结索引的最左列或最左间断多列统一,那么就能够应用该索引。

为了具体阐明最左前缀准则,同时阐明最左前缀准则的一些非凡状况。

5. 索引生效场景

即使咱们依据最左前缀的准则创立了联结索引,还是会有一些非凡的场景会导致索引生效,上面举例说明。

假如有一张 table 表,它有一个联结索引,索引列为 a,b,c 这三个字段,这三个字段的长度均为 10。

CREATE TABLE `demo`  (`a` varchar(1) DEFAULT NULL,
  `b` varchar(1) DEFAULT NULL,
  `c` varchar(1) DEFAULT NULL,
  INDEX `abc_index`(`a`, `b`, `c`) USING BTREE
) ENGINE = InnoDB;

5.1 全字段匹配

第一种状况是查问条件与索引字段全副统一,并且用的是等值查问,如:

select * from demo where a='1' and b='1' and c='1';
select * from demo where c='1' and a='1' and b='1';

输入上述两条 SQL 的执行打算来看它们应用索引的状况。

mysql> explain select * from demo where a='1' and b='1' and c='1';
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key       | key_len | ref               | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+
|  1 | SIMPLE      | demo  | NULL       | ref  | abc_index     | abc_index | 18      | const,const,const |    1 |   100.00 | Using index |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql> explain select * from demo where c='1' and a='1' and b='1';
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key       | key_len | ref               | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+
|  1 | SIMPLE      | demo  | NULL       | ref  | abc_index     | abc_index | 18      | const,const,const |    1 |   100.00 | Using index |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

第一条 SQL 很显然可能用到联结索引。

从执行打算中能够看到,第二条 SQL 与第一条 SQL 应用的索引以及索引长度是统一的,都是应用 abc_index 索引,索引长度为 18 个字节。

按理说查问条件与索引的程序不统一,应该不会用到索引,然而因为 MySQL 有优化器存在,它会把第二条 SQL 优化成第一条 SQL 的样子,所以第二条 SQL 也应用到了联结索引 abc_index

综上所述,全字段匹配且为等值查问的状况下,查问条件的程序不统一也能应用到联结索引

5.2 局部字段匹配

第二种状况是查问条件与索引字段局部保持一致,这里就须要遵循最左前缀的准则,如:

select * from demo where a='1' and b='1';
select * from demo where a='1' and c='1';

上述的两条查问语句别离对应三个索引字段只用到两个字段的状况,它们的执行打算是:

mysql> explain select * from demo where a='1' and b='1';
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key       | key_len | ref         | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------+------+----------+-------------+
|  1 | SIMPLE      | demo  | NULL       | ref  | abc_index     | abc_index | 12      | const,const |    1 |   100.00 | Using index |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql> explain select * from demo where a='1' and c='1';
+----+-------------+-------+------------+------+---------------+-----------+---------+-------+------+----------+--------------------------+
| id | select_type | table | partitions | type | possible_keys | key       | key_len | ref   | rows | filtered | Extra                    |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------+------+----------+--------------------------+
|  1 | SIMPLE      | demo  | NULL       | ref  | abc_index     | abc_index | 6       | const |    1 |   100.00 | Using where; Using index |
+----+-------------+-------+------------+------+---------------+-----------+---------+-------+------+----------+--------------------------+
1 row in set, 1 warning (0.00 sec)

从它们的执行打算能够看到,这两条查问语句都应用到了 abc_index 索引,不同的是,它们应用到索引的长度别离是:12、6 字节。

在这里须要额定提一下索引长度的计算形式,对于本例中申明为 varchar(1) 类型的 a 字段,它的 索引长度 = 1 * (3) + 1 + 2 = 6

  • 第一个数字 1 是该字段申明时的长度。
  • 第二个数字 3 是该字段字符类型的长度:utf8=3, gbk=2, latin1=1。
  • 第三个数字 1 是该字段的默认类型,若默认容许 NULL,第三个数字是 1,因为 NULL 须要一个字节的额定空间;若默认不容许 NULL,这里应该是 0。
  • 第四个数字 2 是 varchar 类型的变长字段须要附加的字节。

所以这两条查问语句应用索引的状况是:

  1. 应用联结索引,索引长度为 12 字节,应用到的索引字段是 a,b 字段;
  2. 应用联结索引,索引长度为 6 字节,应用到的索引字段是 a 字段;

由此可见:最左前缀准则要求,查问条件必须是从索引最左列开始的间断几列

5.3 范畴查问

第三种状况是查问条件用的是范畴查问(<,>,!=,<=,>=,between,like)时,如:

select * from demo where a='1' and b!='1' and c='1';

这两条查问语句的执行打算是:

mysql> EXPLAIN select * from demo where a='1' and b!='1' and c='1';
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+--------------------------+
| id | select_type | table | partitions | type  | possible_keys | key       | key_len | ref  | rows | filtered | Extra                    |
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+--------------------------+
|  1 | SIMPLE      | demo  | NULL       | range | abc_index     | abc_index | 12      | NULL |    2 |    10.00 | Using where; Using index |
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+--------------------------+
1 row in set, 1 warning (0.00 sec)

从执行打算能够看到,第一条 SQL 应用了联结索引,且索引长度为 12 字节,即用到了 a,b 两个字段;第二条 SQL 也应用了联结索引,索引长度为 6 字节,仅应用了联结索引中的 a 字段。

综上所述,在全字段匹配且为范畴查问的状况下,也能应用联结索引,但只能应用到联结索引中第一个呈现范畴查问条件的字段

须要留神的是:

  • like 必须要求是左含糊匹配能力用到索引,因为字符类型字段的索引树也是有序的。
  • between 并不一定是范畴查问,它相当于应用 in 多值准确匹配,所以 between 并不会因为是范畴查问就让联结索引前面的索引列生效。

5.4 查问条件为函数或表达式

第四种状况是查问条件中带有函数或非凡表达式的,比方:

select * from demo where id + 1 = 2;
select * from demo where concat(a, '1') = '11';

可能因为数据的起因(空表),我输入的执行打算是应用了联结索引的,然而事实上,在查问条件中,等式不等式左侧的字段 蕴含表达式或函数时,该字段是不会用到索引的

至于起因,是因为应用函数或表达式的状况下,索引字段自身的值已不具备有序性。

5.5 其余索引生效的场景

  • 查问影响行数大于全表的 25%
  • 查问条件应用 <>(!=), not in, is not null
  • in 查问条件中值数据类型不统一,MySQL 会将所有值转化为与索引列统一的数据类型,从而无奈应用索引

6. 索引下推

上文中曾经列举了联结索引的理论构造、最左前缀准则以及索引生效的场景,这里再说一下索引下推这个重要的优化规定。

select * from demo where a > '1' and b='1';

mysql> explain select * from demo where a > '1' and b='1';
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+
| id | select_type | table | partitions | type  | possible_keys | key       | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+
|  1 | SIMPLE      | demo  | NULL       | range | abc_index     | abc_index | 6       | NULL |    1 |    10.00 | Using index condition |
+----+-------------+-------+------------+-------+---------------+-----------+---------+------+------+----------+-----------------------+
1 row in set, 1 warning (0.00 sec)

下面这条查问语句,从它的执行打算也能够看出,它应用的索引长度为 6 个字节,只用到了第一个字段。

所以 MySQL 在查问过程中,只会对第一个字段 a 进行 a > '1' 的条件判断,当满足条件后,存储引擎并不会进行 b=1 的判断,而是通过回表拿到整个数据行之后再进行判断。

这如同很蠢,就算索引只用到了第一个字段,但明明索引树中就有 b 字段的数据,为什么不间接进行判断呢?

听下来如同是个 bug,其实在未应用索引下推之前整个查问逻辑是:由存储引擎检索索引树,就算索引树中存在 b 字段的值,但因为这条查问语句的执行打算应用了联结索引但没有用到 b 字段,所以也无奈进行 b 字段的条件判断,当存储引擎拿到满足条件(a>'1')的数据后,再由 MySQL 服务器进行条件判断。

在 MySQL5.6 版本中对这样的状况进行优化,引入 索引下推 技术:在搜寻索引树的过程中,就算没能用到联结索引的其余字段,也能优先对查问条件中蕴含且索引也蕴含的字段进行判断,缩小回表次数,进步查问效率

在应用索引下推优化之后,b 字段作为联结索引列,又存在于查问条件中,同时又没有在搜寻索引树时被应用到,MySQL 服务器会把查问条件中对于 b 字段的局部也传给存储引擎,存储引擎会在搜寻索引树命中数据之后再进行 b 字段查问条件的判断,满足的才会退出后果集。

Ps: 执行打算中 Extra 字段的值蕴含 Using index condition 就代表应用到了索引下推。

7. 温故知新

  1. 索引分类?聚簇索引构造?非聚簇索引构造?
  2. 罕用的实现索引的数据模型?
  3. B+ 树索引的执行流程?
  4. 什么是回表?如何优化?
  5. 什么是笼罩索引?
  6. 什么是最左前缀准则?
  7. 索引在哪些状况下可能会生效?
  8. 什么是索引下推?

8. 参考资料

  • MySQL 索引 -B+ 树
  • MySQL 实战 45 讲 - 深入浅出索引
  • MySQL 索引原理及 BTree(B-/+Tree)构造详解
  • MySQL key_len 大小的计算
  • mysql 数据库中无奈应用索引的状况总结
  • Mysql 性能优化:什么是索引下推?
退出移动版