不同类型的页简介

页是 InnoDB 存储引擎管理存储空间的基本单位，一个页的大小一般是 16 KB。
InnoDB 存储引擎为了不同的目的而设计了许多种不同类型的页，
比如：存放表空间头部信息的页，存放 Insert Buffer 信息的页，存放 inode 信息的页，存放 undo 日志信息的页等。
存放表中记录的那种类型的页，官方称这种存放记录的页为索引（index）页，鉴于目前还没有了解过索引，而这些表中的记录就是我们日常口中所称的数据，所以目前还是叫这种存放记录的页为数据页吧。

数据页结构的快速浏览

数据页代表的这块 16KB 大小的存储空间大致被划分成 7 个部分，
不同的部分有不同的功能，
有的部分占用的字节数是确定的，有的部分占用的字节数是不确定的。
下表大致描述这 7 个部分存储的内容

记录在页中的存储

在页的 7 个组成部分中，我们自己存储的记录会按照我们指定的行格式存储到 User Records 部分。
但是在一开始生成页的时候，其实并没有 User Records 这个部分，
每当我们插入一条记录，都会从 Free Space 部分，也就是尚未使用的存储空间中申请一个记录大小的空间划分到 User Records部分，
当 Free Space 部分的空间全部被 User Records 部分替代掉之后，也就意味着这个页使用完了，
如果还有新的记录插入的话，就需要去申请新的页，这个过程的图示如下：

为了更好的管理在 User Records 中的这些记录，InnoDB 存储引擎费了一番力气，
这话还得从记录行格式的记录头信息中说起。
记录头信息的秘密
我们需要建一个数据库表用于演示说明：

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 表有 3 个列：

• c1 和 c2 列是用来存储整数的
• c3 列是用来存储字符串的

需要注意的是：我们把 c1 列指定为主键，所以在具体的行格式中 InnoDB 存储引擎不会去创建 row_id 隐藏列了。
而且我们为这个表指定了 ascii 字符集以及 Compact 的行格式，
所以这个表中记录的行格式示意图如下：

InnoDB 记录结构
下边我们向 page_demo 表中插入几条记录：

insert into page_demo values(1, 100, ‘aaaa’), (2, 200, ‘bbbb’), (3, 300, ‘cccc’), (4, 400, ‘dddd’);

为了方便观察记录在页的 User Records 部分中是怎么表示的，
下图把记录中信息用十进制表示出来了（其实是一堆二进制位）
变长字段长度列表和 null 值列表虽然没有画出，但实际存在，
下图是 User Records 部分：

详细讲解记录头信息
delete_mask

• 这个属性表示：当前记录是否被删除，占用 1 个二进制位
• 值为 0 的时候代表记录没有被删除，为 1 的时候代表记录被删除
• 被删除的记录之所以不立即从磁盘上移除，是因为移除它之后把其他的记录在磁盘上重新排列需要性能消耗
• 所有被删除掉的记录都会组成一个垃圾链表，在这个链表中的记录占用的空间称为可重用空间，之后如果有新记录插入到数据库表中的话，可能会把这些被删除的记录占用的存储空间覆盖掉。

  小贴士： 将这个 delete_mask 位设置为 1 和将被删除的记录加入到垃圾链表中其实是两个阶段， 后边介绍事务的文章会详细说明删除操作的详细过程。

min_rec_mask

• B+ 树的每层非叶子节点中的最小记录都会添加该标记，占用 1 个二进制位
• 值为 0 的时候代表记录不是，值为 1 的时候代表记录是

n_owned

• 后面有详细说明

heap_no

• 这个属性表示：当前记录在本页中的位置
• 从图中可以看出来，我们插入的 4 条记录在本页中的位置分别是：2、3、4、5
• 设计 InnoDB 存储引擎的人，他们自动给每个页里加了两个记录，称为伪记录或者虚拟记录
• 不管我们向页中插入了多少自己的记录，设计 InnoDB 存储引擎的人规定他们定义的两条伪记录分别为：最小记录与最大记录
• 最小记录和最大记录的 heap_no 值分别是 0 和 1，也就是说它们的位置最靠前

• 对于一条完整的记录来说，比较记录的大小就是比较主键的大小

  小贴士： 强调了对于一条完整的记录来说，比较记录的大小就相当于比的是主键的大小。 后边会介绍只存储一条记录的部分列的情况

