查看原文
其他

Mysql8中降序索引的底层实现

1点25 1点25 2022-09-05

什么是降序索引

大家可能对索引比较熟悉,而对降序索引比较陌生,事实上降序索引是索引的子集。

我们通常使用下面的语句来创建一个索引:

create index idx_t1_bcd on t1(b,c,d);

上面sql的意思是在t1表中,针对b,c,d三个字段创建一个联合索引。

但是大家不知道的是,上面这个sql实际上和下面的这个sql是等价的:

create index idx_t1_bcd on t1(b asc,c asc,d asc);

asc表示的是升序,使用这种语法创建出来的索引叫做升序索引。也就是我们平时在创建索引的时候,创建的都是升序索引。

可能你会想到,在创建的索引的时候,可以针对字段设置asc,那是不是也可以设置desc呢?

当然是可以的,比如下面三个语句:

create index idx_t1_bcd on t1(b desc,c desc,d desc);
create index idx_t1_bcd on t1(b asc,c desc,d desc);
create index idx_t1_bcd on t1(b asc,c asc,d desc);

这种语法在mysql中也是支持的,使用这种语法创建出来的索引就叫降序索引,关键问题是:在Mysql8.0之前仅仅只是语法层面的支持,底层并没有真正支持。

我们分别使用Mysql7、Mysql8两个版本来举例子说明一下:

在Mysql7、Mysql8中分别创建一个表,有a,b,c,d,e五个字段:

create table t1 (
a int primary key,
b int,
c int,
d int,
e varchar(20)
) engine=InnoDB;

然后分别创建一个降序索引:

create index idx_t1_bcd on t1(b desc,c desc,d desc);

创建成功后,我们使用以下sql查看一下索引信息:

show index from t1;

Mysql7中你将得到结果:

Mysql8中你将得到结果:

我们只关心Key_name为idx_t1_bcd的三行记录,细心的你应该可以发现,这两个结果中的Collation字段的结果是不一样的:

  • 在Mysql7中,Collation字段的结果为A,A,A,表示b,c,d三个字段的排序方式是asc

  • 在Mysql8中,Collation字段的结果为D,D,D,表示b,c,d三个字段的排序方式是desc

但是我们在创建索引的时候,明明在语法层面已经指定了b,c,d三个字段的排序方式是desc,这就可以看出来在Mysql7中降序索引只是语法层面的支持,底层并没有真正支持,并且固定是升序索引。而在Mysql8中则真正从底层支持了降序索引。

到此为止,大家应该对升序索引和降序索引有了一个大概的了解,但并没有真正理解,因为大家并不知道升序索引与降序索引底层到底是如何实现的。

升序索引底层实现

我们知道,索引是用来提高查询速度的,但是为什么索引能提高查询速度呢?

给定你一个数列,比如[1,3,7,9,2,5,4,6,8],这是一个无序的数列或数组,现在如果想提高这个数列的查询速度,你首先会做什么?我相信大部分人都能够想到先排序,先把这个无序的数列,按从小到大的顺序进行排序,比如得到[1,2,3,4,5,6,7,8,9],有了这个有序的数列之后,我们就可以利用比如二分法等等算法来提高这个数列的查询速度了。

我举这个例子想告诉大家的是:想提高数据集合的查询速度,首先你可以对这些数据进行排序。

所以,对Mysql表中的存储的数据也是一样的,我们如果想提高这个表的查询速度,我们可以先对这个表里的数据进行排序,那么表里的某一行数据包括了很多字段,我们现在想对这些数据行进行排序,我们应该根据哪些字段来确定这个顺序呢?这就是索引,在创建索引的时候你所指定的列就是用来对表里的数据行进行排序的。

比如我们仍然利用上面所创建的t1表,向t1表里插入8条数据:

insert into t1 values(4,3,1,1,'d');
insert into t1 values(1,1,1,1,'a');
insert into t1 values(8,8,8,8,'h');
insert into t1 values(2,2,2,2,'b');
insert into t1 values(5,2,3,5,'e');
insert into t1 values(3,3,2,2,'c');
insert into t1 values(7,4,5,5,'g');
insert into t1 values(6,6,4,4,'f');

那么这些数据肯定是存储在文件中的,所以文件中保存这些数据的格式大概如下,顺序与插入顺序保持一致:

4311d
1111a
8888h
2222b
5235e
3322c
7455g
6644f

注意,t1是Innodb的存储引擎,而且a字段是主键,所以Innodb存储引擎在处理这些插入的数据时,会按主键进行排序,也就是上面我说的文件中保存这些数据的格式是不准确的,因为不想篇幅太长,所以不去深究,感兴趣的同学可以关注一波公众号:1点25,我会专门写一篇文章来讲解Innodb中索引的具体实现,包括B+树到底是如何生成的。

而如果我们基于上面的这种存储方式,来查找数据,比如查找a=3的这行记录,查找需要从第一行记录开始查找,那么要查找6次,而如果我们将上面的数据按照a字段的大小来进行排序:

1111a
2222b
3322c
4311d
5235e
6644f
7455g
8888h

