MySQL存储引擎内部之：`InnoDB`的`Page`结构：`Page`头部、`记录`、`空闲空间`和`尾部`的布局。 - 智猿学院-前后端，数据库，人工智能，云计算等领域前沿技术讲座

InnoDB Page结构剖析：深入理解数据存储的基石

大家好！今天我们来深入探讨MySQL InnoDB存储引擎中至关重要的概念：Page结构。InnoDB将数据存储在磁盘上，而Page是InnoDB管理数据的最小单元，默认大小为16KB。理解Page的结构布局对于理解InnoDB的性能优化、数据存储机制至关重要。

Page由多个部分组成，主要包括：Page Header（页面头部）、User Records（用户记录）、Free Space（空闲空间）和 Page Trailer（页面尾部）。我们将逐一分析这些组成部分，并结合实际代码示例，深入理解它们的作用和相互关系。

1. Page Header (页面头部)

Page Header 位于Page的起始位置，占用固定的空间，用于存储关于Page的元数据信息。这些元数据对于InnoDB的管理和维护至关重要。Page Header 包含以下重要信息：

字段名	数据类型	长度 (字节)	描述
`FIL_PAGE_OFFSET`	`unsigned int`	4	当前页面的页号（Page Number）。InnoDB使用页号唯一标识每个页面。
`FIL_PAGE_TYPE`	`unsigned short`	2	页面类型。例如：数据页、索引页、Undo页等。不同的页面类型有不同的结构。
`FIL_PAGE_PREV`	`unsigned int`	4	前一个页面的页号。用于将页面链接成双向链表。
`FIL_PAGE_NEXT`	`unsigned int`	4	后一个页面的页号。用于将页面链接成双向链表。
`FIL_PAGE_SPACE_ID`	`unsigned int`	4	表空间的ID。InnoDB将数据存储在表空间中，每个表空间有唯一的ID。
`FIL_PAGE_LSN`	`unsigned long long`	8	页面最后被修改时的日志序列号（Log Sequence Number）。用于崩溃恢复。
`PAGE_MAX_TRX_ID`	`unsigned long long`	8	修改当前页的最大事务ID。
`PAGE_LEVEL`	`unsigned short`	2	当前页在B+树索引中的层级。根节点为0，叶子节点层级最高。
`PAGE_INDEX_ID`	`unsigned long long`	8	索引ID。每个索引在表空间中都有一个唯一的ID。
`PAGE_N_DIR_SLOTS`	`unsigned short`	2	Page Directory 中 slot 的数量。Page Directory 用于快速查找记录。
`PAGE_HEAP_TOP`	`unsigned short`	2	堆顶地址。用于动态分配空间。
`PAGE_N_HEAP`	`unsigned short`	2	堆中记录的数量。包括最小记录和最大记录。
`PAGE_FREE`	`unsigned int`	4	指向空闲空间起始位置的指针。
`PAGE_GARBAGE`	`unsigned int`	4	已删除记录占用的字节数。当达到一定阈值时，会触发碎片整理。
`PAGE_LAST_INSERT`	`unsigned short`	2	最后插入记录的位置。
`PAGE_DIRECTION`	`unsigned short`	2	记录插入的方向。用于优化记录插入性能。
`PAGE_N_RECS`	`unsigned short`	2	当前页面中记录的数量（不包括最小记录和最大记录）。
`PAGE_NEWEST_REC`	`unsigned long long`	8	页面中最新插入的记录的相对偏移量。
`PAGE_FILE_FLUSH_LSN`	`unsigned long long`	8	页面被刷新到磁盘时对应的 LSN。

通过这些信息，InnoDB可以有效地管理和维护页面，保证数据的完整性和一致性。

2. User Records (用户记录)

User Records 存储实际的用户数据。对于数据页，它存储表中的行数据；对于索引页，它存储索引键值和指向数据页的指针。User Records 的存储方式依赖于页面的类型和表的行格式（ROW_FORMAT）。常见的行格式包括：Redundant、Compact、Dynamic、Compressed。

