In-depth explanation of the principle of MySQL Innodb index

introduction

Looking back four years ago, when I was learning about MySQL indexes, the teacher said the following when talking about indexes:

An index is like the table of contents of a book. When a user searches for data through an index, it is like a user searching for a certain knowledge point in a chapter through a directory. This helps users effectively improve their search speed. Therefore, using indexes can effectively improve the overall performance of the database system.

Well, that’s actually true. However, after reading this statement, you may still think it is too abstract! Therefore, I would like to explain it in more detail, so this article was created!

It should be noted that what I said is only valid in MySQL's Innodb engine. The correctness in the Mysiam engine of Sql Server, Oracle, and Mysql may not be true!

InnoDB is the most commonly used storage engine for MySQL. Understanding the index of the InnoDB storage engine is of great benefit for daily work. The existence of the index is to speed up the retrieval of database row records.

What is an index?

Index is translated as a directory, which is used to quickly locate the data we want to find. For example, we compare a database to a book, and the index is the table of contents in the book. To find a certain interesting content in the book, we usually do not flip through the entire book to confirm where the content is. Instead, we use the table of contents to locate the page where the content chapter is located, and then directly flip to that page.

Let's take a look at the indexes in the database:

Full Table Scan vs Index Scan

Taking the dictionary as an example, a full table scan means that if we are looking for a certain word, we read the Xinhua Dictionary through and then find the word we want. The corresponding to a full table scan is an index search, which is to find the specific location of the data we want in the index part of the table, and then find all the data we want in the table.

OK, without further ado, let’s start talking!

text

Popular Science of Index

First introduce the concepts of clustered index and non-clustered index!

In the Mysql we usually use, we use the following statement

CREATE [UNIQUE|FULLTEXT|SPATIAL] INDEX index_name
 [USING index_type]
 ON tbl_name (index_col_name,...)
 
index_col_name:
 col_name [(length)] [ASC | DESC]

The created indexes, such as composite indexes, prefix indexes, and unique indexes, are all non-clustered indexes. In some books, they are also called secondary indexes. In the following text, we call it a non-clustered index, and its data structure is a B+ tree.

Well, there is no statement in MySQL to generate this clustered index separately. In Innodb, the data in MySQL is stored in the order of the primary key. Then the clustered index constructs a B+ tree according to the primary key of each table, and the leaf nodes store the row data of the entire table. Since the data in the table can only be sorted according to a B+ tree, a table can only have one clustered index.

In Innodb, the clustered index is the primary key index by default.

At this time, the smart readers should ask me

What if my table doesn't have a primary key?

The answer is: If there is no primary key, then build a clustered index according to the following rules:

When there is no primary key, a unique and non-empty index column will be used as the primary key, which becomes the clustered index of this table. If there is no such index, InnoDB will implicitly define a primary key as the clustered index.

ps: Do you still remember the difference between auto-increment primary key and uuid as primary key? Since the primary key uses a clustered index, if the primary key is an auto-incrementing ID, the corresponding data must also be stored adjacently on the disk, and the write performance is relatively high. If it is in the form of UUID, frequent insertions will cause InnoDB to frequently move disk blocks, and the write performance will be relatively low.

Introduction to indexing principles

First, let's take a table with a primary key, as shown below, pId is the primary key

Draw the structure diagram of the table as follows

As shown in the figure above, it is divided into two parts, the upper part is the B+ tree formed by the primary key, and the lower part is the real data on the disk! Then, when we execute the following statement

select * from table where pId='11'

Then, the execution process is as follows

As shown in the figure above, starting from the root, after 3 searches, the real data can be found. If you don't use an index, you have to scan the disk row by row until you find the data location. Obviously, using an index will be faster. However, when writing data, the structure of this B+ tree needs to be maintained, so the write performance will decrease!

OK, let's introduce a non-clustered index! We execute the following statement

create index index_name on table(name);

The structure diagram is as follows

Please note that a new B+ tree will be generated based on your index field. Therefore, every time we add an index, we increase the size of the table and take up disk storage space. However, pay attention to the leaf nodes. The leaf nodes of non-clustered indexes are not real data. Their leaf nodes are still index nodes, which store the value of the index field and the corresponding primary key index (clustered index).

If we execute the following statement

select * from table where name='lisi'

The structure diagram is as follows

It can be seen from the red line in the figure above that the search starts from the non-clustered index tree and then the clustered index is found. According to the clustered index, find the complete data in the B+ tree of the clustered index!

That

Why not query the clustered index tree?

Remember that our non-clustered index tree stores the value of the index field. If, at this time we execute the following statement

select name from table where name='lisi'

The structure diagram is as follows

As shown by the red line in the figure above, if the desired value is found in the non-clustered index tree, the clustered index tree will not be queried. Remember the indexing problem mentioned by the blogger in "The Correct Posture of Select":

When executing select col from table where col = ? and there is an index on col, the efficiency is several times faster than executing select * from table where col = ?!

After looking at the picture above, you should have a deeper understanding of this sentence.

So at this time, we execute the following statement, what will happen?

create index index_birthday on table(birthday);

The structure diagram is as follows

You see, adding one more index will generate one more non-clustered index tree. Therefore, many articles say that indexes cannot be added randomly. Because, there are as many non-clustered index trees as there are indexes! When you perform an insert operation, you need to maintain the changes of these trees at the same time! Therefore, if you have too many indexes, insert performance will degrade!

Summarize

Having said that, everyone should clearly understand the principle of indexing! The details may not be rigorous enough, but I think it is enough for a R&D person to understand this. After all, we are not professional DBAs.
I hope everyone gains something from it!