• 伪记录并不存放在页的 User Records 部分，他们被单独放在一个称为 Infimum + Supremum 的部分，

• 这两条伪记录的构造十分简单，都是由 5 个字节大小的记录头信息和 8 字节大小的固定部分组成的（无变长字段长度列表 和 null 值列表），下图所示：

record_type

• 这个属性表示：当前记录的类型
• 一共有 4 种类型的记录，值的对应情况如下
  • 0 表示普通记录
  • 1 表示B+树非叶节点记录
  • 2 表示最小记录
  • 3 表示最大记录
• 从图中可以看出，我们上面执行 insert 语句插入的记录是普通记录
• record_type 为 1 的情况，后面讲解索引的文章会重点强调

next_record

• 这个属性表示：从当前记录的真实数据到下一条记录的真实数据的地址偏移量
• 比方说：第一条记录的 next_record 值为 32，意味着从第一条记录的真实数据的地址处向后找 32 个字节便是下一条记录的真实数据。
• 这其实是个链表，可以通过一条记录找到它的下一条记录。
• 下一条记录指得并不是按照我们插入顺序的下一条记录，而是按照主键值由小到大顺序的下一条记录
• 规定 Infimum 记录（最小记录） 的下一条记录就是本页中主键值最小的用户记录，本页中主键值最大的用户记录的下一条记录就是 Supremum 记录（最大记录）
• 为了更形象的表示这个 next_record 起到的作用，我们用箭头来替代 next_record 中的地址偏移量，如下图所示：

• 从图中可以看出来：最大记录的 next_record 的值为 0，这也就是说最大记录是没有下一条记录了，它是这个单链表中的最后一个节点。
• 如果从中删除掉一条记录，比如我们把第 2 条记录删掉，删掉第 2 条记录后如下图所示：

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

• 第 2条记录并没有从存储空间中移除，而是把该条记录的 delete_mask 值设置为 1
• 第 2 条记录的 next_record 值变为了 0，意味着该记录没有下一条记录了
• 第 1 条记录的 next_record 指向了第 3 条记录

• 最大记录的 n_owned 值从 5 变成了 4，关于这点的变化后面会详细说明

  小贴士： next_record 为什么要指向记录头信息和真实数据之间的位置呢？ 为什么不指向整条记录的开头位置，也就是记录的额外信息开头的位置呢？

  因为这个位置刚刚好，向左读取就是记录头信息，向右读取就是真实数据。 变长字段长度列表、null 值列表中的信息都是逆序存放，这样可以使记录中位置靠前的字段和它们对应的字段长度信息在内存中的距离更近，可能会提高高速缓存的命中率。

• 主键值为 2 的记录被删掉了，但是存储空间却没有回收，如果再次把这条记录插入到表中，InnoDB 存储引擎并不会因为新记录的插入而为它申请新的存储空间，而是直接复用了原来被删除记录的存储空间

  小贴士： 当数据页中存在多条被删除的记录时，这些记录的 next_record 属性会把这些被删掉的记录组成一个垃圾链表，以备之后重用这部分存储空间。

Page Directory（页目录）

上面已经了解了记录在页中按照主键值由小到大顺序串联成一个单链表，
那如果想根据主键值查找页中的某条记录该怎么办呢？比如说这样的查询语句：
select * from page_demo where c1 = 3;
设计 InnoDB 存储引擎的人，他们从书的目录中找到了灵感。
我们平常想从一本书中查找某个内容的时候，一般会先看目录，找到需要查找的内容对应的书的页码，然后到对应的页码查看内容。
设计 InnoDB 存储引擎的人为我们的记录也制作了一个类似的目录，他们的制作过程是这样的：

1. 将所有正常的记录（包括最大和最小记录，不包括标记为已删除的记录）划分为几个组。
2. 每个组的最后一条记录（也就是组内最大的那条记录）的头信息中的 n_owned 属性表示该记录拥有多少条记录，也就是该组内共有多少条记录。
3. 将每个组的最后一条记录的地址偏移量单独提取出来按顺序存储到靠近页的尾部的地方，

这个地方就是所谓的 Page Directory，也就是页目录。
页目录中的这些地址偏移量被称为槽（Slot），所以这个页目录就是由槽组成的。
比方说现在的 page_demo 表中正常的记录共有 6 条，InnoDB 存储引擎会把它们分成两组：
第一组中只有一个最小记录，第二组中是剩余的 5 条记录，如下图所示：

