Shulou(Shulou.com)06/01 Report--

This article mainly explains the MySQL8 in the implementation of the bottom of the descending index method, the content is clear and clear, interested in this small partner can learn, I believe you will be helpful after reading.

What is a descending index?

You may be familiar with indexes, but you are unfamiliar with descending indexes. In fact, descending indexes are subsets of indexes.

We usually use the following statement to create an index:

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

SQL above means to create a union index on the three fields b,c,d in the t1 table.

But what you don't know is that the SQL above is actually equivalent to the SQL below:

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

Asc represents ascending, and indexes created using this syntax are called ascending indexes. That is, when we usually create indexes, we create ascending indexes.

You might think that when you create an index, you can set asc for a field, but can you also set desc?

Of course, it is possible, such as the following three sentences:

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);

This syntax is also supported in mysql, and indexes created using this syntax are called descending indexes. The key problem is that before Mysql 8.0, it was only syntax level support, and the bottom layer did not really support it.

Let's use MySQL7 and MySQL8 as examples:

Create a table in Mysql7 and Mysql8, respectively, with five fields: a,b,c,d,e:

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

Then create a descending index:

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

After successful creation, we use the following sql to check the index information:

show index from t1;

In Mysql7 you will get the result:

In Mysql8 you will get the result:

We only care about the three rows of records with Key_name idx_t1_bcd. If you are careful, you should find that the results of the Collation field in these two results are different:

In Mysql7, the result of the Collation field is A, indicating that the sorting method of the three fields b,c,d is asc. In Mysql8, the result of the Collation field is D, indicating that the sorting method of the three fields b,c,d is desc.

However, when we create the index, it is obvious that the sorting method of the three fields b,c,d has been specified at the syntax level as desc, which can be seen that in Mysql7, descending index is only supported at the syntax level, and the bottom layer does not really support it, and it is fixed as ascending index. In Mysql8, descending indexing is supported from the bottom up.

At this point, you should have a general understanding of ascending and descending indexes, but you don't really understand, because you don't know how ascending and descending indexes are implemented at the bottom.

Low-level implementation of ascending index

We know that the index is used to improve query speed, but why can the index improve query speed?

Given you a sequence, such as [1, 3, 7, 9, 2, 5, 4, 6, 8], which is an unordered sequence or array, what would you do first if you wanted to speed up the query of this sequence? I believe that most people can think of sorting first, first sorting this disordered series from small to large, such as [1, 2, 3, 4, 5, 6, 7, 8, 9], with this ordered series, we can use algorithms such as dichotomy to improve the query speed of this series.

What I'm trying to show you with this example is that to speed up querying a data set, you can sort the data first.

So, the data stored in Mysql table is the same, if we want to improve the query speed of this table, we can sort the data in this table first, then a row of data in the table includes a lot of fields, we now want to sort these data rows, which fields should we determine the order according to? This is the index, and the columns you specify when creating the index are used to sort the rows in the table.

For example, we still use the t1 table created above to insert 8 pieces of data into the t1 table:

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');

Then the data must be stored in the file, so the format of storing the data in the file is roughly as follows, in the same order as the insertion order:

4311d

1111a

8888h

2222b

5235e

3322c

7455g

6644f

Note that t1 is Innodb's storage engine, and field a is the primary key, so Innodb's storage engine will sort by primary key when processing these inserted data, that is, the format of saving these data in the file I said above is inaccurate, because I don't want to be too long, so I don't go deep into it. Interested students can pay attention to a wave of public numbers: 1:25. I will write an article to explain the specific implementation of Innodb's index, including how B+ trees are generated.

And if we look for data based on the above storage method, such as finding the row of records with a=3, the search needs to start from the first row of records, so we have to find 6 times, and if we sort the above data according to the size of the a field:

1111a

2222b

3322c

4311d

5235e

6644f

7455g

8888h

After sorting, if we still look for the row with a=3, we only need to look at it three times. And one of the benefits of this is that if we now need to look up the row a=3.5, if we look up all eight rows of data based on the unsorted storage method, we need to finally determine that the row a=3.5 does not exist, and if we use the sorted storage method, we only need to look up four times, because when you look up the row 4311d, you will find that 4>3.5. It has been determined that the row with a=3.5 does not exist.

