MySQL面试必备一之索引

本文首发于公众号:Hunter后端

原文链接:MySQL面试必备一之索引

在面试过程中,会有一些关于 MySQL 索引相关的问题,以下总结了一些:

  1. MySQL 的数据存储使用的是什么索引结构
  2. B+ 树的结构是什么样子
  3. 什么是复合索引、聚簇索引、覆盖索引
  4. 什么是最左匹配原则
  5. 数据 B+ 树中是如何查询的
  6. 回表是什么操作
  7. B+ 树的查询有什么优势
  8. 索引下推是什么意思

对于上面这几个问题,看完这篇笔记你应该就会明白这些问题应该如何作答。

这篇笔记将从以下几个方面开始介绍:

  1. B+树
  2. 查询数据的过程
  3. 覆盖索引
  4. 联合索引
  5. MyISAM 的存储结构
  6. InnoDB 与 MyISAM 的区别
  7. B 树与 B+ 树

1、B+树

MySQL 的存储引擎包括 InnoDB、MyISAM、Memory 等,其中 InnoDB 是默认的表存储引擎,InnoDB 和 MyISAM 的数据都存储在 B+ 树这种结构中。

首先来了解下 B+ 树的结构。

1. B+ 树结构

与二叉树一样,B+ 树也是一种树结构,与之不同的点在于每一层并非只有左右两个子结点,而是可以有多个结点,而在 InnoDB 中,数据都是存储在叶子结点上,现在假设我们有一张 user 表,以 id 为主键,有 name、age 这两个字段,那么数据的存储示意图则如下:

在上图中,只展示了 B+ 树的两层,每一层有四个子结点,所有的数据都存储在叶子结点上。

在 InnoDB 中,B+ 树的高度通常为 2 到 4 层,假设每一层我们有 1000 个结点,那么如果树有 4 层,那么在第四层的叶子结点我们可以存储 1000 的三次方条数据,那么就可以存储 10 亿条数据。

2. 主键索引与聚簇索引

当我们创建一张表,并往里面添加数据,数据存储的格式就是上面这张图的形式,默认以主键作为索引,也就是 B+ 树的非叶子结点,所以又称其为主键索引。

对于这张表,除了 id 字段,还有 age 和 name 字段,这几个表字段是一起存放在叶子结点的,因此这种存储方式也称为聚簇索引。

3. 非聚簇索引与二级索引

在 InnoDB 中,除了主键索引外,我们还可以为表的某个或者某些字段创建索引,对于这些索引,我们称其为非聚簇索引或者二级索引。

二级索引的存储结构也是 B+ 树,不一样的点在于非叶子结点的值是创建了索引的字段值,叶子结点就不再是这条表数据了,而是这个索引字段所在的数据的主键值。

还是以前面的 user 表为例,我们在 name 字段上创建索引,那么 InnoDB 会额外创建一个 B+ 树,B+ 树的结构大致如下:

这里为了更直白的表示字段值的排序,用了英文名字来表示,如上就是一个二级索引的存储形式。

2、查询数据的过程

1. 根据主键查询

比如我们要查询 id = 80 的数据,sql 语句如下:

select id, name, age from user where id = 80;

这里是针对 id 字段进行查询,所以可以直接查询主键索引,根据上面主键索引的示意图,其查询步骤如下:

  1. 根据 id = 18 逐层找到 B+ 树的对应非叶子结点,比如这里就到了图里的最上层结点
  2. 根据 id = 18,判断 1 <18 < 35,所以查询进入的叶子结点将会进入最左侧往下
  3. 在最左侧的叶子结点,找到 id = 18 的叶子结点,然后这个节点对应的 id,name,age 字段获取然后返回

以上就是一次根据主键进行查询的过程

2. 根据二级索引查询

还是 user 表,在 name 字段上建立了一个二级索引,我们想要找到 name = "Hunter" 的 id,name,age 字段:

select id, name, age from user where name = "Hunter";

其查询过程如下:

  1. 根据 name="Hunter" 查询二级索引的 B+ 树,也就是我们的第二张图,根据非叶子结点的值找到最左侧的数据
  2. 根据 "Hunter" 可以找到这条数据的主键 id = 3
  3. 根据 id = 3 去主键索引的 B+ 树里查询对应的字段(这里的查询操作就是根据主键查询数据了)

回表:上面的查询过程中,根据二级索引获取到的主键 id,到主键索引里查询对应的数据,这个过程就称为回表

3、覆盖索引

对上面二级索引查询的过程,我们有一个回表的操作,即根据二级索引获取到的主键 id 再去主键索引获取相应的字段数据,这部分的查询过程是会影响查询效率的。

那么针对这种回表的情况,我们可以在某些情况下使用覆盖索引来对其进行优化。

所谓覆盖索引,并非某种实际的索引结构,而应该算得上是一种思想或者优化手段。其主要思想为在二级索引中就可以拿到查询所需的全部字段,而不需要进行回表操作。

针对前面我们对 name 加了索引的情况,如果我们的 SQL 语句如下,那么即可使用覆盖索引,而不需要再到主键索引里回表查询:

select id, name from user where name = "Hunter";

在上面这个语句中,我们查询的是 id 和 name 两个字段,这两个字段在 name 字段的二级索引的查询中即可获取所需的字段值,那么则不需要进行回表操作,这个过程就相当于使用了覆盖索引。

而如果我们所需要的字段并不只是这两个字段,比如我们还要查询 age 字段,针对这种情况,如果要用覆盖索引的话,就需要引入下一节的内容,联合索引,或者叫复合索引。

4、联合索引

