InnoDB的Page结构

发表于 | 分类于

深入InnoDB底层实现

What is Page？

理解InnoDB的实现不得不提Page结构，Page是整个InnoDB存储的最基本构件，也是InnoDB磁盘管理的最小单位，与数据库相关的所有内容都存储在这种Page结构里。

Page分为几种类型，常见的页类型有数据页（B-tree Node）、Undo页（Undo Log Page）、系统页（System Page） 、事务数据页（Transaction System Page）等。单个Page的大小是16K（编译宏UNIV_PAGE_SIZE控制），每个Page使用一个32位的int值来唯一标识，这也正好对应InnoDB最大64TB的存储容量（16Kib * 2^32 = 64Tib）。

Page结构

基本结构

一个Page的基本结构如下图所示：

每个Page都有通用的头和尾，但是中部的内容根据Page的类型不同而发生变化。

头部

Page的头部里有我们关心的一些数据，下图把Page的头部详细信息显示出来：

我们重点关注和数据组织结构相关的字段：Page的头部保存了两个指针，分别指向前一个Page和后一个Page，头部还有Page的类型信息和用来唯一标识Page的编号。

根据这两个指针我们很容易想象出Page链接起来就是一个双向链表的结构：

主体

再看看Page的主体内容：

我们主要关注行数据和索引的存储，他们都位于Page的User Records部分。

User Records

User Records占据Page的大部分空间，User Records由一条一条的Record组成，每条记录代表索引树上的一个节点（非叶子节点和叶子节点）。在一个Page内部，单链表的头尾由固定内容的两条记录来表示，字符串形式的”Infimum”代表开头，”Supremum”代表结尾。这两个用来代表开头结尾的Record存储在System Records的段里，这个System Records和User Records是两个平行的段。

InnoDB存在4种不同的Record，它们分别是：

  • 主键索引树非叶节点
  • 主键索引树叶子节点
  • 辅助键索引树非叶节点
  • 辅助键索引树叶子节点

这4种节点的Record格式有一些差异，但是它们都存储着Next指针指向下一个Record。后续我们会详细介绍这4种节点，现在只需要把Record当成一个存储了数据同时含有Next指针的单链表节点即可。

User Record在Page内以单链表的形式存在，最初数据是按照插入的先后顺序排列的，但是随着新数据的插入和旧数据的删除，数据物理顺序会变得混乱，但他们依然保持着逻辑上的先后顺序。如下图：

把User Record的组织形式和若干Page组合起来，就看到了稍微完整的形式：

如何定位一个Record
  1. 通过根节点开始遍历一个索引的B+树，通过各层非叶子节点最终到达一个Page，这个Page里存放的都是叶子节点。
  2. 在Page内从”Infimum”节点开始遍历单链表（这种遍历往往会被优化），如果找到该键则成功返回。如果记录到达了”supremum”，说明当前Page里没有合适的键，这时要借助Page的Next Page指针，跳转到下一个Page继续从”Infimum”开始逐个查找。
四种record

详细看下不同类型的Record里到底存储了什么数据，根据B+树节点的不同，User Record可以被分成四种格式。

下图种按照颜色予以区分：

主索引树非叶节点（绿色）

  • 子节点存储的主键里最小的值（Min Cluster Key on Child），这是B+树必须的，作用是在一个Page里定位到具体的记录的位置。
  • 最小的值所在的Page的编号（Child Page Number），作用是定位Record。

主索引树叶子节点（黄色）

  • 主键（Cluster Key Fields），B+树必须的，也是数据行的一部分
  • 除去主键以外的所有列（Non-Key Fields），这是数据行的除去主键的其他所有列的集合。
  • 上面两部分加起来就是一个完整的数据行。

辅助索引树非叶节点非（蓝色）

  • 子节点里存储的辅助键值里的最小的值（Min Secondary-Key on Child），这是B+树必须的，作用是在一个Page里定位到具体的记录的位置。
  • 主键值（Cluster Key Fields），非叶子节点为什么要存储主键呢？因为辅助索引是可以不唯一的，但是B+树要求键的值必须唯一，所以这里把辅助键的值和主键的值合并起来作为在B+树中的真正键值，保证了唯一性。但是这也导致在辅助索引B+树中非叶节点反而比叶子节点多了4个字节（即蓝色节点反而比红色多了4字节）。
  • 最小的值所在的Page的编号（Child Page Number），作用是定位Record。

辅助索引树叶子节点（红色）

  • 辅助索引键值（Secondary Key Fields），这是B+树必须的。
  • 主键值（Cluster Key Fields），用来在主索引树里再做一次B+树检索来找到整条记录。

主索引树的Page组织结构

结合B+树的结构和前面介绍的4种Record的内容，我们终于可以画出一幅全景图。

由于辅助索引的B+树与主键索引有相似的结构，这里只画出了主键索引树的结构图，只包含了主键非叶节点和主键叶子节点两种节点，也就是上面绿色和黄色的部分。

把上图还原成下面这个更简洁的树形示意图，这就是B+树的一部分：

注意Page和B+树节点之间并没有一一对应的关系，Page只是作为一个Record的保存容器，它存在的目的是便于对磁盘空间进行批量管理，上图中的编号为47的Page在树形结构上就被拆分成了两个独立节点。