MySQL索引页结构

1. 前言

「页」是 InnoDB 管理存储空间的基本单位，也是内存和磁盘交互的基本单位。也就是说，哪怕你需要 1 字节的数据，InnoDB 也会读取整个页的数据，下次读取的数据如果恰巧也在这个页里，就能命中缓存了。写也是一样的，写数据前要先把页加载到内存，然后在内存中修改，该页被记为「脏页」，脏页淘汰之前必须刷盘。

InnoDB 有很多类型的页，它们的用处也各不相同。比如：有存放 undo 日志的页、有存放 INODE 信息的页、有存放 Change Buffer 信息的页、存放用户记录数据的页等等。今天我们要聊的，就是最基础也是最重要的，存放用户记录数据的「索引页」。

2. 索引页结构

InnoDB 默认的页大小是 16KB，在初始化表空间之前可以在配置文件中进行配置，一旦初始化完成就不可再变更了。查看页大小的命令如下，显示的是字节数。

SHOW VARIABLES LIKE 'innodb_page_size';

索引页结构如下图所示：索引页由七部分组成，其中 Infimum 和 Supremum 也属于记录，只不过是虚拟记录，这里为了与用户记录区分开，还是决定将两者拆开。

名称	大小	描述
File Header	38 字节	所有页的通用文件头信息
Page Header	56 字节	索引页特有的页头信息
Infimum+Supremum	26 字节	页中虚拟的最小、最大记录
User Records	变长	用户记录数据
Free Space	变长	空闲空间
Page Directory	变长	页目录，加速页内数据检索效率
File Trailer	8 字节	所有页的通用文件尾信息，校验页是否完整

2.1 File Header

File Header 是所有页都有的一个通用的结构，占用固定的 38 字节，它记录了页的一些通用的状态信息，例如：页的页号、Checksum、把页串联成双向链表的指针、页的类型等等。

名称	大小	描述
FIL_PAGE_SPACE_OR_CHECKSUM	4 字节	新版本中代表页的校验和 Checksum
FIL_PAGE_OFFSET	4 字节	页号
FIL_PAGE_PREV	4 字节	上一个页的页号
FIL_PAGE_NEXT	4 字节	下一个页的页号
FIL_PAGE_LSN	8 字节	页面最后被修改时的 LSN 值
FIL_PAGE_TYPE	2 字节	页的类型
FIL_PAGE_FILE_FLUSH_LSN	8 字节	仅在系统表空间的第 1 个页中使用，代表文件至少被刷新到了对应的 LSN 值
FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID	4 字节	页数据哪个表空间

FIL_PAGE_SPACE_OR_CHECKSUM

基于当前页计算出的校验和(Checksum)，可以把它看作是哈希值，校验和不同，则两个页数据肯定不同。它的作用是 InnoDB 在脏页刷盘时，有可能会遇到页刷到一半断电的情况，页的头和尾部分分别记录校验和，只有当头尾的校验和一致的时候，才代表磁盘上的页是完整的，否则就是一个损坏的页。

FIL_PAGE_OFFSET

页号，页的唯一标识，全局递增的数字，InnoDB 通过页号来定位唯一的一个页。4 字节存储，意味着一个表空间最多可以有 232 个页，按照一个页 16KB 计算，则一个表空间最多支持 64TB 的数据。

FIL_PAGE_PREV & FIL_PAGE_NEXT

一个页大小才 16KB，一张表数据其实是由 N 多个页构成的，页与页之间在物理上可以是不连续的，但是逻辑上要连续，FIL_PAGE_PREV 和 FIL_PAGE_NEXT 分别指向当前页的上一个页和下一个页的页号，通过这两个指针将索引页串联成了一个双向链表。记录与记录之间是单向的，页与页之间是双向的！

FIL_PAGE_LSN

页面最后被修改时，对应的 LSN 值。LSN 的全称是 Log Sequence Number，日志序列号。它是一个递增的数字，和事务相关，这里不作赘述。

FIL_PAGE_TYPE

当前页的类型，InnoDB 为了不同的目的设计了很多不同类型的页，索引页的固定值是0x45BF。

FIL_PAGE_FILE_FLUSH_LSN

仅在第 1 个页中使用，用来判断数据库是正常关闭还是异常宕机。

FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID

仅记录当前页数据哪个表空间。

2.2 Page Header

Page Header 是索引页特有的结构，占用固定的 56 字节，它记录了索引页中记录相关的状态信息。