• 现在页目录部分中有两个槽，也就意味着我们的记录被分成了两个组
• 槽 1 中的值是 112，代表最大记录的地址偏移量（就是从页面的 0 字节开始数，数 112 个字节）；槽0 中的值是 99，代表最小记录的地址偏移量
• 注意最小和最大记录的头信息中的 n_owned 属性
  • 最小记录的 n_owned 值为1，这代表着以最小记录结尾的这个分组中只有 1 条记录，也就是最小记录本身。
  • 最大记录的 n_owned值为 5，这代表着以最大记录结尾的这个分组中有 5 条记录，包括最大记录本身和插入的 4 条记录。

99 和 112 这样的地址偏移量很不直观，我们用箭头指向的方式替代数字如下图所示：

设计 InnoDB 存储引擎的人对每个分组中的记录条数有如下规定：

• 对于最小记录所在的分组只能有 1 条记录
• 对于最大记录所在的分组拥有的记录条数只能在 1~8 条之间
• 剩下的分组拥有的记录条数只能在 4~8 条之间。

所以分组是按照下边的步骤进行的：

• 初始情况下：一个数据页里只有最小记录和最大记录两条记录，它们分属于两个分组
• 之后每插入一条记录，都会从页目录中找到主键值比本记录的主键值大并且差值最小的槽，

然后把该槽对应的记录的 n_owned 值 + 1，表示本组内又添加了一条记录，直到该组中的记录数 = 8

• 在一个组中的记录数 = 8 后，再插入一条记录时，会将组中的记录拆分成两个组，

一个组中 4 条记录，另一个组中 5 条记录。
这个过程会在页目录中新增一个槽来记录这个新增分组中最大的那条记录的偏移量。
为了演示添加了页目录之后加快查找速度的过程，再往 page_demo 表中添加一些记录：
现在一共有 16 条记录（包括最小和最大记录），这些记录被分成 5 个组，如下图所示：

现在看怎么从这个页目录中查找记录。
因为各个槽代表的记录的主键值是从小到大排序的，所以可以使用二分法来进行快速查找。
5 个槽的编号分别是：0、1、2、3、4，所以初始情况下最低的槽就是 low = 0，最高的槽就是 high = 4。
比方说我们想找主键值为 5 的记录，过程如下：

• 计算中间槽的位置：(0 + 4) / 2 = 2，所以查看槽 2 对应记录的主键值为 8，又因为 8 > 5，所以设置high = 2，low 保持不变
• 重新计算中间槽的位置：(0 + 2) / 2 = 1，所以查看槽 1 对应的主键值为 4。所以设置 low = 1，high 保持不变
• 因为 high - low 的值为 1，所以确定主键值为 5 的记录在槽 2 对应的组中，接下来就是通过遍历槽 2 对应的组的链表进行查找
• 由于一个组中包含的记录条数只能在 1 ~ 8 条之间，所以遍历一个组中的记录的代价是很小的

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

1. 通过二分法确定该记录所在的槽。
2. 通过记录的 next_record 属性遍历该槽所在的组中的各个记录。

   Page Header（页面头部）

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

在这里我们先说一下 page_direction 和 page_n_direction 的意思：

• page_direction：假如新插入的一条记录的主键值比上一条记录的主键值大，我们说这条记录的插入方向是右边，反之则是左边。用来表示最后一条记录插入方向的状态就是 page_direction
• page_n_direction：假设连续几次插入新记录的方向都是一致的，InnoDB 会把沿着同一个方向插入记录的条数记下来，这个条数就用 page_n_direction 这个状态表示。如果最后一条记录的插入方向改变了的话，这个状态的值会被清零重新统计。

其余未出现的状态信息，将在用到时详细说明。

File Header（文件头部）

上边说的 Page Header 是专门针对数据页记录的各种状态信息。
File Header 针对各种类型的页都通用的信息，比如：这个页的编号是多少，它的上一个页、下一个页是谁等。
File Header 是页结构的第一部分，这个部分占用固定的 38 个字节，记录的信息如下：

fil_page_space_or_chksum

• 这个代表当前页面的校验和（checksum）
• 校验和：对于一个很长的字节串来说，我们会通过某种算法来计算一个比较短的值来代表这个很长的字节串，这个比较短的值就称为校验和
• 这样在比较两个很长的字节串之前先比较这两个长字节串的校验和，如果校验和都不一样，那么两个长字节串肯定是不同的，所以省去了直接比较两个长字节串的时间损耗

