Make writing a habit together! This is the 11th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

When we talk about indexes, we usually talk about the following three types of indexes

  • B + several indexes
  • The full text indexing
  • The hash index

The hash index is mainly used to build an adaptive hash index to deal with some hot rows.

B + tree index

Clustering index

Clustered index is a B+ tree constructed according to the primary key of each table, and leaf nodes store row records of the whole table. Leaf nodes of clustered index are also called data pages.

The leaves of a B+ tree are bidirectionally linked, ensuring that they can be read sequentially without being stored sequentially at the physical level (which would be expensive).

Clustered indexes have two benefits

It is quick to sort and range lookups for primary keys, the former because bidirectional lists do not need sort and are themselves ordered. The latter is because the scope query can select the scope of the page through the previous tiers of nodes

Non-clustered index

For non-clustered indexes, leaf nodes do not contain all the data for row records. The leaf node contains only a bookmark to the leaf node of the clustered index, in addition to the key value.

The InnoDB storage engine iterates through the secondary index and obtains the primary key to the primary key index through leaf level Pointers, and then finds a complete row record through the primary key index.

B+ tree splitting

Since primary keys are mostly likely to increment, splitting in the middle is likely to result in wasted space. So InnoDB decides whether to split left or right based on some information in the Page Header

If the number of records to insert into the same direction is 5, and is currently located (cursor) to record (insert the InnoDB storage engine, you need to locate, location of the record to be inserted into the previous records) after three records, records of the split point for locating the record after the third records, Otherwise, the split-point record is the record to be inserted.