排好序之后,如果我们还是查找a=3的这行记录,我们只需要查3次了。而且这样还有一个好处就是,如果我们现在需要查找a=3.5这行数据,如果我们基于未排序之前的存储方式,我们需要查询所有8行数据最终确定a=3.5这行数据不存在,而如果我们利用排好序之后的存储方式,我们就只需要查4次就好了,因为当你查到4311d这行记录时,你会发现4>3.5了,已经可以确定a=3.5的这行记录不存在了。

而如果我们现在对t1创建一个索引,就像上面创建索引一样,如果我们写的是下面的sql:

create index idx_t1_bcd on t1(b,c,d);

这个sql表示要对t1创建一个索引,索引字段是b,c,d,并且是升序的,所以实际上就是对原本的数据按照b,c,d三个字段进行排序,那么排序之后类似:

1111a
2222b
5235e
4311d
3322c
7455g
6644f
8888h

可以好好看下,上面的记录是按照b,c,d三个字段来对数据行就行排序的,比如1111a中的b,c,d三个字段的值是111,而2222b中的b,c,d三个字段的值是222111是小于222的,所以对应的行排在前面。

那么数据如果这样排序有什么好处呢?其实和刚刚按a字段排序之后的好处是类似的,比如你现在想来查找b=4 and c=4 and d=4的数据也是能查询更快的,实际上这就是索引的原理:我们对某个表创建一个索引,就是对这个表中的数据进行排序,而排好序之后的数据是能够提高查询速度。

还有一点需要注意的是,排序有很多中方式,或者所可以利用一些数据结构,比如二叉树、红黑树、B+树,这些数据结构实际上就是对数据进行排序,只是排序的形式各不相同而已,每种数据结构有它各自的特点,而大家应该都知道,Mysql中用得最多的就是B+树了,还是一样,因为篇幅不想太长,感兴趣的同学可以关注一波公众号:1点25,我会专门写一篇文章来讲解Innodb中索引的具体实现,包括B+树到底是如何生成的。

相信,看到这里,大家应该对索引重新有了认识,只不过我们上面举的几个例子都是升序排序,而且排好序之后的数据不仅可以提高查询速度,而且对于order by也是管用的,比如我们如果现在想对t1进行order by b asc,c asc,d asc;对于这个排序,如果已经在t1表建立了b,c,d的升序索引,那么就代表对t1表中的数据已经提前按照b,c,d排好序了,所以对于order by语句可以直接使用已经排好序的数据了,不用利用filesort再次进行排序了。

而且如果我们的order by是order by b desc, c desc, d desc,同样可以利用b,c,d的升序索引,因为如果是order by b asc,c asc,d asc就从上往下遍历即可,如果是order by b desc, c desc, d desc就从下往上遍历即可。

那么,如果是order by b asc, c desc, d desc呢?这个order by是不是就没有办法利用b,c,d的升序索引了。

这个时候就需要降序索引了。

降序索引底层实现

我们花了较大篇幅介绍了升序索引的实现原理,总结来说就是对表中的数据按照指定的字段比较大小进行升序排序

升序是什么?是数据进行大小比较后,是小的在上,大的在下,或者如果是B+树的话就是小的在左,大的在右。而降序就是大的在上,小的在下,或者如果是B+树的话就是大的在左,小的在右

所以,对于上面的那份原始数据:

4311d
1111a
8888h
2222b
5235e
3322c
7455g
6644f

如果我们将这份数据按照a desc进行排序就是:

8888h
7455g
6644f
5235e
4311d
3322c
2222b
1111a

非常简单吧,那如果我们将这份数据按照b desc, c desc, d desc排序就是:

8888h
6644f
7455g
3322c
4311d
5235e
2222b
1111a

也非常简单,那如果我们要将这份数据按照b desc, c asc, d desc排序呢?这是不是就有点懵了?

其实不难,排序其实就是对数据比较大小,我们用下面三行数据来模拟一下:

3322c
7455g
4311d

首先,按照b desc, c desc, d desc来排序,得到结果如下:

7455g
3322c
4311d

按照b desc, c asc, d desc来排序,得到结果如下:

7455g
4311d
3322c

可能一部分大佬已经能理解,实际上b desc所表达的意思就是b字段数据大者在上,数据小者在下,数据相等的话则开始比较c字段,而c字段是按升序排的,也就是c字段数据小者在下,数据大者在上。所以就得到了上面的结果。

这就是降序索引

总结

实际上升序索引和降序索引是不同的排序方式而已,Mysql8中正在实现了降序索引后,我们在创建索引时更加灵活,可以根据业务需要的排序规则来创建合适的索引,这样能使你的查询更快。

当然本文只讲了原理,大家一定要知道Mysql中排序利用的B+树,而不是上面我举例的那种很简单的方式,但是就算用B+树原理也是一样的,比较数据的大小而已。

还有一点,现在只有Innodb存储引擎支持降序索引

如果觉得这篇文章能让你学到知识,能否帮忙转发,将知识分享出去。如果想第一时间学习更多的精彩的内容,请关注微信公众号:1点25


您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存