MySQL 的索引是如何执行的?

B+ 树在具体的引擎中是怎么发挥作用的呢?

本系列主要说一下 InnDB 索引。

主键索引

主键索引又叫聚簇索引,它使用 B+ 树构建,叶子节点存储的是数据表的某一行数据。

当表没有创建主键索引是,InnDB 会自动创建一个 ROWID 字段用于构建聚簇索引。

规则如下:

  1. 在表上定义主键 PRIMARY KEY,InnoDB 将主键索引用作聚簇索引。

  2. 如果表没有定义主键,InnoDB 会选择第一个不为 NULL 的唯一索引列用作聚簇索引。

  3. 如果以上两个都没有,InnoDB 会使用一个 6 字节长整型的隐式字段 ROWID 字段构建聚簇索引。

该 ROWID 字段会在插入新行时自动递增。

多说无益,以下面的 Student 表为例,它的 id 是主键,age 列为普通索引。

CREATE TABLE `student`  (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL,
  `age` int(11) NULL DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  INDEX `index_age`(`age`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 66 CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Compact;

数据如下:

(1)主键索引等值查询 sql

select * from student where id = 38;

过程如下:

  • 第一次磁盘 IO:从根节点检索,将数据块 1 加载到内存,比较 38 < 44,走左边。

  • 第二次磁盘 IO:将左边数据块 2 加载到内存,比较 8<37<38,走右边。

  • 第三次磁盘 IO:将右边数据块 6 加载到内存,比较 37<38,38=38。查询完毕,将数据返回客户端。

流程图:3 次磁盘 IO

3 次磁盘 IO

(2)主键索引范围查询 sql

select * from student where id between 38 and 44;

前面也介绍说了,B+ 树因为叶子节点有双向指针,范围查询可以直接利用双向有序链表。

过程如下:

第一次磁盘 IO:从根节点检索,将数据块 1 加载到内存,比较 38 < 44,走左边。

第二次磁盘 IO:将左边数据块 2 加载到内存,比较 8<37<38,走右边。

第三次磁盘 IO:将右边数据块 6 加载到内存,比较 37<38,38=38。走右边。

第四次磁盘 IO:将右边数据块 7 加载到内存,比较 38<44=44。查询完毕,将数据返回客户端。

流程图:一共四次磁盘IO

四次磁盘IO

普通索引

(1)普通索引等值查询 sql

在 InnDB 中,B+ 树普通索引不存储数据,只存储数据的主键值。

比如本表中的 age,它的索引结构就是这样的:

普通索引等值查询

执行以下查询语句,它的流程又是怎样的呢?

select * from student where age = 48;

使用普通索引需要检索两次索引。第一次检索普通索引找出 age = 48 得到主键值,再使用主键到主键索引中检索获得数据。这个过程称为回表。

也就是说,基于非主键索引的查询需要多扫描一遍索引树。因此,我们应该尽量使用主键查询。

过程如下:

第一次磁盘 IO:从根节点检索,将数据块1 加载到内存,比较 48 < 54,走左边。

第二次磁盘 IO:将左边数据块 2 加载到内存,比较 28<47<48,走右边。

第三次磁盘 IO:将右边数据块 6 加载到内存,比较 47<48,48=48。得到主键 38。

第四次磁盘 IO:从根节点检索,将根节点加载到内存,比较 38 < 44,走左边。

第五次磁盘 IO:将左边数据块 2 加载到内存,比较 8<37<38,走右边。

第六次磁盘 IO:将右边数据块 6 加载到内存,比较 37<38,38=38。查询完毕,将数据返回客户端。

流程图:一共 6 次磁盘 IO。

回表

组合索引

如果为每一种查询都设计一个索引,索引是不是太多了?

如果我现在要根据学生的姓名去查它的年龄。

假设这个需求出现的概览很低,但我们也不能让它走全表扫描吧?

但是为一个不频繁的需求创建一个(姓名)索引是不是有点浪费了?

那该咋做呢?我们可以建个(name,age)的联合索引来解决呀。

组合索引的结构如下图所示:

组合索引

执行以下查询语句,它的流程又是怎样的呢?

select * from student where name = '二狗5' and age = 48;

过程如下:

  • 第一次磁盘 IO:从根节点检索,将数据块1 加载到内存,比较 二狗5 < 二狗6,走左边。

  • 第二次磁盘 IO:将左边数据块 2 加载到内存,比较 二狗2<二狗4<二狗5,走右边。

  • 第三次磁盘 IO:将右边数据块 6 加载到内存,比较 二狗4<二狗5,二狗5=二狗5。得到主键 38。

  • 第四次磁盘 IO:从根节点检索,将根节点加载到内存,比较 38 < 44,走左边。

  • 第五次磁盘 IO:将左边数据块 2 加载到内存,比较 8<37<38,走右边。

  • 第六次磁盘 IO:将右边数据块 6 加载到内存,比较 37<38,38=38。查询完毕,将数据返回客户端。

流程图:一共六次磁盘 IO

回表

为什么需要联合索引?

最左匹配原则

最左前缀匹配原则和联合索引的索引存储结构和检索方式是有关系的。

在组合索引树中,最底层的叶子节点按照第一列 name 列从左到右递增排列,但是 age 列是无序的,age 列只有在 name 列值相等的情况下小范围内递增有序。

PS: 这里为什么 age 无顺序?其实就是一条记录的多个字段,当以 name 作为第一个排序字段时,后面的 age 等字段并不能保证顺序。 当然当 name 相等的时候,age 是小范围内有序的。

就像上面的查询,B+ 树会先比较 name 列来确定下一步应该搜索的方向,往左还是往右。如果 name 列相同再比较 age 列。

但是如果查询条件没有 name 列,B + 树就不知道第一步应该从哪个节点查起,这就是所谓的最左匹配原则。

可以说创建的 idx_name_age (name,age) 索引,相当于创建了 (name)、(name,age)两个索引。、

组合索引的最左前缀匹配原则:使用组合索引查询时,mysql 会一直向右匹配直至遇到范围查询 (>、<、between、like) 就停止匹配

基础例子

假设,我们对(a,b)字段建立一个索引,也就是说,你where后条件为

a = 1
a = 1 and b = 2

是可以匹配索引的。

但是要注意的是~你执行 b= 2 and a =1 也是能匹配到索引的,因为Mysql有优化器会自动调整a,b的顺序与索引顺序一致。

相反的,你执行 b = 2 就匹配不到索引了。

而你对(a,b,c,d)建立索引,where后条件为

a = 1 and b = 2 and c > 3 and d = 4 

那么,a,b,c三个字段能用到索引,而d就匹配不到。

因为遇到了范围查询!

ps: 为什么遇到范围查询就不行呢?

最左匹配的原理?

假设,我们对(a,b)字段建立索引,那么入下图所示

最左匹配

如图所示他们是按照a来进行排序,在a相等的情况下,才按b来排序。

因此,我们可以看到a是有序的1,1,2,2,3,3。

而b是一种全局无序,局部相对有序状态!

什么意思呢?

从全局来看,b的值为1,2,1,4,1,2,是无序的,因此直接执行b = 2这种查询条件没有办法利用索引。

从局部来看,当a的值确定的时候,b是有序的。

例如a = 1时,b值为1,2是有序的状态。当a=2时候,b的值为1,4也是有序状态。

因此,你执行a = 1 and b = 2是a,b字段能用到索引的。

而你执行a > 1 and b = 2时,a字段能用到索引,b字段用不到索引。

因为a的值此时是一个范围,不是固定的,在这个范围内b值不是有序的,因此b字段用不上索引。

综上所示,最左匹配原则,在遇到范围查询的时候,就会停止匹配。

几个例子

例子 1

如果sql为

SELECT * FROM table WHERE a = 1 and b = 2 and c = 3; 

如何建立索引?

如果此题回答为对(a,b,c)建立索引,那都可以回去等通知了。

此题正确答法是,(a,b,c)或者(c,b,a)或者(b,a,c)都可以,重点要的是将区分度高的字段放在前面,区分度低的字段放后面

像性别、状态这种字段区分度就很低,我们一般放后面。

例如假设区分度由大到小为b,a,c。那么我们就对(b,a,c)建立索引。

在执行sql的时候,优化器会 帮我们调整where后a,b,c的顺序,让我们用上索引。

题型二

如果sql为

SELECT * FROM table WHERE a > 1 and b = 2; 

如何建立索引?

如果此题回答为对(a,b)建立索引,那都可以回去等通知了。

此题正确答法是,对(b,a)建立索引。如果你建立的是(a,b)索引,那么只有a字段能用得上索引,毕竟最左匹配原则遇到范围查询就停止匹配。

如果对(b,a)建立索引那么两个字段都能用上,优化器会帮我们调整where后a,b的顺序,让我们用上索引。

题型三

如果sql为

SELECT * FROM `table` WHERE a > 1 and b = 2 and c > 3; 

如何建立索引?

此题回答也是不一定,(b,a)或者(b,c)都可以,要结合具体情况具体分析。

题型四

SELECT * FROM `table` WHERE a = 1 ORDER BY b;

如何建立索引?

这还需要想?一看就是对(a,b)建索引,当a = 1的时候,b相对有序,可以避免再次排序!

那么

SELECT * FROM `table` WHERE a > 1 ORDER BY b; 

如何建立索引?

对(a)建立索引,因为a的值是一个范围,这个范围内b值是无序的,没有必要对(a,b)建立索引。

题型五

SELECT * FROM `table` WHERE a IN (1,2,3) and b > 1; 

如何建立索引?

还是对(a,b)建立索引,因为 IN 在这里可以视为等值引用,不会中止索引匹配,所以还是(a,b)!

覆盖索引

覆盖索引是一种很常用的优化手段。

因为在上面普通索引的例子中,由于查询结果所需要的数据只在主键索引上有,所以不得不回表。

那么有没有可能经过索引优化,避免回表呢?

比如改成这样子:

select age from student where age = 48;

在上面普通索引例子中,如果我只需要 age 字段,那是不是意味着我们查询到普通索引的叶子节点就可以直接返回了,而不需要回表。这种情况就是覆盖索引。

索引的使用技巧

避免回表

上面说了,回表的原因是因为查询结果所需要的数据只在主键索引上有,所以不得不回表。

回表必然会影响性能。

那怎么避免呢?

使用覆盖索引,举个栗子:还是上面的 student ,它的一条 sql 在业务上很常用:

select id, name, age from student where name = '二狗2';

而 student 表的其他字段使用频率远低于它,在这种情况下,如果我们在建立 name 字段的索引的时候,并不是使用单一索引,而是使用联合索引(name,age)这样的话再执行这个查询语句就可以根据辅助索引查询到的结果获取当前语句的完整数据。

这样就有效避免了通过回表再获取 age 的数据。

这就是一个典型的用覆盖索引的优化策略减少回表的情况。

联合索引的使用

联合索引,在建立索引的时候,尽量在多个单列索引上判断下是否可以使用联合索引。

联合索引的使用不仅可以节省空间,还可以更容易的使用到索引覆盖。

比如上面的 student 表,我就建了 (name,age) 和 age 索引。

联合索引的创建原则,在创建联合索引的时候因该把频繁使用的列、区分度高的列放在前面,频繁使用代表索引利用率高,区分度高代表筛选粒度大

也可以在常需要作为查询返回的字段上增加到联合索引中,如果在联合索引上增加一个字段而使用到了覆盖索引,这种情况下应该使用联合索引。

联合索引的使用

考虑当前是否已经存在多个可以合并的单列索引,如果有,那么将当前多个单列索引创建为一个联合索引。

当前索引存在频繁使用作为返回字段的列,这个时候就可以考虑当前列是否可以加入到当前已经存在索引上,使其查询语句可以使用到覆盖索引。

索引下推

现在我的表数据是这样的:加了一个 sex 列。

说到满足最左前缀原则的时候,最左前缀可以用于在索引中定位记录。

这时,你可能要问,那些不符合最左前缀的部分,会怎么样呢?

我们还是以学生表的联合索引(name,age)为例。

如果现在有一个需求:检索出表中“名字第一个字是张,而且年龄是 38 岁的所有男生”。

那么,SQL语句是这么写的:

select * from student where name like '张%' and age=38 and sex='男';

根据前缀索引规则,所以这个语句在搜索索引树的时候,只能用”张”,找到三个满足条件的记录(图中红框数据)。

当然,这还不错,总比全表扫描要好。

然后呢?当然是判断其他条件是否满足。

在MySQL5.6之前,只能从满足条件的记录 id=18 开始一个个回表。

到主键索引上找出数据行,再对比字段

而MySQL 5.6引入的索引下推优化(index condition pushdown),可以在索引遍历过程中,对索引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数

它的整个执行的流程图是这样的:

流程图

InnoDB在(name,age)索引内部就判断了 age 是否等于 38,对于不等于 38 的记录,直接判断并跳过。

在我们的这个例子中,只需要对 id=18 和 id=65 这两条记录回表取数据判断,就只需要回表 2 次,这就是所谓的索引下推。

参考资料

MySQL:索引详解

https://www.begtut.com/mysql/mysql-composite-index.html

【原创】面试官:谈谈你对mysql联合索引的认识?