每条记录都有一个记录头（Record Header），记录头包含以下信息：

字段名	数据类型	长度 (字节)	描述
`delete_mask`	`bit`	1	删除标记。标记记录是否被删除。
`min_rec_mask`	`bit`	1	最小记录标记。标记记录是否为最小记录。
`n_owned`	`unsigned short`	4	当前记录拥有的槽（Slot）的数量。用于Page Directory。
`heap_no`	`unsigned short`	13	记录在堆中的编号。
`record_type`	`unsigned short`	3	记录类型。0表示普通记录，1表示B+树非叶子节点记录，2表示最小记录，3表示最大记录。
`next_record`	`unsigned short`	16	指向下一条记录的偏移量。用于将记录链接成单向链表。

next_record 字段使用相对偏移量，指向页面内的下一条记录。通过 next_record，InnoDB 可以遍历页面内的所有记录。

代码示例：模拟 User Record 结构

#include <iostream>
#include <string>
#include <vector>

struct RecordHeader {
  unsigned char delete_mask : 1;
  unsigned char min_rec_mask : 1;
  unsigned char n_owned : 4;
  unsigned char heap_no : 7; // 使用7位表示heap_no
  unsigned char record_type : 2;
  unsigned short next_record;
};

struct UserRecord {
  RecordHeader header;
  std::string data;
};

int main() {
  UserRecord record1;
  record1.header.delete_mask = 0;
  record1.header.min_rec_mask = 0;
  record1.header.n_owned = 0;
  record1.header.heap_no = 1;
  record1.header.record_type = 0;
  record1.header.next_record = 20; // 假设下一条记录偏移量为20
  record1.data = "This is record 1";

  UserRecord record2;
  record2.header.delete_mask = 1; // 标记为已删除
  record2.header.min_rec_mask = 0;
  record2.header.n_owned = 0;
  record2.header.heap_no = 2;
  record2.header.record_type = 0;
  record2.header.next_record = 0; // 假设这是最后一条记录
  record2.data = "This is record 2 (deleted)";

  std::cout << "Record 1 data: " << record1.data << std::endl;
  std::cout << "Record 2 data: " << record2.data << std::endl;

  return 0;
}

这个简单的 C++ 代码示例模拟了 RecordHeader 和 UserRecord 的结构。RecordHeader 使用位域（bit field）来紧凑地存储信息，next_record 用于链接记录。

3. Free Space (空闲空间)

Free Space 是页面中未被使用的空间。当插入新的记录时，InnoDB 会从 Free Space 中分配空间。当删除记录时，被删除的记录所占用的空间会被标记为 Free Space。

InnoDB 使用链表来管理 Free Space。PAGE_FREE 字段指向 Free Space 链表的起始位置。当需要分配空间时，InnoDB 会从链表中查找足够大小的空闲块。

当 Free Space 不足以容纳新的记录时，InnoDB 会尝试进行碎片整理，将页面中的碎片空间合并成更大的连续空间。如果碎片整理后仍然无法满足需求，InnoDB 可能会分裂页面，或者将记录移动到其他页面。

4. Page Directory (页面目录)

Page Directory 位于 User Records 和 Free Space 之间，它是一个槽（Slot）的数组，用于加速记录的查找。每个槽指向页面中的一组记录。通过 Page Directory，InnoDB 可以快速定位到目标记录所在的槽，而无需遍历所有记录。

Page Directory 的工作原理类似于哈希索引。InnoDB 将页面中的记录分成若干组，每组记录对应一个槽。槽中存储的是该组中最大记录的偏移量。当查找记录时，InnoDB 首先在 Page Directory 中查找合适的槽，然后在该槽对应的记录组中进行线性查找。

PAGE_N_DIR_SLOTS 字段存储 Page Directory 中槽的数量。槽的数量会影响查找性能。过少的槽会导致每个槽对应的记录组过大，线性查找的效率降低；过多的槽会占用额外的空间。

代码示例：模拟 Page Directory 查找

#include <iostream>
#include <vector>
#include <string>