复合索引,或者叫联合索引,指的是针对多个字段创建的索引,常常适用于多个字段进行查询的场景。

1. 联合索引的结构

联合索引也是二级索引,不过它的非叶子结点的值是多个字段组合的。

还是以 user 表为例,我们在 age 和 name 上创建一个联合索引:

CREATE INDEX age_name_idx ON user (age, name);

那么,在 MySQL 中,这个二级索引的存储结构大致如下:

根据上面的这个结构,我们可以知道,字段的顺序是十分重要的,如果我们 SQL 语句的使用不当可能就会用不上联合索引。

2. 联合索引生效的情况

根据上图可以看到非叶子结点的值由两部分组成,分别是 age 和 name 的值,那么我们在进行查询的时候,也应该遵循这个顺序才可能使得索引生效。

1) 单个字段查询

如果我们要查询单个字段,比如 age,那么下面的条件都可以使得索引生效:

where age = 23;
where age > 25;

但是如果 where 后面的条件是针对 name 字段,那么下面的条件则不会使得这个联合索引生效:

where name = "Hunter";

2) 多个字段查询

如果是多个字段查询,那么则使用的时候一定要注意查询的顺序,下面的条件的是可以生效的:

where age = 23 and name = "Hunter";
where age = 24 and name like "Hun*";

而如果是 age 是一个范围查找,则不管 name 字段是什么条件,这个索引也可以生效,但仅仅是 age 字段会用到索引,name 字段的则不会用到索引,比如:

where age > 34 and name = "Hunter";

上面这个 SQL 语句,索引则只会对 age 字段生效进行范围查找,name 字段不用用到索引的精确匹配。

3) 最左匹配原则

基于联合索引的结构,如上图,最左匹配原则的概念其实就显而易见了,即联合索引只会从建立了索引的最左字段开始匹配,直到遇到范围查询则停止,就比如上面提到的这条:

where age > 34 and name = "Hunter";

它匹配到 age 就停止了,因为 age 是一个范围查询。

再来一种情况,如果我们的联合索引字段有三个,按照顺序为 age, name 和 field_3,下面的语句则会分别匹配到 age、name 和 field_3:

where age > 4 and name = "Hunter" and field_3 = 45;
where age = 34 and name like "Hun*" and field_3 = 45;
where age = 34 and name = "Hunter" and field_3 > 45;

下面这几种针对后面几个字段的查询联合索引都是不生效的:

where name = "Hunter" and field_3 = 45;
where field_3 = 45;

因为他们都没有从联合索引的最左字段字段开始查询。

3. 索引下推

索引下推是 MySQL 5.6 版本及以上引入的一个特性,主要用于减少回表的次数,从而实现提高查询性能的效果。

还是以前面 age 和 name 这个复合索引为例,SQL 如下:

where age > 30 and name like "Hun*";

如果没有索引下推,那么它的查询流程是根据 age > 30 这个条件,查询主键 id,逐个回表去主键索引里查询 name 字段的值是否满足 "Hun*" 这个条件。

而如果有索引下推这个优化,那么在二级索引里,查找出 age > 30 的值后,会直接根据复合索引中 name 的值来判断是否满足 "Hun*" 这个特性,满足的话就去回表查询,不满足则在当前复合索引里直接将这条数据过滤掉。

所谓的索引下推就是通过这个流程来减少回表的次数,以提高查询的性能。

5、MyISAM 的存储结构

MyISAM 的数据存储结构也是 B+ 树,但有一点不同,那就是 InnoDB 的叶子结点存储的是完整的一条数据,而 MyISAM 的叶子结点存储的数据的指针,通过指针指向底层存储的数据,其大概示意图如下:

同理,MyISAM 的二级索引的叶子结点也是直接指向存储的数据。

因此,MyISAM 在底层存储的表文件有三个,一个是 frm,是表的定义文件,一个 MYD,用于存储数据的文件,一个是 MYI,用于存储索引的文件。

相对来说,InnoDB 就只有两个,一个是 frm,一个是 IBD,用于存储索引和数据,因为 InnoDB 的叶子结点即存储了数据。

6、InnoDB 与 MyISAM 的区别

这里总结一下 InnoDB 与 MyISAM 的区别:

  1. InnoDB 是聚簇索引,MyISAM 是非聚簇索引
    1. 即 InnoDB 的主键索引是数据和索引放在一起的,而 MyISAM 是索引和数据分离的
  2. InnoDB 支持外键,MyISAM 不支持外键
  3. InnoDB 支持事务,MyISAM 不支持事务
  4. InnoDB 默认支持到行级锁,而 MyISAM 支持表级锁

7、B 树与 B+ 树

B 树和 B+ 树是很相似的树结构,都是每个结点都有多个子结点,不一样的在于 B 树的非叶子结点也存有数据,而 B+ 树只有叶子结点才有数据,非叶子结点都是索引数据,且 B+ 树的叶子结点之间也形成有序链表。

针对以上这个不同点,在 MySQL 中使用 B+ 树有如下优点:

  1. B+ 树在非叶子结点不包含数据,因此在内存页可以存放更多 key,从而在查询的时候可以减少 IO 次数
  2. B+ 树的叶子结点之间形成链表,遍历操作会更方便,而 B 树需要从根节点从上往下遍历
  3. B+ 树的数据都存放在叶子结点,而 B 树的非叶子结点也都有数据,所以查询的过程中 B+ 树总是需要访问到叶子结点,所以 B+ 树的查询效率会更稳定

如果想获取更多后端相关文章,可扫码关注阅读:

作者:XHunter原文地址:https://www.cnblogs.com/hunterxiong/p/18106972

%s 个评论

要回复文章请先登录注册