InnoDB 数据页结构

页是 InnoDB 管理存储空间的基本单位，一个页一般是 16KB。InnoDB 为了不同的目的设计了多种不同类型的页：比如存放表空间头部信息的页、存放 Change Buffer 信息的页、存放的 INODE 信息的页、存放 undo 日志信息的页等等。这里我们关心的是那些存放表中记录的那种类型的页，官方称这种存放记录的页为索引（INDEX）页，这里暂且称为数据页。

数据页结构快览

数据页代表的这块 16KB 大小的存储空间可以划分为多个部分，不同部分有不同的功能：

一个 InnoDB 数据页的存储空间大致被划分为 7 部分，有的部分占用的字节数是确定的，有的部分占用的字节数是不确定的。

名称	中文名	占用空间大小	简单描述
`File Header`	文件头部	38 字节	页的一些通用信息
`Page Header`	页面头部	56 字节	数据页专有的一些信息
`Infimum + Supremum`	页面中最小记录页面中最大记录	26 字节	两个虚拟的记录
`User Records`	用户记录	不确定	用户存储的记录内容
`Free Space`	空闲空间	不确定	页中尚未使用的空间
`Page Directory`	页目录	不确定	页中某些记录的相对位置
`File Trailer`	文件尾部	8 字节	检验页是否完整

记录在页中的存储

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

记录头信息的秘密

为了详细展开讲述，我们先创建一个表：

CREATE TABLE PAGE_DEMO (
    C1 INT,
    C2 INT,
    C3 VARCHAR(10000),
    PRIMARY KEY(C1)
) CHARSET=ASCII ROW_FORMAT=COMPACT;

新创建的 PAGE_DEMO 表有 3 列，其中 C1 列指定为主键，所以 InnoDB 就没必要创建那个所谓的 row_id 隐藏列了。

我们把记录头信息特意进行了展开，因为很重要，这里再回顾一下各个属性的含义：

名称	大小（位）	描述
预留位1	1	没有使用
预留位2	1	没有使用
`delete_flag`	1	标记该记录是否删除
`min_rec_flag`	1	B+数的每层非叶子节点中最小的记录都会添加该标记
`n_owned`	4	一个页面中的记录会被分为若干个组，每组中有一个记录是大哥，其余的记录都是小弟，带头大哥的n_owned值代表该组中有多少个记录，小弟的n_owned值都为0
`heap_no`	13	表示当前记录在页面堆中的相对位置
`record_type`	3	表示当前记录的类型，0表示普通记录，1表示B+树非叶子节点目录项记录，2表示Infimum记录，3表示Supremum记录
`next_record`	16	表示下一条记录的相对位置

下面尝试向PAGE_DEMO 表中插入几条记录：

1	INSERT INTO PAGE_DEMO VALUES(1, 100, 'aaa'), (2, 200, 'bbb'), (3, 300, 'ccc'), (4, 400, 'ddd');

为了方便理解，在演示图中只展示有关的头信息属性和C1、C2、C3列的信息，为了方便展示这些记录在页的User Records部分是怎么表示的，这里把记录中的头信息和实际列数据使用十进制表示（其实是一堆二进制）。每条记录之间存储时并没有空隙，这里为了方便展示，将每条记录单独展示在一行。

