B+ tree (4) joint index -- MySQL from entry to proficiency (16)

The last article introduced the primary key index ( Cluster index ), Secondary indexes ( Non primary key index , Secondary index ), The primary key index query queries the corresponding data page directory through the root directory record . The secondary index query first queries the column + The directory of page names is not a leaf node , Then the leaf node is queried , At this moment, the primary key and column are stored on the leaf node , Query the whole data through the primary key .

B+ Trees (3) Cluster index , Secondary indexes --mysql From entry to mastery （ 15、 ... and )

Joint index

Joint index is also called composite index , Let's say we want b+ Tree press c2,c3 Sort the size of two columns , That means ：1） According to the first c2 Sort .2）c2 In the same case , Press c3 Sort .

So now the bottom leaf node records ：c2,c3, The primary key corresponding to it c1, Directory records non leaf nodes record c2,c3 And page name , According to the first c2 Sort , If the same , Just press the c3 Sort . Its essence is also a secondary index , But the difference is ：

There is only one joint index b+ Trees .

If c2,c3 There are two indexes respectively b+ Trees .

InnoDB Index tree considerations ：

The root node remains unchanged

B+ The formation of trees ,1） Create a primary key index for the new table ( Cluster index ), Clustered indexes are not artificially created , By default, there is , At this point, the root node page will be created , There's no data .2） Then insert the user record data , Put the data into the root node .3） When the root node space runs out , At this moment, perform the page splitting operation , Get a new page , At this moment, the directory record node will put the primary key value and page number or the column value and page number of the secondary index , The bottom leaf node puts user records and primary key values , Or primary key value and column value , The root node is upgraded to the directory record root node .

Uniqueness of internal node directory entries

The inner node of the secondary index stores column values , But because the column value , For example, names are not unique , There may be two or more names with the same name , At this time, how to identify his uniqueness , Therefore, the secondary index stores more than column values in the directory page + Page name , It will also bring the unique primary key of the current row record , So the contents stored in the inner node are column values + Primary key + Page number .

A page stores at least two records

We know b+ As long as the tree has three levels, it can store huge data , Query efficiency is very high , Every time you query down, you will filter out many unnecessary subdirectories , What is the effect if only one subdirectory is placed on a large directory page ？ There will be a lot of hierarchical directories , And there is only one piece of data in the last user record . therefore innoDB Set to store at least two pieces of data , This is also the conclusion we said when we talked about row format .（ When there is only one column in the table , Without row overflow , How many bytes can be saved ,65535 Bytes ）