[MySQL from introduction to proficiency] [advanced chapter] (IX) precautions for InnoDB's b+ tree index

Hello! , I'm Manon Feige , Thank you for reading this article , Welcome to three links with one button .
1. Python Basic column , Basic knowledge in a net ,9.9 Yuan can't buy a loss , I can't buy it . Python From entry to mastery
️ 2. Python Crawler column , Systematically learn the knowledge points of reptiles .9.9 Yuan can't buy a loss , I can't buy it .python Reptile beginner level
️ 3. Ceph actual combat , Everything from principle to actual combat . Ceph actual combat
️ 4. Java Introduction to high concurrency programming , Punch in to learn Java High concurrency . Java Introduction to high concurrency programming
5. Take a stroll around the community , Weekly benefits , There are surprises every week . Manon Feige community , Leap plan
The whole network has the same name 【 Manon Feige 】 Welcome to your attention , personal VX: wei158556

1. brief introduction

In the last article, we introduced clustering index , Non clustered index and federated index 【MySQL From entry to mastery 】【 Advanced 】（ 8、 ... and ） Cluster index & Nonclustered index & Joint index . We are introducing B+ When indexing trees , First, draw the leaf nodes that store user records , Then draw the inner node that stores the directory records , actually B+ The formation process of trees is not like this .

2. Environmental Science

Environmental Science	edition
Red Hat	4.8.5-39
MySQL	5.7

3. The location of the root page remains unchanged for ten thousand years

B+ The actual formation process of trees is like this ：

• Whenever a table is created B+ Tree index （ Clustered indexes are not artificially created , By default, there is ） When , Will create a... For this index The root node page . When there is no data in the table at first , Every B+ Corresponding to tree index The root node There are no user records in , There are no catalog entry records .
• When a user record is subsequently inserted into the table , First store the user record in this The root node in .
• When available in the root node When space runs out Continue inserting records , All records in the root node will be copied to a newly allocated page , such as page a in , Then the new page is Page splitting The operation of , Get another new page , Not as good as page b. At this time, the newly inserted record is based on the key value （ That is, the primary key value in the cluster index , The value of the corresponding index column in the secondary index ） The size of will be allocated to page a perhaps page b in , and The root node It is upgraded to a page that stores directory item records .
  This process pays special attention to ： One B+ The root node of the tree index is from the date of birth , It won't move . In this way, as long as we build an index on a table , Then the page number of its root node will be recorded somewhere , And then everything InnoDB When the index engine is used , Will take out the page number of the root node from that fixed place , To access this index .

4. Uniqueness of directory records in internal nodes

We know B+ The contents of the directory entry record in the inner node of the tree index are Index columns + Page number The collocation of , But this collocation is not rigorous for the secondary index , Also take index_demo Table as an example , Suppose the data in this table is like this .

id	age	name
1	30	Zhou
3	30	Wang
5	30	Grandchildren
7	30	Li

If the contents of the directory entry record in the secondary index are only Index columns + Page number If you match it , So for age Column after indexing B+ Trees should grow like this ：

If we want to insert a new line of record , among id,age,name The values of ：（9,30, Liu ）, Then you are modifying this age The secondary index established by the column corresponds to B+ When I was a tree, I ran into a big problem ： because page 3 The directory entry records stored in are created by age Column + Page number The value of , page 3 Corresponding to the two directory entry records in age The values of the columns are 30, And the new record we inserted age The value of the page is also 30, So should our newly inserted record be placed in page 4 in , Or should we put it in page 5 Middle ,
In order that the newly inserted record can find itself on that page , We need to Guaranteed at B+ The directory entry records of nodes in the same layer of the tree are unique except for the page number field . Therefore, the content of the directory entry record of the inner node of the secondary index is actually composed of three parts .

1. Value of index column
2. Primary key value
3. Page number
   That is, we add the primary key value to the directory entry records in the nodes in the secondary index , So you can make sure B+ Each directory entry record in each layer node of the tree is unique except for the page number field , So we are for age The diagram after the secondary index of the column should actually look like this ：
   

Then we insert when , Because of the page 3 The directory entry records stored in are created by age Column + Primary key + Page number The value of , You can put the newly recorded age Column The value of and page 3 Of each catalog item record in age Column For comparison , If age Column If the value of is the same , You can then compare the primary key values , because B+ Records of different directory items in the same layer of the tree age Column + Primary key The value of must be different , Therefore, it is certain that the only directory entry record can be located in the end , In this case, it is finally determined that the new record should be inserted into the page 5 in .

5. A page stores at least 2 Bar record

One B+ The tree can easily store hundreds of millions of records with very few levels , The query speed is quite good , This is because B+ A tree is essentially a large multi-level directory , When passing through a directory, many invalid subdirectories will be filtered out , Until you finally access the directory where the real data is stored , What is the effect of storing only one subdirectory in a large directory ？ That is, there are many directory levels , And only one record can be stored in the last directory where the real data is stored . It took a long time to store only one real user record , therefore InnoDB A data page can store at least two records .

summary

Necessary for interview InnoDB Of B+ Considerations for tree indexing , The location of the root page remains unchanged for ten thousand years , The directory entry record in the inner node is unique , A page stores at least 2 Bar record .