MySQL InnoDB 数据页的结构

Question

之前说过页是 MySQL 管理存储空间的基本单位，一个页一般是 16KB。MySQL 一次会将整个页加载到内存中（原因：内存速度远大于磁盘速度）。现在来看一下 InnoDB 中存放表中记录和索引的页的结构。了解了索引页的结构可以帮助我们了解后面使用索引查找为什么那么快。

先看数据页的结构，整体如下图：

比较简单的一些字段快速过一下：File Header 和 Page Header 是一些通用信息，其中用于存放记录的数据页的 File Header 中有 FIL_PAGE_PREV 和 FIL_PAGE_NEXT，用于将多个页连成双向链表，如下图：

File Trailer 用于校验页是否完整（为保证从内存中同步到磁盘的页的完整性，在页的首部和尾部都会存储页中数据的校验和和页面最后修改时对应的LSN值，如果首部和尾部的校验和和LSN值校验不成功的话，就说明同步过程出现了问题），Infimum + Supremum 是两个虚拟的行记录，代表最小和最大记录。每当插入一条记录时，都会从 Free Space部分申请空间划到 User Records 部分，直到 Free Space 空间用尽，意味着这个页已经用完了。

现在我们想要看到插入一堆记录之后，这些记录在页中是怎样组织起来的。首先回顾一下上一节说过的一条记录的格式，其中有个记录头信息，这个很关键，记录头信息里有几个值得我们现在关注的字段：

• heap_no：这个属性代表当前记录在本页中的位置，其中页的 Infimum + Supremum 这两条虚拟记录始终占有heap_no为0和1的两个值，后面插入的用户记录按照大小，heap_no依次递增，这里说的记录大小，对于一条完整的记录来说，就是主键的大小。对于一条索引记录来说，就是索引列的大小。
• record_type：这个属性表示当前记录的类型，一共有4种类型的记录，0表示普通记录，1表示B+树非叶节点记录，2表示最小记录，3表示最大记录。我们自己插入的记录就是普通记录，它们的record_type值都是0，而最小记录和最大记录的record_type值分别为2和3
• n_owned：下面讲页目录的时候会讲，页中的数据会分组，n_owned属性表示每组中的最大记录拥有的记录数，也就是该组内有多少条记录
• next_record：表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量（回顾一下一条记录的格式，每条记录的真实数据是在记录头信息之后）。因此，这其实是个单向链表。并且，这个链表的顺序并不是按照插入顺序，而是按照heap_no类似的记录大小的顺序，Infimum虚拟记录在最开始，Supremum虚拟记录在最后面。删除记录之后这个链表也会发生变化。

直观的看一下这个链表：

这里插入一个小问题，为啥 next_record 要指向记录头信息和真实数据之间的位置呢？为啥不干脆指向整条记录的开头位置，也就是记录的额外信息开头的位置呢？

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

我们看到了页中的记录是用链表组织起来的，但这还不够，因为要在一个页中根据主键快速找到一条记录还是很慢，而快速查找的关键就在页的Page Directory结构中。Page Directory差不多就是为页内存放的记录做了一个目录，方便快速查找。

Page Directory

刚刚讲记录的 n_owned 属性的时候说过，一个页中的记录会被分为几组（如何分组马上就讲），每组的最大一条记录的n_owned属性表示该组有多少条记录。而 Page Directory 中存放的就是每组的最大一条记录的地址偏移量（被称为槽，slot），Page Directory 就是由 slot 组成的。

那么是如何进行分组的呢？对于最小记录 Infimum 所在的分组只能有 1 条记录，最大记录 Supremum 所在的分组拥有的记录条数只能在 1-8 条之间，剩下的分组中记录的条数范围只能在是 4-8 条之间。所以每插入一条记录的时候，都会根据这条记录的大小匹配到该记录应该属于哪个槽，如果这个槽的记录数还没有满8个，那么就加入这个组，如果满了，会拆分成两个组，一个4条记录，一个5条记录，在页目录中新增一个槽。

那么，在一个页中根据主键快速查找一条记录的过程就是：通过二分法确定该记录所在的槽，再通过next_record形成的链表定位到记录