Take an in-depth study of the InnoDB data page of MySQL Principles

This article brings you relevant knowledge about InnoDB data pages in mysql principles, including relevant knowledge about page directories, page headers and file headers. I hope it will be helpful to everyone.

Introduction to different types of pages

It is the basic unit of InnoDBManaging storage space, The size of a page is generally It’s 16KB. InnoDBMany different types of pages are designed for different purposes, such as pages that store table space header information, pages that store Insert Buffer information, The page that stores INODE information, the page that stores undo log information, etc. Of course, if you haven’t heard any of the terms I mentioned, just think that I farted~ But it doesn’t matter a dime. We are not going to talk about these types of pages today. What we are focusing on is Those types of pages that store records in our table are officially called index (INDEX) pages. Since we have not yet understood what an index is, and the pages in these tables Records are what we call data in our daily lives, so for now we still call this page where records are stored data page.

Quick Browse of the Data Page Structure

The 16KB storage space represented by the data page can be divided into multiple parts, and different parts have different functions. Each part is shown in the figure:

As can be seen from the figure, the storage space of an InnoDB data page is roughly divided into There are 7 parts, some parts occupy a certain number of bytes, and some parts occupy an uncertain number of bytes. Below we use a table to roughly describe what content is stored in these 7 parts (just take a quick glance, we will talk about it in detail later):

Storage of records in the page

Among the 7 components of the page, the records we store ourselves will be # specified by us ##Row format is stored in the User Records section. But when the page is generated at the beginning, there is actually no User Records section. Whenever we insert a record, it will be from the Free Space section, which is the unused storage space. Apply for a record-sized space and divide it into the User Records part. When all the space in the Free Space part is replaced by the User Records part, it means this The page has been used up. If there are new records inserted, you need to apply for a new page. The diagram of this process is as follows:

User Records took a lot of effort in InnoDB. Where did I put the effort? Isn't it just to place the records one by one in the User Records section according to the specified line format? In fact, we have to start with the record header information of the record line format.

mysql> CREATE TABLE page_demo(
    ->     c1 INT,
    ->     c2 INT,
    ->     c3 VARCHAR(10000),
    ->     PRIMARY KEY (c1)
    -> ) CHARSET=ascii ROW_FORMAT=Compact;
Query OK, 0 rows affected (0.03 sec)

page_demo table has 3 Columns, of which the c1 and c2 columns are used to store integers, and the c3 column is used to store strings. It should be noted that we specify the c1 column as the primary key, so in the specific row format, InnoDB does not need to create the so-called row_id for us. The column is hidden. And we specified the ascii character set and the Compact row format for this table. So the schematic diagram of the row format recorded in this table is like this:

record header information The byte data is marked, indicating that it is very important. Let us once again browse the general meaning of each attribute in these record header information (we currently use the Compact line format) Demo):

由于我们现在主要在唠叨记录头信息的作用，所以为了大家理解上的方便，我们只在page_demo表的行格式演示图中画出有关的头信息属性以及c1、c2、c3列的信息（其他信息没画不代表它们不存在啊，只是为了理解上的方便在图中省略了～），简化后的行格式示意图就是这样：

下边我们试着向page_demo表中插入几条记录：

mysql> INSERT INTO page_demo VALUES(1, 100, 'aaaa'), (2, 200, 'bbbb'), (3, 300, 'cccc'), (4, 400, 'dddd');
Query OK, 4 rows affected (0.00 sec)
Records: 4  Duplicates: 0  Warnings: 0

为了方便大家分析这些记录在页的User Records部分中是怎么表示的，我把记录中头信息和实际的列数据都用十进制表示出来了（其实是一堆二进制位），所以这些记录的示意图就是：

看这个图的时候需要注意一下，各条记录在User Records中存储的时候并没有空隙，这里只是为了大家观看方便才把每条记录单独画在一行中。我们对照着这个图来看看记录头信息中的各个属性是啥意思：

