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

This article shows you what the index supported by the MySQL InnoDB storage engine architecture is. The content is concise and easy to understand, which will definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.

As we all know, in the InnoDB engine of MySQL, in order to improve the query speed, you can add an index to the field. The index is like the catalog of a book, through which page the content of the book is located.

The following indexes are supported by InnoDB:

B+ tree index

Full-text index

Hash indexing

This paper focuses on the B+ tree index.

1. Data structure-- B + tree

I believe you have learned binary search, binary tree and balanced binary tree in the course of data structure in the university. In a group of ordered data, binary search can be used to retrieve data quickly in the complexity of log2N. Balanced binary tree is evolved on the basis of binary search tree, which solves the problem of transforming binary search tree into single linked list in extreme cases. What about the B + tree? Let's look at the structure of the B+ tree.

In the B+ tree, the data is stored in the leaf node from bottom to large, which can be obtained from the B+ tree above. The height of this B+ tree is 2, each page can store 4 pieces of data, fan out is 5, the first layer is the index page, and the second layer is the data page. The essence of the database B + tree index is the implementation of the B + tree in the database, and the height of the B + tree is generally limited to 2-4 layers, and the IO operation of the disk only needs 2-4 times, so it is very fast to find data on the index.

Second, B + tree index

1. Clustered index

In the InnoDB engine, there is a clustered index, usually primary key. If the specified primary key,InnoDB is not shown, the unique index of the first not null of the table will be selected by default as the primary key. If not, a 6-byte rowid will be automatically created as the primary key.

The image above is a schematic diagram of a clustered index. from the image above, we can see that the tree is divided into two tiers, the first layer is the index page, and the second layer is the data page, where the data is actually stored. We can also conclude that the index page does not store data but an offset to the real data, while the real data is stored in the data page of the second layer, so if a SQL statement hits the index, it only hits the data of the index page, and then uses the index page to find the page where the real data is located.

The storage of clustered indexes is not physically continuous, but logically continuous, because pages and pages are maintained through two-way linked lists, and row records in each page are also maintained through two-way linked lists. Why two-way linked list? This is because it is convenient to query and sort the range, such as finding the offset of the data page where an index is located, traversing the linked list directly or traversing the linked list in reverse order. such as

Select * from table where id > 10 and id

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.