名称	大小	描述
PAGE_N_DlR_SLOTS	2 字节	页目录中的槽数量
PAGE_HEAP_TOP	2 字节	未使用的空间最小地址，User Records 和 Free Space 分界点
PAGE_N_HEAP	2 字节	本页中的记录的数量(包括虚拟记录和删除记录)
PAGE_FREE	2 字节	第一个删除的记录地址，后续删除的记录会形成链表。
PAGE_GARBAGE	2 字节	已删除记录占用的字节数
PAGE_LAST_INSERT	2 字节	最后插入记录的位置
PAGE_DIRECTION	2 字节	记录插入的方向
PAGE_N_DIRECTION	2 字节	同一个方向连续插入的记录数量
PAGE_N_RECS	2 字节	该页中记录的数量(不包括虚拟记录和删除记录)
PAGE_MAX_TRX_ID	8 字节	修改当前页的最大事务 ID，仅在二级索引中使用
PAGE_LEVEL	2 字节	当前页在 B+树中所处的层级
PAGE_INDEX_ID	8 字节	索引 ID，表示当前页属于哪个索引
PAGE_BTR_SEG_LEAF	10 字节	B+树叶子段的头部信息，仅在 B+树的 Root 页定义
PAGE_BTR_SEG_TOP	10 字节	B+树非叶子段的头部信息，仅在 B+树的 Root 页定义

不用每个属性都了解，我们挑几个比较重要的看看。

PAGE_N_DlR_SLOTS

一个页内可能有上千条记录，挨个遍历的话效率太慢了。为了提高页内记录的检索效率，InnoDB 将页内的记录划分为多个组，组里最大的那条记录相较于页的地址偏移量会记录到「Page Directory」部分，每个组都对应一个槽，槽的大小是固定的 2 字节。该属性记录的就是页内槽的数量。

PAGE_HEAP_TOP

Free Space 的起始位置，它是 User Records 和 Free Space 分界点。一个全新的页一开始是没有 User Records 部分的，每插入一条记录，都要向 Free Space 申请空间，Free Space 耗尽就代表页满了。

PAGE_FREE

DELETE 命令删除记录时，InnoDB 并不会真的将记录从磁盘中删除，而是在记录的头信息里打个标记，然后将其加入到「垃圾链表」中。PAGE_FREE 指向的就是垃圾链表的表头记录。后面删除的记录，也会自动加入到链表里。

PAGE_DIRECTION & PAGE_N_DIRECTION

PAGE_DIRECTION 表示最后一条记录插入的方向，比上一条记录值大则记为右边，反之则是左边。PAGE_N_DIRECTION 表示同一方向连续插入的记录数，方向变了该值就会重置。

PAGE_LEVEL

InnoDB 组织数据的形式就是 B+树，树中的节点就是索引页，PAGE_LEVEL 代表当前页在 B+树中所处的层级。InnoDB 规定，叶子节点层级为 0，然后向上递增。

2.3 User Records

Infimum 和 Supremum 也属于记录，只是为了与用户记录区分开才划分成了两部分，我们先看 User Records。

用户记录存放在 User Records 部分，一个全新的页一开始全是 Free Space，是没有 User Records 部分的。每插入一条记录都需要到 Free Space 申请一块空间，并将其划分到 User Records 用来存放用户记录。当 Free Space 耗尽也就代表当前页已经用完了，再有新记录需要插入，就需要申请一个新的页了。还记得 MySQL 的行格式吗？它决定了记录在磁盘里的存储格式。以 COMPACT 为例，存储格式如下图：记录头信息里的字段比较关键，以防大家忘记，我这里再贴一下：

名称	大小(Bit)	说明
预留位 1	1	没有使用
预留位 2	1	没有使用
deleted_flag	1	记录删除标记
min_rec_flag	1	B+树非叶子节点的最小目录项标记
n_owned	4	同一页内同一组里最大的记录会记录组里的记录数量，其余记录该值为 0
heap_no	13	当前记录在页面堆里的相对位置
record_type	3	记录类型。0:普通记录,1:B+树非叶子节点目录项记录,2:Infimum 记录,3:Supremum 记录.
next_record	16	下一条记录的相对位置

记录头信息的最后 2 字节用来连接下一条记录，将页内所有记录串联成一个单向链表。所以我们隐藏变长字段长度列表和 NULL 值列表，记录的格式应该是这样的：记录是怎么排序的？我们已经知道，页内的记录会自动串联成一个单向链表。那这个链表的编排顺序是什么呢？是按照记录的插入时间排序的吗？其实不是的，如果表有主键，会根据主键排序；没主键有唯一非空索引，会根据该索引排序；两者都没有，InnoDB 会自动生成一个row_id列并根据该列进行排序。