• delete_mask

  这个属性标记着当前记录是否被删除，占用1个二进制位，值为0的时候代表记录并没有被删除，为1的时候代表记录被删除掉了。

  啥？被删除的记录还在页中么？是的，摆在台面上的和背地里做的可能大相径庭，你以为它删除了，可它还在真实的磁盘上[摊手]（忽然想起冠希～）。这些被删除的记录之所以不立即从磁盘上移除，是因为移除它们之后把其他的记录在磁盘上重新排列需要性能消耗，所以只是打一个删除标记而已，所有被删除掉的记录都会组成一个所谓的垃圾链表，在这个链表中的记录占用的空间称之为所谓的可重用空间，之后如果有新记录插入到表中的话，可能把这些被删除的记录占用的存储空间覆盖掉。

• min_rec_mask

  B+树的每层非叶子节点中的最小记录都会添加该标记，什么是个B+树？什么是个非叶子节点？好吧，等会再聊这个问题。反正我们自己插入的四条记录的min_rec_mask值都是0，意味着它们都不是B+树的非叶子节点中的最小记录。

• n_owned

  这个暂时保密，稍后它是主角～

• heap_no

  这个属性表示当前记录在本页中的位置，从图中可以看出来，我们插入的4条记录在本页中的位置分别是：2、3、4、5。是不是少了点啥？是的，怎么不见heap_no值为0和1的记录呢？

  这其实是设计InnoDB的大叔们玩的一个小把戏，他们自动给每个页里边儿加了两个记录，由于这两个记录并不是我们自己插入的，所以有时候也称为伪记录或者虚拟记录。这两个伪记录一个代表最小记录，一个代表最大记录，等一下哈~，记录可以比大小么？

  是的，记录也可以比大小，对于一条完整的记录来说，比较记录的大小就是比较主键的大小。比方说我们插入的4行记录的主键值分别是：1、2、3、4，这也就意味着这4条记录的大小从小到大依次递增。

• 但是不管我们向页中插入了多少自己的记录，设计InnoDB的大叔们都规定他们定义的两条伪记录分别为最小记录与最大记录。这两条记录的构造十分简单，都是由5字节大小的记录头信息和8字节大小的一个固定的部分组成的，如图所示

  

  由于这两条记录不是我们自己定义的记录，所以它们并不存放在页的User Records部分，他们被单独放在一个称为Infimum + Supremum的部分，如图所示：

  

  从图中我们可以看出来，最小记录和最大记录的heap_no值分别是0和1，也就是说它们的位置最靠前。

• record_type

  这个属性表示当前记录的类型，一共有4种类型的记录，0表示普通记录，1表示B+树非叶节点记录，2表示最小记录，3表示最大记录。从图中我们也可以看出来，我们自己插入的记录就是普通记录，它们的record_type值都是0，而最小记录和最大记录的record_type值分别为2和3。

  至于record_type为1的情况，我们之后在说索引的时候会重点强调的。

• next_record

  这玩意儿非常重要，它表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量。比方说第一条记录的next_record值为32，意味着从第一条记录的真实数据的地址处向后找32个字节便是下一条记录的真实数据。如果你熟悉数据结构的话，就立即明白了，这其实是个链表，可以通过一条记录找到它的下一条记录。但是需要注意注意再注意的一点是，下一条记录指得并不是按照我们插入顺序的下一条记录，而是按照主键值由小到大的顺序的下一条记录。而且规定 Infimum记录（也就是最小记录） 的下一条记录就是本页中主键值最小的用户记录，而本页中主键值最大的用户记录的下一条记录就是 Supremum记录（也就是最大记录） ，为了更形象的表示一下这个next_record起到的作用，我们用箭头来替代一下next_record中的地址偏移量：

  

  从图中可以看出来，我们的记录按照主键从小到大的顺序形成了一个单链表。最大记录的next_record的值为0，这也就是说最大记录是没有下一条记录了，它是这个单链表中的最后一个节点。如果从中删除掉一条记录，这个链表也是会跟着变化的，比如我们把第2条记录删掉：

  mysql> DELETE FROM page_demo WHERE c1 = 2;
  Query OK, 1 row affected (0.02 sec)

  Copy after login

  删掉第2条记录后的示意图就是：

  

  从图中可以看出来，删除第2条记录前后主要发生了这些变化：

  • 第2条记录并没有从存储空间中移除，而是把该条记录的delete_mask值设置为1。
  • 第2条记录的next_record值变为了0，意味着该记录没有下一条记录了。
  • 第1条记录的next_record指向了第3条记录。
  • 还有一点你可能忽略了，就是最大记录的n_owned值从5变成了4，关于这一点的变化我们稍后会详细说明的。

  所以，不论我们怎么对页中的记录做增删改操作，InnoDB始终会维护一条记录的单链表，链表中的各个节点是按照主键值由小到大的顺序连接起来的。