deleted_flag：这个属性用来标记当前记录是否被删除，占用1比特。值为0时表示记录未删除，值为1时表示记录被删除。
可以看到被删除的记录依旧在页中，这些被删除的记录之所以不被物理删除，是因为移除它们后，还需要在磁盘上重新排列其他的记录，这会带来性能消耗，所以只打一个标记就可以避免这个问题。所有被删除的记录会组成一个垃圾链表，记录在这个链表中占用的空间称为可重用空间，之后有新纪录插入到表中时，它们就可能覆盖掉被删除的这些记录占用的存储空间。
min_rec_flag：B+ 树每层非叶子节点中最小的目录项记录都会添加该标记。
n_owned：
heap_no：向表中插入的记录从本质上来说都是放到数据页的User Records部分，这些记录一条一条地排列着，这种排列的结构称为堆。为了方便管理这个堆，一条记录在堆中的相对位置为heap_no。
从上面我们插入的样例来看，heap_no 为 0 和 1 的两条记录不见了？
这里其实是InnoDB会自动给每个页加入两条记录，这两条记录被称为伪记录或虚拟记录。这两条记录中，一条记录代表页面最小记录（Infimum记录），另一条代表页面最大记录（Supremum记录）。任何用户记录都比Infimum记录大，任何用户记录都比Supremum记录小。Infimum记录的heap_no值为0，Supremum记录的heap_no值为1，它们在堆中的相对位置最靠前。
🏷️注意：
堆中记录的heap_no值在分配之后就不会发生改动了，即使之后删除了堆中的某条记录，这条被删除的记录的heap_no值也仍然保持不变。
record_type：表示当前记录的类型。共有四种类型的记录
类型编号类型描述
0 普通记录
1 B+ 树非叶节点的目录项记录
2 Infimum 记录
3 Supremum 记录
next_record：表示从当前记录的真实数据到下一条记录的真实数据的距离。如果该值为正数，说明当前记录的下一条记录在当前记录的前面。可以理解为是一个链表结构，可以通过一条记录找到它的下一条记录。下一条记录指的并不是插入顺序中的下一条记录，而是按照主键值由小到大的顺序排列的下一条记录。如下图所示：
如第1条记录的next_record是32，意味着它当前地址往向后找32个字节便是它的下一条记录。此时如果从表中删除一条记录，比如把第2条记录删掉，此时如下图所示：
从上图可以看出，删除第2条记录后主要发生了下面这些变化：
- 第2条记录并没有从存储空间删除，而是把这条记录的deleted_flag置为1
- 第2条记录的next_record值被置为0，意味着当前记录没有下一条记录了
- 第1条记录的next_record值被置为64，也就是指向其之后64个字节处，即第3条记录的地址
- Supremum记录的n_owned值被置为4，也表示当前组内记录加上自己只有4条记录
无论对页中的记录进行增删改操作，InnoDB始终会维护一个记录的单向链表。链表中的各个节点按照主键值由小到大的顺序链接起来。
主键值为2的记录被删除，但是并没有释放空间，如果我们再次将这条记录插入表中，会发生什么呢？
没错，这条重新插入的记录复用了被删除记录的存储空间。
当数据页中存在大量的删除记录时，可以使用这些记录的next_record属性，将这些记录组成一个链表，以备之后复用这部分存储空间，这个链表也称为垃圾链表。

类型编号	类型描述
0	普通记录
1	B+ 树非叶节点的目录项记录
2	Infimum 记录
3	Supremum 记录

Page Directory (页目录)

现在，我们知道了记录是按照主键从小到大挨个排好的一个链表，如果我们现在要查询一条记录，我们可以从Infimum记录开始往后遍历，如果存在这条记录一定会找到，反之则没有。但是这种查找方式在数据量小的时候还可以应付，如果面对大量数据，每次查找未免也太浪费时间了。

想一想，我们日常生活中查字典的时候，难道从第一页开始挨个往后翻吗，我们会先看目录，通过目录我们可以看到这个记录所在的页码范围，然后从所在范围的第一页往后遍历，减少大量数据的无用查询。而InnoDB也有一个类似的目录，具体过程如下：

将所有正常的记录(包括Infimum和Supremum记录，但不包括已经删除保存至垃圾链表中的记录)划分为几组。
每个组中的最后一条记录，保存当前组内连同自己一共有几条记录，将信息保存至自己的n_owned属性中。
将每个组中最后一条记录在页面中的地址偏移量提取出来，按顺序存储在靠近页尾部的地方。这里就是Page Directory。页目录中这些地址偏移量被称为槽(Slot)，每个槽占用两个字节。页目录也就是由多个槽构成。

一个页面也就是16KB的大小，即16384个字节，而2字节可以表示的地址偏移量范围是0～65535，所以一个槽用2字节足矣。

比如，上面的 page_demo 表中现在共有记录6条，InnoDB会将它们分为两组，第一组只有Infimum记录，第二组是实际的四条记录和一条Supermum记录。两个组分别对应两个槽，每个槽中保存最大的那一条记录在页面中的地址偏移量。

现在分析一下这张图：

页目录部分中有两个槽，意味着表中记录分为了两组，槽1的值是112，代表Supremum记录在页面中的地址偏移量。槽0的值是99，代表Infimum记录在页面中的地址偏移量。
Infimum记录的n_owned值为1，表示以Infimum记录为最后一个节点的这个分组中只有1条记录，也就是自己本身。
Supremum记录的n_owned值为5，表示以Supremum记录为最后一个节点的这个分组中有5条记录，除了Supremum记录本身，还有实际插入的4条记录。
每个槽占用2个字节，按照对应记录的大小相邻分布，槽对应的记录越小，它的位置就越靠近File Trailer。

但是划分分组的依据是什么呢？为什么Infimum要单独一组，而Supremum不用呢？

因为MySQL规定Infimum记录所在组只能有1条记录，Supremum记录所在组记录拥有数也只能1 ~ 8条之间，剩余的普通组记录拥有数只能在4 ~ 8条之间。

这里我们来模拟一下分组的过程：

