[advanced MySQL] index details (I): index data page structure

InnoDB Data page structure of

summary

InnoDB Many different types of... Have been designed for different purposes page , For example, the page storing the header information of the table space , Deposit Insert Buffer Pages of information , Deposit INODE Pages of information , Deposit undo Page of log information, etc . The page used to store user saved data is innoDB Basic storage structure ： Index page .（ Data pages ）.

It is InnoDB The basic unit for managing storage space , Brush set （ From memory to hard disk ）、 Read operation , One page at a time .

The maximum page size is 16KB

innoDB The index data structure of is B+ Trees , Each node of the tree is “ page ”,B+ The pages at the same level of the tree are connected by two-way linked lists .

A data page will contain the above parts , among ,（ Minimum record 、 Maximum record 、 User record 、 Free space ）, Record for line （ Self made words , That is, the structure of line format is observed during storage ）.

Introduction to page structure

File header

File Header Common for all types of pages , In other words, different types of pages will be File Header As the first component , It describes some information that is common to all kinds of pages , For example, what's the number of this page , It's the previous page 、 Who's next . This part occupies a fixed space 38 Bytes

FIL_PAGE_SPACE_OR_CHKSUM
This represents the check sum of the current page （checksum）.

For very long byte strings , Will pass some algorithm （ such as MD5） To calculate / Compress to a shorter value to represent , This is the checksum .

Compare whether the two data are the same , You can first compare the checksums , If the checksums are different , Then the data must be different , It can greatly reduce the space and time for comparison .

FIL_PAGE_TYPE
This represents the current situation page The type of , InnoDB Divide pages into different types for different purposes , The type of data page where we store records is actually FIL_PAGE_INDEX , It's called Index page .

At the end of the file

There is also a checksum field , Used to compare with the checksum of the file header .

To ensure that the data is saved completely when brushing the disk . Prevent the brush plate from being brushed halfway , power failure 、 Downtime . such

Page directory

innoDB The data will be grouped , The of each group The last record The address offset of is extracted separately and stored in order near the end of the page , This place is called Page Directory , That is to say Page directory . These address offsets in the page directory are called Slot （ English name ： Slot ）, So this page directory is made up of Slot Composed of .

When we are looking for data , When locating the data on a page , How to quickly find the data in the page ？

We know , The data in the page consists of a linked list , If the search can only be traversed one by one , This is slow , At this point, there is a page directory .

1. innoDB User records will be grouped , among , The smallest record is a single group , The largest record is a group with the tail record . The maximum number of groups where records are located is 1-8 strip , The group where ordinary records are located 4-8 strip .
2. When adding data to it , Will be in Page directory Larger than the current primary key value found in , And the group with the closest value , And record the corresponding n_owned It's worth adding 1.
3. until The number of one group reaches 8, At this time, inserting data into the group will split the records in the group into two groups , A group of 4 One group 5 strip , A slot will be added to the page directory accordingly .

So the process of finding the record with the specified primary key value in a data page is divided into two steps ：

1. The slot in which the record is located is determined by dichotomy , And find the record with the smallest primary key value in the slot .
2. By recording next_record Property to traverse the records in the group where the slot is located

Page header

In order to get the status information of records stored in a data page , For example, how many records have been stored in this page , What is the address of the first record , How many slots are stored in the page directory and so on , Specially defined a name in the page Page Header Part of , It's a page The second part of the structure , This part occupies a fixed space 56 Bytes , Special storage of various status information . The components of the page header are as follows ：

PAGE_DIRECTION

If the primary key value of a newly inserted record is larger than that of the previous record , We say the insertion direction of this record is on the right , The opposite is on the left . The state used to indicate the insertion direction of the last record is PAGE_DIRECTION .

PAGE_N_DIRECTION

Suppose that the direction of inserting new records several times in succession is the same , InnoDB The number of records inserted in the same direction will be recorded , Use this number PAGE_N_DIRECTION This state means . Of course , If the insertion direction of the last record changes , The value of this state will be cleared and counted again .