And if we now create an index on t1, just like we did above, if we write sql:

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

This sql means to create an index for t1, the index fields are b,c,d, and it is ascending, so in fact, the original data is sorted according to the three fields b,c,d, then the sorting is similar:

1111a

2222b

5235e

4311d

3322c

7455g

6644f

8888h

You can take a good look, the above records are sorted according to the three fields b,c,d, for example, the values of the three fields b,c,d in 1111a are 111, and the values of the three fields b,c,d in 222b are 222, 111 is less than 222, so the corresponding rows are ranked first.

So what's the benefit of sorting data like this? In fact, the benefits of sorting by a field are similar. For example, if you want to find the data of b=4 and c=4 and d=4, you can query faster. In fact, this is the principle of index: we create an index for a table, which is to sort the data in this table, and the sorted data can improve the query speed.

Another point to note is that there are many ways to sort, or you can use some data structures, such as binary trees, red-black trees, B+ trees, these data structures are actually sorting data, but the form of sorting is different, each data structure has its own characteristics, and we should all know that Mysql is the most used B+ tree.

I believe, see here, we should have a new understanding of the index, but we cited a few examples above are ascending sort, and the sorted data can not only improve the query speed, but also for order by is also useful, for example, if we now want to t1 order by b asc,c asc,d asc; For this sort, if the ascending index of b,c,d has been established in the t1 table, then it means that the data in the t1 table has been sorted in advance according to b,c,d, so for the order by statement, you can directly use the sorted data without using filesort to sort again.

And if our order by is order by b desc, c desc, d desc, we can also use the ascending index of b,c,d, because if it is order by b asc,c asc,d asc, we can traverse from top to bottom, if it is order by b desc, c desc, d desc, we can traverse from bottom to top.

What if it is order by b asc, c desc, d desc? This order by means that there is no way to use the ascending index of b,c,d.

At this point, you need a descending index.

Low-level implementation of descending index

We spent a lot of time explaining how ascending indexing works, and in summary, it sorts the data in a table in ascending order by a specified field comparison size.

What's ascending? After comparing the sizes of the data, the small ones are on the top and the large ones are on the bottom, or if it is a B+ tree, the small ones are on the left and the large ones are on the right. Descending order would be big up, small down, or big on the left and small on the right if it was a B+ tree.

So, for the raw data above:

4311d

1111a

8888h

2222b

5235e

3322c

7455g

6644f

If we sort this data by a desc:

8888h

7455g

6644f

5235e

4311d

3322c

2222b

1111a

Very simple, so if we sort this data by b desc, c desc, d desc, then:

8888h

6644f

7455g

3322c

4311d

5235e

2222b

1111a

And it's very simple, so what if we want to sort this data by b desc, c asc, d desc? Isn't this a little confusing?

In fact, it is not difficult. Sorting is actually comparing the size of the data. We use the following three lines of data to simulate it:

3322c

7455g

4311d

First, sorting by b desc, c desc, d desc yields the following result:

7455g

3322c

4311d

Sorting by b desc, c asc, d desc yields the following result:

7455g

4311d

3322c

Perhaps some big shots can already understand, in fact, what b desc means is that the data in field b is larger than the data in field b, and the data in field c is smaller than the data in field c. If the data is equal, the comparison will begin, and field c is arranged in ascending order, that is, the data in field c is smaller than the data in field c, and the data in field c is larger. So we get the results above.

This is called a descending index.

summary

In fact, ascending index and descending index are different sorting methods, Mysql8 is implementing a descending index, we are more flexible in creating an index, you can create an appropriate index according to the sorting rules of business needs, so that you can query faster.

Of course, this article only talks about the principle, we must know the B+ tree used for sorting in Mysql, not the simple way I exemplified above, but even with the B+ tree principle is the same, comparing the size of the data.

One more thing, only the Innodb storage engine now supports descending indexing.

After reading the above content, is there a further understanding of the implementation method of the bottom layer of descending index in MySQL8? If you still want to learn more, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.