若无特殊说明，本文均假定表有主键。

2.4 Infimum & Supremum

Infimum 和 Supremum 是索引页内的两条虚拟记录，InnoDB 规定所有索引页都会有这两条记录，而且所有的用户记录都比 Infimum 大，都比 Supremum 小。记录头信息里的 heap_no 代表记录在堆里的相对位置，该值越小代表记录越靠前。细心的同学会发现，上图中的用户记录 heap_no 值是从 2 开始的，那 0 和 1 呢？不说你也肯定猜到了，就是被 Infimum 和 Supremum 占用了。Infimum 和 Supremum 的 heap_no 值分别是 0 和 1，它俩在所有用户记录的最前面。

Infimum 和 Supremum 结构非常的简单，和用户记录一样也有头信息，真实数据部分是固定的字符串，如下图所示：我们把这两条虚拟记录也加入到记录里面，完整的结构就是下面这样的：Supremum 记录的 next_record 属性为 0，代表它已经没有下一条记录了。

2.5 Page Directory

Free Space 没什么好说的，就是一块未被使用的空闲空间。

Page Directory 也叫作「页目录」，它的目的是提高页内记录的检索效率。相较于一张表几千万的记录来说，一个页内几百上千条记录已经是很少很少了。可即便如此，它也有几百上千条啊，如果页内检索记录只能挨个遍历的话，那也太低效了。别忘了，页内的记录是根据索引值排好序的，我们可以巧用「二分法」来快速查找。

具体做法是：将页内所有非删除的记录划分为 N 个组，每个组里最后一条记录(即主键最大的记录)称作“大哥”，其余记录是“小弟”，“大哥”的n_owned属性记录了组内的记录数量。将“大哥”在页内的地址偏移量提取出来，按顺序依次从 File Trailer 部分往前写，每个地址偏移量占用 2 字节，称作一个「槽」，Page Directory 就是由这些槽构成的。InnoDB 对于分组内的记录数量有一些规定：

Infimum 记录所在分组，只能有一条记录。
Supremum 记录所在分组，允许有 1~8 条记录。
其余分组，允许有 4~8 条记录。

由此可见，一个组里最多有 8 条记录，只要通过二分法快速定位到组，InnoDB 也只需要遍历这 8 条记录，相较于遍历页内所有记录，效率要高的多。

2.6 File Trailer

File Trailer 是所有页都有的通用结构，占用固定的 8 字节，它的主要作用就是为了校验页的完整性。磁盘的速度实在是太慢了，InnoDB 不会每次写点数据都直接刷新到磁盘上，那样 MySQL 会慢死。而是将页作为刷盘的基本单位，数据修改时，先改内存里的页，稍后再将整个页的数据一次性刷新到磁盘里。但是这会带来一个问题，一个页 16KB，刷到第 10KB 的时候磁盘断电了怎么办？重启后 InnoDB 如何判断磁盘里的页数据是完整的？

InnoDB 是这么处理的，刷盘前根据页数据计算出一个 Checksum，在页头和页尾都写一份。页刷盘的时候，先刷页头再刷页尾，当头尾两个 Checksum 值一致的时候，代表磁盘里的页是完整的，否则就表示页头刷了页尾没刷，那肯定是刷到一半出错了。

大小	说明
4 字节	页的校验和 Checksum
4 字节	页最后被修改时对应的 LSN 的后 4 个字节，正常情况下应该与 File Header 里的 FIL_PAGE_LSN 的后 4 个字节相同。

3. 总结

页是 InnoDB 存取数据的基本单位，默认页大小是 16KB，InnoDB 为了不同的目的设计了很多不同类型的页，本文重点分析了存放用户记录的索引页。页的头尾部分 File Header 和 File Trailer 是所有页都有的一个通用结构，它们记录了页的一些通用状态信息，和 Checksum 用来验证页的完整性。Page Header 是索引页特有的结构，它记录了页内用户记录相关的状态信息。User Records 部分用来存放用户记录。另外，由于页内的记录数量也不少，为了提高页内记录的检索效率，InnoDB 在索引页中加入了 Page Directory，它通过将记录分组，将组里最大的记录的地址偏移量形成一个个槽，Page Directory 就是由这些槽构成的。检索数据时，使用二分法快速定位到槽所在的组，就可以避免遍历所有组的记录了。