再来看一个有意思的事情，因为主键值为2的记录被我们删掉了，但是存储空间却没有回收，如果我们再次把这条记录插入到表中，会发生什么事呢？

mysql> INSERT INTO page_demo VALUES(2, 200, 'bbbb');
Query OK, 1 row affected (0.00 sec)

我们看一下记录的存储情况：

从图中可以看到，InnoDB并没有因为新记录的插入而为它申请新的存储空间，而是直接复用了原来被删除记录的存储空间。

Page Directory（页目录）

现在我们了解了记录在页中按照主键值由小到大顺序串联成一个单链表，那如果我们想根据主键值查找页中的某条记录该咋办呢？比如说这样的查询语句：

SELECT * FROM page_demo WHERE c1 = 3;

最笨的办法：从Infimum记录（最小记录）开始，沿着链表一直往后找，总有一天会找到（或者找不到[摊手]），在找的时候还能投机取巧，因为链表中各个记录的值是按照从小到大顺序排列的，所以当链表的某个节点代表的记录的主键值大于你想要查找的主键值时，你就可以停止查找了，因为该节点后边的节点的主键值依次递增。

This method is no problem when the number of records stored in the page is relatively small. For example, our table now only has 4 records that we have inserted, so we can only find at most. All records can be traversed 4 times, but if a page stores a lot of records, such a search will still have a loss in performance, so we say that this kind of traversal search is a Stupid way. But who are the uncles who designed InnoDB? Can they use such a stupid method? Of course, they have to design a better search method. They found inspiration from the table of contents of the book.

When we usually want to find something in a book, we usually look at the table of contents first, find the page number of the book corresponding to the content we want to find, and then go to the corresponding page number to view the content. The uncles who designed InnoDB also made a similar directory for our records. Their production process is as follows:

