页是 InnoDB 管理存储空间的基本单位，InnoDB 为了不同的目的设计了不同类型的页，比如，这里我们讨论的是存储表中记录的数据页。

数据页结构简图：

image.png

记录在页中的存储

当页一开始生成的时候，其实并没有 User Record 部分，每当插入一条记录时，都会从 Free Space 部分申请一个记录大小的空间，并将这个空间划分到 User Record 部分。

image.png

• 记录头部信息
  记录头信息由固定的 5 字节组成，用于描述记录的一些属性。

  名称	大小	描述
  预留位1	1	没有使用
  预留位2	1	没有使用
  deleted_flag	1	标记该记录是否被删除
  min_re_flag	1	B+树的每层非叶子节点中最小的目录项都会添加该标记
  n_owned
  heap_no
  record_type
  next_record

  image.png

  • deleted_flag
    占用1比特，值为0表示记录没有被删除，值为1表示记录被删除了。

  • min_rec_flag
    后面介绍

  • n_owned
    后面介绍

  • heap_no
    InnoDB 把记录一条一条亲密无间的排列的结构称之为堆，为了方便管理，把一条记录在堆中相对位置称之为heap_no，每当一条插入一条新纪录，该记录的 heap_no 比前一条记录的heap_no +1

    InnoDB 会自动给每个页面加入2条记录 Infimum 和 Supremum。
    它们构造十分简单，都是由5字节大小的记录头信息和8字节大小的固定单词组成

    • Infimum，代表页面中的最小记录，按照主键比较大小

      
      
      image.png

    • Supremum，代表页面中的最大记录的下一条记录（类似链表的最后NULL），按照主键比较大小

      
      
      image.png

  • record_type

    • 0 表示普通记录
    • 1 表示B+树非叶节点的目录项记录
    • 2 表示 Infimum 记录
    • 3 表示 Supremum 记录

  • next_record
    表示从当前记录的真实数据到下一条记录的真实数据的距离。这里的这个下一条记录并不是指插入顺序中的下一条记录，而是按照主键大小由小到大的顺序排列的下一条记录。
    举例：

    image.png

Page Directory 页目录

记录在页中是按照主键大小由小到大的顺序串联成一个单向链表。

最笨的方法是从记录开始，沿着单向链表一直往后找，当页中存储的记录比较少时，这样查找倒也没什么问题。但是记录很多时，这个查找效率就不高了。为了提高查找效率，InnoDB为记录制作了一个目录：

• 将所有正常的记录，但不包括已经移除到垃圾链表中的记录，划分为几组
• 每个组的最后一条记录的头信息中的n_owned属性表示该组内 有几条记录。
• 将每个组中最后一条记录在页面中的地址偏移量（该记录的真实数据与页面中第0字节的距离）提取出来，按顺序存储到靠近页尾部的地方。这个地方就是 Page Directory，这些地址偏移量称为槽，每个槽占用2字节。

image.png

以Infimum记录的n_owned值为1，表示以记录Infimum为最后一个节点的这个组只有1条记录，那就是本身。
以Supremum记录的n_owned值为5，表示以记录Supremum为最后一个节点的这个组有5条记录。

关于这个分组数量的确定，也有规则：
对于Infimum记录所在的分组只能有1条记录，
Supremum记录所在的分组拥有的记录条数在1~8之间
剩下的分组中记录的条数在4~8之间。

这时，回到开头的问题，在一个数据页中查找指定主键值记录时，过程分为2步：

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

File Header

Page Header

File Trailer