Query process of MySQL secondary index

The cluster index is innodb The default primary key based index structure is created , And the data in the table is directly placed in the cluster index , Data pages as leaf nodes ：

Data search based on primary key ： The binary search starts from the root node of the cluster index , Find the corresponding data page all the way , Based on the page directory, you can directly locate the primary key target data .

If you want to index other fields , Even a joint index based on multiple fields , What is the index structure at this time ？

Suppose you index other fields , Such as name、age And so on , It's all the same principle . For example, when you insert data ：

• Insert the complete data into the data page of the leaf node of the cluster index , At the same time, maintain the cluster index
• Index your other fields , Rebuild another B+ Trees

For example, you are based on name Fields create an index , When inserting data , Will make another one B+ Trees ,B+ The leaf node of the tree is also a data page , But only the primary key field and... Are placed in the data page name Field ：

This is another index independent of clustering name Field B+ Tree index , The data page of its leaf node only stores the primary key and name field value .

The overall sorting rule is the same as that of the cluster index according to the primary key , namely ：

• In the data page of the leaf node name Values are sorted
• In the next data page name All field values ＞ In the previous data page name field value

name Index of field B+ The tree will also build multi-level index pages , In the index page ：

• The page number of the next layer
• Minimum name field value , according to name Sort field values .

So if you follow name Field query data , The process is the same , from name The root node of the index tree starts , Look down one layer at a time , Keep finding the data page of the leaf node , Locate the name The primary key value corresponding to the field value .

And then for

select * from t where name='xx'

This kind of sentence , First, according to name Values in name Look in the index tree , Find the leaf node , You can only find the corresponding primary key value , And can't find all the fields of this row of data .

So I need to return the form ： It also needs to be based on the primary key value , Then go to the cluster index, starting from the root node , Find the data page of the leaf node , Locate the complete data row corresponding to the primary key value , Only then can select * All field values to be taken out .

Joint index

such as name+age, The operation process is the same , Building an independent B+ Trees , The data pages of leaf nodes are stored id+name+age after , Press default name Sort ,name Just press the same age row , Between different data pages name+age The same goes for sorting values .

And then this name+age Joint index of B+ The index page of the tree stores ：

• The page number of the next layer node
• The smallest name+age Value

So when you're based on name+age When searching , Will go name+age Union index tree , Search for primary key , Then search the cluster index according to the primary key .

summary

That's all InnoDB The realization principle of index , It's about building B+ Trees , Layer by layer binary search . Different indexes create different B+ Trees , Then add, delete and modify ：

• Update the data in the data page
• Maintain all your indexes