初始情况下，只有Infimum记录和Supremum记录，他们分属于两个分组，此时页目录也只有两个槽，分别保存Infimum和Supremum的页内地址偏移量。
每插入1条记录，都会从页目录中找到主键值比待插入记录的主键值大的记录，然后把该槽对应的记录的n_owned值加1，表示本组内又添加了一条记录，直到该组记录数等于8个。
当一个组中的记录数等于8后，再插入1条记录，会将组中的记录拆分为两组，其中一个组中4条记录，另一个5条记录。这个拆分过程中会在页目录中新增一个槽，记录这个新增分组中最大的那条记录的业内地址偏移量。

mysql> INSERT INTO page_demo VALUES(5, 500, 'eee'), (6, 600, 'fff'),
								   (7, 700, 'ggg'), (8, 800, 'hhh'),
								   (9, 900, 'iii'), (10, 1000, 'jjj'),
								   (11, 1100, 'kkk'), (12, 1200, 'lll'),
								   (13, 1300, 'mmm'), (14, 1400, 'nnn'),
								   (15, 1500, 'ooo'), (l6, 1600, 'ppp'); Query OK, 12 rows affected (0.00 sec) Records: 12 Duplicates: 0 Warnings: 0

现在我们往page_demo表中再添加12条记录，现在一共18条，此时记录被分为5组。因为图太大了，为了避免眼花缭乱，进行了精简，只保留了变化的n_owned和next_record属性。如下图：

现在我们该怎么在一个页目录中查找记录？

因为一个槽占用2个字节，且各个槽是紧挨着的，槽中存放的数据是当前分组中主键值最大的记录，所以我们可以通过二分法快速查找。比如我们现在想找主键值为6的记录，过程如下：

计算中间槽位置： $(0+4)/2=2$ ，中间槽为2号槽，查看槽中存放的记录偏移量找到对应的记录，发现其主键值为8， $8 > 6$ ，所以设置 $high=2， low=0$ 保持不变；
重新计算中间槽位置： $(0+2)/2=1$ ，中间槽为1号槽，槽中存放记录其主键值为4， $4 < 6$ ，所以设置 $low = 1，high = 2$ 保持不变；
找到槽后寻找目标记录：因为 $high-low=1$ ，所以可以确定主键值为6的记录在2号槽对应的分组中，此时需要从分组中找到最小的记录，挨个遍历分组，直到主键值相同，但是槽中只保留了主键最大值的记录，而根据next_record可以往后找主键值更大的记录，无法找到之前的记录，此时我们可以通过拿到1号槽中的最大主键值记录，通过他的next_record属性值，可以找到下一条记录，也就是2号分组中主键值最小的记录，通过遍历对比得到主键值为6的记录。

因为一个槽中至多只有8条记录，所以遍历一个组中的记录代价是很小的

MySQL为了能得到存储在数据页中的记录的状态信息，比如数据页中已存储了多少条记录、Free Space在页面中的地址偏移量、页目录中存储了多少个槽等，特意在数据页中定义了一个名为Page Header的部分，占用固定的56字节，存储各种状态信息：

状态名称	占用空间大小	描述
`PAGE_N_DIR_SLOTS`	2	在页目录中的槽数量
`PAGE_HEAP_TOP`	2	还未使用的空间最小地址，也就是从该地址之后的区域就是Free Space
`PAGE_N_HEAP`	2	第1位表示本记录是否是紧凑型的记录剩余15位表示本页的堆中记录的数量（包括Infimum、Supremum以及标记为“已删除”的记录）
`PAGE_FREE`	2	各个已删除的记录通过next_record组成一个单向链表，这个单向链表中的记录所占用的存储空间可以被重新利用，PAGE_FREE表示该链表头节点对应记录在页面中的偏移量
`PAGE_GARBAGE`	2	已删除记录占用的字节数
`PAGE_LAST_INSERT`	2	最后插入记录的位置
`PAGE_DIRECTION`	2	记录插入的方向
`PAGE_N_DIRECTION`	2	一个方向连续插入的记录数量
`PAGE_N_RECS`	2	该页中用户记录的数据（不包括Infimum和Supremum记录以及被删除的记录）
`PAGE_MAX_TRX_ID`	8	修改当前页中的最大事务ID，该值仅在二级索引页面中定义
`PAGE_LEVEL`	2	当前页在B+树中所处的层级
`PAGE_INDEX_ID`	8	索引ID，表示当前页属于哪个索引
`PAGE_BTR_SEG_LEAF`	10	B+树叶子节点段的头部信息，仅在B+树的根页面中定义
`PAGE_BTR_SEG_TOP`	10	B+树非叶子结点段的头部信息，仅在B+树的根页面中定义

