MySQL页

基于MySQL是怎样运行的这本书，对页章节进行简化，仅为了以最小的篇幅了解各种页结构。

页的定义

InnoDB在磁盘和内存之间交互的基本单位，也是InnoDB管理存储空间的基本单位。

各种页的通用结构

InnoDB设计者设计了各种类型的页，每种页都有不同的数据结构，但是他们都有几个通用的结构用来存储一些关键数据，这些页结构包括。

• File Header。不同类型页中File Header存储的信息也不一样，但仍然有部分数据是通用的：
  • FIL_PAGE_SPACE_OR_CHKSUM。页的校验和。
  • FIL_PAGE_OFFSET。页号。
  • FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID。页所属表空间。
  • FIL_PAGE_TYPE。页类型。
    • FIL_PAGE_TYPE_ALLOCATED。最新分配，还没使用。
    • FIL_PAGE_UNDO_LOG。Undo日志页。
    • FIL_PAGE_INODE。段信息节点。
    • FIL_PAGE_IBUF_FREE_LIST。Insert Buffer空闲列表。
    • FIL_PAGE_IBUF_BITMAP。Insert Buffer位图。
    • FIL_PAGE_TYPE_SYS。系统页。
    • FIL_PAGE_TYPE_TRX_SYS。事务系统数据。
    • FIL_PAGE_TYPE_FSP_HDR。表空间头部信息。
    • FIL_PAGE_TYPE_XDES。扩展描述页。
    • FIL_PAGE_TYPE_BLOB。BLOB页。
    • FIL_PAGE_INDEX。索引页，也就是我们所说的数据页。
• File Tailer。
  • 前4个字节代表页的校验和。
  • 后4个字节代表页面被最后修改时对应的日志序列位置（LSN）。

数据页

存放表中行记录的页类型

页结构

记录如何在页中存储

而典型的记录格式（Compact）是这样的：

会在记录头中存储一些关键信息：

记录头信息（在数据页存储时需要用到的用粗体表示）：

• delete_mask。标记该记录是否被删除。
• min_rec_mask。B+树的每层非叶子节点中的最小记录都会添加该标记。
• n_owned。表示当前记录拥有的记录数。
• heap_no。表示当前记录在页中的位置信息。
• record_type。表示当前记录的类型，0表示普通记录，1表示B+树非叶子节点记录，2表示最小记录，3表示最大记录。
• next_record。表示下一条记录的相对位置。

行记录在页中按照主键从小到大存储形成一个单链表。

其中最小记录（infimum）和最大记录（supremum）是InnoDB自动为每个页加上的两条记录，顾名思义，分别代表当前页的最小记录和最大记录，由于这两条记录不是我们自己加入的，所以又称为伪记录。

因为基于现有数据结构如果要查找页中的一条记录，需要遍历页的整个单链表，效率太低，所以InnoDB设计者们将入了目录层，以提高页内查找效率，这样为什么能提高查找效率，后面解释了查询原理后就能明白了。

1. 我们将所有记录（包括最小记录和最大记录，不包括已删除记录）从小到大分成几个组。
2. 让每组的最后一条记录的n_owned表示该组的记录数量。
3. 将每组的最后一条记录的数据地址偏移量（基于页的）集中逆序放在Page Directory（即页目录）中，每一组最有一条记录地址在Page Directory中对应一个槽。

缩短查询时间的秘密在查询流程中：

1. 首先使用二分法找到该记录所在的槽，并找到槽中最小的那条记录。
2. 通过next_record指针遍历该槽所在组中的所有记录。

例如我们现在需要查询主键为5的行记录：

1. 二分法找到槽。
   • low=0，high=4，计算中间值(low+high)/2=2的主键值，为8，大于5，所以high=2。
   • 计算中间值(low+high)/2=1的主键值，为4，小于5，所以low=1。
   • 因为high-low=1，low槽中最大主键为4，所以确定主键=5的记录在槽5中。
   • 通过槽1的next_record我们找到了槽2中的最小记录。
2. 通过next_record指针遍历该槽。
   • 遍历槽2的第一个元素，刚好第一个元素就是主键值为5的元素，成功找到了！

时间复杂度：因为找到槽后通过next_record遍历的时间为常数，所以基本上时间复杂度就是二分法的时间复杂度N(log₂ⁿ)了。

数据页的文件头部

• FIL_PAGE_SPACE_OR_CHKSUM。页的校验和（checksum值）。
• FIL_PAGE_OFFSET。页号。
• FIL_PAGE_PREV。上一个页的页号。
• FIL_PAGE_NEXT。下一个页的页号。
• FIL_PAGE_LSN。页面被最后修改时对应的日志序列位置（英文名是：Log Sequence Number）。
• FIL_PAGE_TYPE。该页的类型。
• FIL_PAGE_FILE_FLUSH_LSN。仅在系统表空间的一个页中定义，代表文件至少被刷新到了对应的LSN值。
• FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID。页属于哪个表空间。