InnoDB 索引页初探

名称	中文	大小(Byte)	描述
File Header	文件头	38	页的一些通用信息
Page Header]	页头	56	数据页（索引页）专有的信息
Infimum + Supremum	最小记录、最大记录	26	两个虚拟的行记录
User Records	用户记录	~	实际存储的用户记录
Free Space	剩余空间	~	页中尚未使用的空间
Page Directory	页目录	~	页中某些记录的相对位置
File Tailer	文件尾	8	校验页是否完整（用于同步）

背景：Compact 格式下的记录头结构

记录头的前 5 个字节信息：

• 预留位 1、2 没有使用

• delete_mask: 该行记录是否被删除？InnoDB 中的一条用户记录被删除后，它并没有立即从磁盘中删除，而是仅仅被标记为删除。所有被删除的记录会形成一个垃圾链表，这片空间称为可重用空间，要使用时直接覆盖即可（将删除标志位改为 1 和将这条记录移进垃圾链表其实是两个阶段）

• min_rec_mask: B+ 树的每层非叶子节点中的最小目录项记录都会添加该标记

• n_owned: 4 bit, 表示当前记录所在的组拥有的记录数（仅有本组主键最大的那条记录本字段不为 0；且看[下文](##Page Directory)）

• heap_no: 13 bit, 表示当前记录在记录堆中的位置信息，以本记录的主键大小作为排序依据（升序），但是最小记录与最大记录这两个虚拟记录占据了 0、1 两个 heap_no。值得注意的是一条记录一旦被插入数据页中，其 heap_no 就是固定的了，即使它被删除，这个 heap_no 也不会被回收

• record_type: 3 bit, 表示当前记录的类型， 0 表示普通记录， 1 表示 B+ 树非叶节点记录， 2 表示最小记录(Infimum)， 3 表示最大记录 (Supremum)

• next_record: 16 bit, 表示下一条记录的相对位置（因为各条记录之间是以单向链表的形式组织的）。具体来说，是从当前记录的真实数据（记录头信息的最后一位的下一位开始的信息）到下一条记录（按主键大小排列的下一个，可能不是存储顺序的下一个，中间可能隔着几条被标记为删除的记录）的真实数据的地址偏移量。特别地，Infimum 的 next_record 指向为主键值最小的用户记录；Supremum 的 next_record 为 0

  你会不会觉得 next_record 这个指针有点儿怪，为啥要指向记录头信息和真实数据之间的位置呢？为啥不干脆指向整条记录的开头位置，也就是记录的额外信息开头的位置呢？

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

  —— 「MySQL 是怎样运行的」

User Space & Free Space

User Space 增长的空间是从 Free Space 中分配来的

Infimum & Supremum

Infimum: 5 字节的记录头和 8 字节大小的固定数据，这段数据为 69 6E 66 69 6D 75 6D 00，“infimum” 的 ASCII 编码

Supremum: 5 字节的记录头和 8 字节的固定数据，73 75 70 72 65 6D 75 6D, “supremum” 的 ASCII 编码

• 提问：为什么要有这两个一头一尾多余的记录？

  一个想法：联想学数据结构时链表的 dummy 节点，会简化增加和删除节点的操作

Page Directory

（联想 OS 中虚拟内存的 Page Directory）

我们将记录以链表的形式组织起来，链表的查询是很慢的，为了加快查询，InnoDB 采用目录的机制加速查询，具体来说：

1. 将一个页中所有正常的记录（包括最大和最小记录，不包括标记为已删除的记录）划分为几个组。
2. 每个组的最后一条记录（也就是组内主键最大的那条记录）的头信息中的 n_owned 属性表示该组拥有多少条记录（组内其他记录的 n_owned 为 0）
3. 将每个组的最后一条记录的地址偏移量（该记录的真实数据相对本页第 0 个字节的距离）单独提取出来按顺序存储到靠近页的尾部的地方，这个地方就是所谓的 Page Directory ，也就是页目录。页面目录中的这些地址偏移量被称为槽 slot

并且还有如下规定：

1. infimum 必须单独编为 1 组，且该组内仅有 Infimum，则 Infimum 的 n_owned 为 1
2. supremum 所在的分组拥有的记录数为 1-8
3. 其余分组的记录数为 4~8

所以推算某个新加入的记录所在分组的方法为：

• 初始情况下数据页中仅有两条记录，即 infimum 和 supremum，它们各自占据一个分组
• 每新增一个用户记录，都会从页目录中找到主键值比待新增记录的主键值大并且差值最小的槽，然后把该槽对应的记录的 n_owned 值加 1，表示本组内又添加了一条记录，直到该组中的记录数等于 8 个。
• 在一个组中的记录数等于 8 个后再插入一条记录时，会将组中的记录拆分成两个组，一个组中 4 条记录，另一个 5 条记录。这个过程会在页目录中新增一个槽来记录这个新增分组中最大的那条记录的偏移量。

利用 Page Directory 查找某条记录用到了二分法的思想。即先通过二分找到待查记录应该在的那个组（槽），再从这个槽的第一条记录开始做单链表的顺序查找。

（其实访问的是这个槽的上一个槽，因为槽中存储的是本组中主键最大的那条记录的地址，但是我们要从本组中主键最小的那条记录开始遍历链表。那怎么找到本组中主键最小的记录的地址呢？上一个槽的主键最大的那条记录所链接的下一条记录就是本组主键最小的那个记录了呀~因为记录中间以主键的大小顺序排列）

Page Header

InnoDB 中有很多的页，但是只有索引页（数据页）具有 PageHeader，它记录了本数据页中有几条记录、有几个槽等等：

File Header

所有的页都有文件头和文件尾。文件头存储了各种页中都通用的信息，如页编号、本页的下一个页、本页的上一个页

• FIL_PAGE_SPACE_OR_CHKSUM 页面的校验和

• FIL_PAGE_OFFSET 页面的偏移量，即页号

• FIL_PAGE_PREV 指向本页的上一个页

• FIL_PAGE_NEXT 指向本页的下一个页。并不是所有的页都有上一个页和下一个页的指针！数据页是有的，比如有一个记录实在是太长，一个数据页存储不下，此时将剩余数据存储在下一个页，此时我们就需要用一张链表维护上下页的信息

• FIL_PAGE_TYPE 页的类型，数据页的该字段值为 0X45BF

File Tailer

所有的页都有文件头和文件尾。

MySQL 中的数据是存储在硬盘上的，但是处理数据时是将页加载到内存中进行处理的，此时就涉及到磁盘内容与内存内容的同步（主要是写回时的一致性）问题。为了检查从内存到磁盘的同步是否成功，设计了文件尾，其中有 8 个字节，分为两个部分：

• 前 4 个字节：本页面的校验和，与 File Header 中的校验和是一样的。每当一个页被修改了，同步之前需要重新计算本页的校验和，因为 File Header 在页的前面，所以同步时应该最先写回磁盘，当同步完全完成，File Tailer 中的校验和也被更新。当任意时刻，File Header 和 File Tailer 中的校验和不同时，则表示同步尚未完成或者同步失败
• 后 4 个字节：代表页面被最后修改时对应的日志序列位置（LSN）

总结

1. 注意区分 InnoDB 数据页中使用到的链表结构：数据页中的记录是以单链表组织的，数据页之间是以双向链表组织的
2. 数据页内部的槽以本组关键值最大的记录来代表本组（要考虑 Infimum 和 Supremum，即使这两条记录没有主键）；数据页的目录项（下一篇文章会讲到什么是数据页的目录项~）中以本页中主键值最小的记录代表本页（不考虑 Infimum 和 Supremum）