// 假设 UserRecord 和 RecordHeader 的定义如上
// 模拟 Page 结构，包含 User Records 和 Page Directory
struct Page {
  std::vector<UserRecord> records;
  std::vector<unsigned short> directory; // 存储槽中最大记录的偏移量
  unsigned short page_size = 16384; // 16KB
};

// 模拟查找记录
UserRecord* findRecord(Page& page, const std::string& key) {
  // 假设 key 是记录的data字段，并已排序

  // 1. 在 Page Directory 中查找合适的槽
  int slot_index = -1;
  for (int i = 0; i < page.directory.size(); ++i) {
    // 假设槽中的偏移量指向的是该槽中最大记录的索引
    int record_index = page.directory[i];
    if (record_index >= page.records.size()) continue; // 检查索引是否越界

    if (page.records[record_index].data >= key) {
      slot_index = i;
      break;
    }
  }

  // 2. 在槽对应的记录组中进行线性查找
  if (slot_index != -1) {
    int start_index = (slot_index == 0) ? 0 : page.directory[slot_index - 1] + 1;
    int end_index = page.directory[slot_index];

    for (int i = start_index; i <= end_index && i < page.records.size(); ++i) { // 检查索引是否越界
      if (page.records[i].data == key) {
        return &page.records[i];
      }
    }
  }

  return nullptr; // 未找到
}

int main() {
  // 创建一个 Page
  Page page;

  // 添加一些记录 (需要保证排序)
  UserRecord r1, r2, r3, r4;
  r1.data = "Alice";
  r2.data = "Bob";
  r3.data = "Charlie";
  r4.data = "David";

  page.records.push_back(r1);
  page.records.push_back(r2);
  page.records.push_back(r3);
  page.records.push_back(r4);

  // 创建 Page Directory (简单示例：每个槽指向一个记录)
  page.directory.push_back(0);
  page.directory.push_back(1);
  page.directory.push_back(2);
  page.directory.push_back(3);

  // 查找记录
  UserRecord* foundRecord = findRecord(page, "Bob");
  if (foundRecord != nullptr) {
    std::cout << "Found record: " << foundRecord->data << std::endl;
  } else {
    std::cout << "Record not found." << std::endl;
  }

  return 0;
}

这个示例代码模拟了 Page Directory 的查找过程。findRecord 函数首先在 Page Directory 中查找合适的槽，然后在该槽对应的记录组中进行线性查找。这个示例非常简化，实际的 InnoDB 实现会更加复杂，例如槽的数量不是固定的，而是动态调整的。

5. Page Trailer (页面尾部)

Page Trailer 位于Page的尾部，占用固定的空间，主要包含以下信息：

字段名	数据类型	长度 (字节)	描述
`PAGE_CHECKSUM`	`unsigned int`	4	页面的校验和。用于检测页面是否损坏。
`PAGE_LSN`	`unsigned long long`	8	页面最后被修改时的日志序列号（Log Sequence Number）。与 Page Header 中的 LSN 相同，用于双重校验。

PAGE_CHECKSUM 用于检测页面是否损坏。InnoDB 在将页面写入磁盘时，会计算页面的校验和，并将校验和存储在 Page Trailer 中。在读取页面时，InnoDB 会重新计算页面的校验和，并与 Page Trailer 中的校验和进行比较。如果两个校验和不一致，则说明页面已损坏。

PAGE_LSN 与 Page Header 中的 FIL_PAGE_LSN 相同，用于双重校验，确保 LSN 的正确性。

总结：理解Page结构的重要性

Page是InnoDB存储引擎中数据存储的基本单元。Page Header 记录了页面的元数据信息，用于InnoDB的管理和维护；User Records 存储实际的用户数据；Free Space 用于动态分配空间；Page Directory 加速记录的查找；Page Trailer 用于检测页面是否损坏。深入理解Page的结构布局，可以帮助我们更好地理解InnoDB的性能优化、数据存储机制和故障恢复机制，从而更好地使用和管理MySQL数据库。