1. Convert all normal records (including The largest and smallest records (excluding records marked as deleted) are divided into several groups.

2. The n_owned attribute in the header information of the last record of each group (that is, the largest record in the group) indicates how many records the record has. , that is, how many records there are in this group.

3. Extract the address offset of the last record of each group separately and store it in order near the end of page . This place is so-called Page Directory, which is Page Directory (At this time, you should go back to the top and look at the pictures of each part of the page). These address offsets in the page directory are called slot (English name: Slot), so this page directory is composed of slot.

For example, there are currently 6 normal records in the page_demo table. InnoDB will divide them into two groups. In the first group There is only one minimum record, and the second group contains the remaining 5 records. Look at the diagram below:

We need to pay attention to the following points from this picture:

• Now there are two slots in the page directory section, which means that our records are divided into two groups, The value in slot 1 It is 112, which represents the address offset of the largest record (that is, counting from byte 0 of the page and counting to 112 bytes); the value in slot 0 is 99, represents the address offset of the smallest record.

• Note the n_owned attribute in the header information of the minimum and maximum records

  • The n_owned value of the minimum record is 1, which means that there are only 1 records in the group ending with the minimum record, which is the minimum record itself.
  • The n_owned value of the largest record is 5, which means that there are only 5 records in the group ending with the largest record, including The maximum record itself also has 4 records inserted by ourselves. Address offsets like

99 and 112 are very unintuitive. We use arrows to point to numbers instead of numbers, like this It’s easier for us to understand, so the modified schematic diagram is like this:

Oh, it looks weird. Such a messy picture is really intolerable for my obsessive-compulsive disorder. Then we will temporarily ignore the arrangement of each record on the storage device, and simply look at the relationship between these records and the page directory from a logical perspective:

It looks pleasing to the eye. There are too many! Why is the n_owned value of the smallest record 1, while the n_owned value of the largest record is 5? Is there anything fishy here?

Yes, the uncles who designed InnoDB have regulations on the number of records in each group: the group with the smallest record can only have 1 records, the number of records owned by the group where the largest record is located can only be between 1~8, and the number of records in the remaining groups The range can only be between 4~8. Therefore, grouping is carried out according to the following steps:

• Initially, there are only two records in a data page, the minimum record and the maximum record, and they belong to two groups.

• Every time a record is inserted, the slot whose primary key value is greater than the primary key value of this record and has the smallest difference will be found from the page directory, and then the slot will be The n_owned value of the record corresponding to this slot is increased by 1, indicating that another record has been added to this group until the number of records in this group is equal to 8.

• 在一个组中的记录数等于8个后再插入一条记录时，会将组中的记录拆分成两个组，一个组中4条记录，另一个5条记录。这个过程会在页目录中新增一个槽来记录这个新增分组中最大的那条记录的偏移量。

由于现在page_demo表中的记录太少，无法演示添加了页目录之后加快查找速度的过程，所以再往page_demo表中添加一些记录：

mysql> INSERT INTO page_demo VALUES(5, 500, 'eeee'), (6, 600, 'ffff'), (7, 700, 'gggg'), (8, 800, 'hhhh'), (9, 900, 'iiii'), (10, 1000, 'jjjj'), (11, 1100, 'kkkk'), (12, 1200, 'llll'), (13, 1300, 'mmmm'), (14, 1400, 'nnnn'), (15, 1500, 'oooo'), (16, 1600, 'pppp');
Query OK, 12 rows affected (0.00 sec)
Records: 12  Duplicates: 0  Warnings: 0

哈，我们一口气又往表中添加了12条记录，现在页里边就一共有18条记录了（包括最小和最大记录），这些记录被分成了5个组，如图所示：

因为把16条记录的全部信息都画在一张图里太占地方，让人眼花缭乱的，所以只保留了用户记录头信息中的n_owned和next_record属性，也省略了各个记录之间的箭头，我没画不等于没有啊！现在看怎么从这个页目录中查找记录。因为各个槽代表的记录的主键值都是从小到大排序的，所以我们可以使用所谓的二分法来进行快速查找。5个槽的编号分别是：0、1、2、3、4，所以初始情况下最低的槽就是low=0，最高的槽就是high=4。比方说我们想找主键值为6的记录，过程是这样的：

1. 计算中间槽的位置：(0+4)/2=2，所以查看槽2对应记录的主键值为8，又因为8 > 6，所以设置high=2，low保持不变。

2. 重新计算中间槽的位置：(0+2)/2=1，所以查看槽1对应的主键值为4，又因为4 ，所以设置<code>low=1，high保持不变。

3. 因为high - low的值为1，所以确定主键值为6的记录在槽2对应的组中。此刻我们需要找到槽2中主键值最小的那条记录，然后沿着单向链表遍历槽2中的记录。但是我们前边又说过，每个槽对应的记录都是该组中主键值最大的记录，这里槽2对应的记录是主键值为8的记录，怎么定位一个组中最小的记录呢？别忘了各个槽都是挨着的，我们可以很轻易的拿到槽1对应的记录（主键值为4），该条记录的下一条记录就是槽2中主键值最小的记录，该记录的主键值为5。所以我们可以从这条主键值为5的记录出发，遍历槽2中的各条记录，直到找到主键值为6的那条记录即可。由于一个组中包含的记录条数只能是1~8条，所以遍历一个组中的记录的代价是很小的。

所以在一个数据页中查找指定主键值的记录的过程分为两步：

1. 通过二分法确定该记录所在的槽，并找到该槽所在分组中主键值最小的那条记录。

2. 通过记录的next_record属性遍历该槽所在的组中的各个记录。

Page Header（页面头部）

设计InnoDB的大叔们为了能得到一个数据页中存储的记录的状态信息，比如本页中已经存储了多少条记录，第一条记录的地址是什么，页目录中存储了多少个槽等等，特意在页中定义了一个叫Page Header的部分，它是页结构的第二部分，这个部分占用固定的56个字节，专门存储各种状态信息，具体各个字节都是干嘛的看下表：

The above is the detailed content of Take an in-depth study of the InnoDB data page of MySQL Principles. For more information, please follow other related articles on the PHP Chinese website!