B+ tree (3) clustered index, secondary index -- MySQL from entry to proficiency (XV)

The last article said b+ Tree index scheme , Because use the previous dichotomy to find , The prerequisite is that the index must be next to , Inspired by the number of user records , The same directory record page as the user record real data page is established ( Indexes ), And the top three floors , The highest level is the root node , At the bottom is the leaf node , Others are non leaf nodes ,record_type by 0 Represents ordinary data page ,1 Represents the catalog record page .

B+ Tree index scheme (2) --mysql From entry to mastery （ fourteen )

Cluster index

What we introduced above b+ The tree itself is a directory , Or is itself an index , He has two characteristics ：

Use the primary key value size to sort records and pages ：1） The bidirectional linked list between pages is sorted by the primary key value .2） The data in the page is also connected into a single Necklace table through the primary key value .3） The directory record page is also connected into a two-way linked list through the primary key value .

B+ The leaf node of the tree stores the complete user record information , Including hidden pages .

When these two characteristics are met , This is called clustered index , All complete records are recorded in the leaf node . This does not need us to use sql Use of statement display index establish ,innoDB The engine will automatically create a clustered index for us . stay innoDB in , Cluster index is the storage method of data ( All records are in leaf nodes ), That is, index is data , Data is index .

Secondary indexes (secondary index)

The above clustered index is only used when querying the primary key , It works , So cluster index is also called primary key index . Secondary index is also called auxiliary index , Characteristics of secondary index ：

Use the columns in our table c2 Sort records and pages ：1） The two-way linked list between pages passes c2 Column sorting .2） The data in the page passes c2 Columns are connected into a one-way linked list .3） The directory record page is also through c2 Columns are connected into a two-way linked list .

Secondary index B+ The leaf node of the tree is not the user storage data , Only store c2 Column + His primary key .

The directory page of the secondary index is no longer the primary key + Page number , It is c2 Column + Page number .

When we cluster index queries, it is the process ?

First, the root node queries our non leaf nodes , Non leaf nodes are querying page numbers through primary keys , Find the bottom page slot by binary search , Traverse the data in the slot to find all the values we need .

The secondary index lookup process ？

First locate the root directory node to us c2 Nonleaf node , On the basis of c2 Page number corresponding to non leaf points , Find the corresponding c2 Columns and primary keys , Finally, go back to the table , Re pass c2 Query the primary key of b+ Trees , Through clustering index .

That is, when we use secondary index , When indexing , You need to traverse two b+ Trees . Then why do I need to return to the table , It's really possible to put all the data pages in c2 At the leaf node of the column , But this is related to the data redundancy of the leaf node of the component , Too much memory .