fil_page_offset

• 每一个页都有一个单独的页号，就跟身份证号码一样
• InnoDB 通过页号可以唯一定位一个页

fil_page_type

• 这个代表本页的类型
• InnoDB 为了不同的目的而把页分为不同的类型，上边介绍的都是存储记录的数据页，其实还有很多别的类型的页，存储记录的数据页的类型是 fil_page_index，也就是索引页，

下表是不同类型的页：

fil_page_prev 和 fil_page_next

• InnoDB 都是以页为单位存放数据的，有时候我们存放某种类型的数据占用的空间非常大，比如：一张表中可以有成千上万条记录，InnoDB 可能不可以一次性为这么多数据分配一个非常大的存储空间，如果分散到多个不连续的页中存储的话需要把这些页关联起来
• 这两个属性就分别代表本页的上一个和下一个页的页号
• 这样通过建立一个双向链表把许多的页串联起来，而无需这些页在物理上真正连着
• 需要注意的是：并不是所有类型的页都有这两个属性
• 不过数据页（也就是类型为 fil_page_index 的页）是有这两个属性的，所以所有的数据页其实是一个双链表，就像这样：

关于 File Header 的其他属性用到时再详细说明。

File Trailer

InnoDB 会把数据存储到磁盘上，但是磁盘速度太慢，需要以页为单位把数据加载到内存中处理。
如果该页中的数据在内存中被修改了，那么在修改后的某个时间需要把数据同步到磁盘中。
但是在同步了一半时断电了怎么办，为了检测一个页是否完整，设 计InnoDB 的人在每个页的尾部都加了一个 File Trailer 部分，这个部分由 8 个字节组成，可以分成 2 个小部分
前 4 个字节代表页的校验和

• 这个部分是和 File Header 中的校验和对应的
• 每当一个页面在内存中修改了，在同步之前要把它的校验和算出来，因为 File Header 在页面的前边，所以校验和会被首先同步到磁盘
• 当完全写完时，校验和也会被写到页的尾部，如果完全同步成功，则页的首部和尾部的校验和应该是一致的
• 如果写了一半断电了，那么在 File Header 中的校验和代表着已经修改过的页，而在 File Trialer 中的校验和代表着原先的页，二者不同则意味着同步中间出了问题

后4个字节代表页面最后被修改时对应的日志序列位置（LSN）

• 这个部分也是为了校验页的完整性

这个 File Trailer 与File Header 类似，都是所有类型的页通用的。

总结

1. InnoDB 为了不同的目的而设计了不同类型的页，我们把用于存放记录的页叫做数据页。
2. 一个数据页可以被大致划分为7个部分，分别是
   • File Header，表示页的一些通用信息，占固定的 38 个字节。
   • Page Header，表示数据页的一些专有信息，占固定的 56 个字节。
   • Infimum + Supremum，两个虚拟的伪记录，分别表示页中的最小和最大记录，占固定的 26 个字节。
   • User Records：真实存储我们插入的记录的部分，大小不固定。
   • Free Space：页中尚未使用的部分，大小不确定。
   • Page Directory：页中的某些记录的相对位置，也就是各个槽在页面中的地址偏移量，大小不固定，插入的记录越多，这个部分占用的空间越多。
   • File Trailer：用于检验页是否完整的部分，占用固定的 8 个字节。
3. 每个记录的头信息中都有一个 next_record 属性，从而使页中的所有记录串联成一个单链表。
4. InnoDB 会把页中的记录划分为若干个组，每个组的最后一个记录的地址偏移量作为一个槽，存放在Page Directory 中，所以在一个页中根据主键查找记录是非常快的，分为两步：
   • 通过二分法确定该记录所在的槽。
   • 通过记录的 next_record 属性遍历该槽所在的组中的各个记录。
5. 每个数据页的 File Header 部分都有上一个和下一个页的编号，所以所有的数据页会组成一个双链表。
6. 为保证从内存中同步到磁盘的页的完整性，在页的首部和尾部都会存储页中数据的校验和 和 页面最后修改时对应的 LSN 值，如果首部和尾部的校验和 和 LSN 值校验不成功的话，就说明同步过程出了问题。