PAGE_DIRECTION：假如新插入的一条记录的主键值比上一条记录的主键值打，我们说这条记录的插入方向是右边，反之则是左边。用来表示最后一条记录的插入方向。
PAGE_N_DIRECTION：假设连续几次插入新记录的方向都是一致的，InnoDB会把沿着同一方向插入记录的条数记录下来。当然如果新记录的插入方向发生了改变，那么PAGE_N_DIRECTION回清零后重新统计。

File Header (文件头部)

File Header通用于各种类型的页，也就是说各种类型的页都会以File Header作为第一个组成部分，它描述了一些通用于各种页的信息，比如这个页的编号是多少，上一页和下一页是谁等。File Header部分占用固定的38字节，如下所示：

状态名称	占用空间大小	描述
`FIL_PAGE_SPACE_OR_CHKSUM`	4	当 MySQL 的版本低于 4.0.14 版本时，该属性表示本页面所在的表空间 ID；在之后的版本中，该属性表示页的校验和（checksum）
`FIL_PAGE_OFFSET`	4	页号
`FIL_PAGE_PREV`	4	上一页的页号
`FIL_PAGE_NEXT`	4	下一页的页号
`FIL_PAGE_LSN`	8	页面被最后修改时对应的 LSN 值（Log Sequence Number：日志序列号）
`FIL_PAGE_TYPE`	2	该页的类型
`FIL_PAGE_FILE_FLUSH_LSN`	8	仅在系统表空间的第一个页中定义，代表文件至少被刷新到了对应的 LSN 值
`FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID`	4	页属于哪个表空间

讲解一下比较重要的部份：

FIL_PAGE_SPACE_OR_CHKSUM：MySQL 现阶段的版本都是用来代表当前页面的校验和（checksum）。
FIL_PAGE_OFFSET：每一个页都有单独的页号，InnoDB 通过页号来定位唯一的页。

FIL_PAGE_TYPE：表示当前页类型。InnoDB 为了不同目的把页分为了不同的类型。前面讲的都是数据页，其实还有其他页类型，如下所示：

类型名称	十六进制	描述
`FIL_PAGE_TYPE_ALLOCATED`	0x0000	最新分配，还未使用
`FIL_PAGE_UNDO_LOG`	0x0002	undo 日志页
`FIL_PAGE_INODE`	0x0003	存储段的信息
`FIL_PAGE_IBUF_FREE_LIST`	0x0004	Change Buffer 空闲列表
`FIL_PAGE_IBUF_BITMAP`	0x0005	Change Buffer 的一些属性
`FIL_PAGE_TYPE_SYS`	0x0006	存储一些系统数据
`FIL_PAGE_TYPE_TRX_SYS`	0x0007	事务系统数据
`FIL_PAGE_TYPE_FSP_HDR`	0x0008	表空间头部信息
`FIL_PAGE_TYPE_XDES`	0x0009	存储区的一些属性
`FIL_PAGE_TYPE_BLOB`	0x000A	溢出页
`FIL_PAGE_INDEX`	0x45BF	索引页，也就是上面说的数据页

FIL_PAGE_PREV 和 FIL_PAGE_NEXT 分别代表上一页和下一页，通过建立双向链表讲页进行串联，而无需让这些页在物理空间真正连着。但是要注意并不是所有类型的页都有上一页和下一页的属性。

File Trailer (文件尾部)

InnoDB 存储引擎会把数据存储到磁盘上，但是磁盘速度太慢，需要以页为单位把数据加载到内存中处理。但是如果该页中数据在内存中发生了变动，那么在修改后的某个时间还需要把数据刷新到磁盘中。但是 == 如果在刷新到磁盘的过程中系统断电了，怎么办？==

为了检测一个页是否完整（也就是在刷新的过程中只刷新了一部分），设计师在每个页尾增加了 File Trailer 部分，这部分由 8 字节组成，分为 2 个小部分。

前 4 字节代表页的校验和。这部分与 File Header 中校验和相对应。每一个页面在内存中发生修改时，在刷新前都要重新计算校验和，所以 File Header 的校验和会率先被刷新到磁盘，当完全写完后，校验和也会被写到页尾。如果页面刷新成功，页首和页尾的校验和应该一致。如果刷新一部分断电了，那么 File Header 中的校验和代表着已经修改过的页，而 Trailer 中的校验和代表原先页，二者不同意味着刷新期间发生了错误。
后 4 字节代表页面被最后修改时对应的 LSN 的后 4 字节，正常情况应该与 File Header 部分的 FIL_PAGE_LSN 的后 4 字节相同。这个部分也用于校验页的完整性。

File Trailer 部分与 File Header 部分类似，都通用于所有类型的页。

InnoDB数据页结构