【MySQL】Page页的结构

MySQL与磁盘交互基本单位 -- page

一个扇区大小是 512B，而系统读取磁盘是以块为单位的，一般为 8 个扇区，所以一个块一般为 4KB，如下所示：

而 MySQL 进行 IO 的基本单位是 16KB，也就是 "页"。

我们可以通过 "innodb_page_size" 来查查看当前 mysql 的页大小：

mysql> show global status like 'innodb_page_size';
+------------------+-------+
| Variable_name    | Value |
+------------------+-------+
| Innodb_page_size | 16384 |  --16KB大小
+------------------+-------+
1 row in set (0.01 sec)

所以 MySQL 和操作系统、磁盘的关系大概就是如下图所示：

为什么要以页为交换单位呢❓❓❓

在 .ibd 文件中最重要的结构体就是 Page(页)，页是内存与磁盘交互的最小单元，默认大小为 16KB，每次内存与磁盘的交互至少读取一页，所以在磁盘中每个页内部的地址都是连续的，之所以这样做，是因为在使用数据的过程中，根据局部性原理，将来要使用的数据大概率与当前访问的数据在空间上是临近的，所以一次从磁盘中读取一页的数据放入内存中，当下次查询的数据还在这个页中时就可以从内存中直接读取，从而减少磁盘 I/O 提高性能。

页的结构

在 MySQL 中有多种不同类型的页，最常用的就是用来存储数据和索引的"索引页"，也叫做"数据页"（innodb中索引和数据是存储在一起的），但不论哪种类型的页都会包含页头和页尾，页的主体信息使用数据行进行填充，数据页的基本结构如下图所示：

注意上面图中的页头和页尾，应该更具体为页文件头(File Header)、页文件尾(File Trailer)，因为还有一个概念叫做页头(Page Header)，下面会介绍！

页文件头与页文件尾

1. 页文件头(File Header)：文件头位于页面起始位置，占 38B。它记录了页面的全局信息，用于物理存储管理和一致性校验。常见字段包括：

2. 页文件尾(File Trailer)：存储了关于数据页的校验和和其他元数据，其大小固定为 8B。页尾包含以下内容：

1. 校验和：用于验证数据页的完整性和一致性。
2. LSN（Log Sequence Number）：记录页的最后修改日志序列号，用于恢复和事务日志的管理。

可以看出页与页之间存在字段 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 进行连接，即用双向链表连接页。

页头

页头紧跟在页文件头之后，占用 56B，仅存在于索引类型页面（即存放数据或索引记录的“数据页”）中，页头记录了页面内部的数据状态和管理信息，用于控制行记录的存储与访问。典型字段包括：

页主体

数据行存储了实际的数据记录。每行的大小取决于表的定义和存储的数据，每行的最小开销为 5B（记录头信息，包含记录的类型、删除标志、记录长度等）。

每当创建一个新页，都会自动分配两个行，一个是页内最小行 Infimun，另一个是页内最大行 Supremun，这两个行并不存储任何真实信息，而是做为数据行链表的头和尾，第一个数据行有一个记录下一行的地址偏移量的区域 next_record 将页内所有数据行组成了一个单向链表，此时新页的结构如下所示：

当向一个新页插入数据时，将 Infimun 连接第一个数据行，最后一行真实数据行连接 Supremun，这样数据行就构建成了一个单向链表，更多的行数据插入后，会按照主键从小到大的顺序进行链接，如下图所示：

举个例子，其中每行数据可以这样子计算：

CREATE TABLE students (
    student_id INT,
    name VARCHAR(50),
    age INT,
    score INT
) ENGINE=InnoDB;

• student_id：4字节
• name：假设存储的字符串长度为20字节（实际大小取决于存储的字符串长度）
• age：4字节
• score：4字节
• 记录头信息：5字节

因此，每行的总大小为：4 + 20 + 4 + 4 + 5 = 37字节

☠ 注意事项：

• 行溢出：如果一行数据太大（超过页的大小），InnoDB 会将部分数据存储在其他页中，并在当前页中存储一个指针。
• 页的填充因子：InnoDB 默认会将页填充到约 15/16 满，以保留一些空间用于插入和更新操作。

页目录

当按主键或索引查找某条数据时，最直接简单的方法就是从头行 infimun 开始，沿着链表顺序逐个比对查找，但一个页有 16KB，通常会存在数百行数据，每次都要遍历数百行，无法满足高效查询，为了提高查询效率，InnoDB 采用二分查找来解决查询效率问题！

具体实现方式是，在每一个页中加入一个叫做页目录 PageDirectory 的结构，将页内包括头行、尾行在内的所有行进行分组，约定头行单独为一组，其他每个组最多 8 条数据，同时把每个组最后一行在页中的地址，按主键从小到大的顺序记录在页目录中，页目录中的每一个位置称为一个槽，每个槽都对应了一个分组，一旦分组中的数据行超过分组的上限 8 个时，就会分裂出一个新的分组。

后续在查询某行时，就可以通过二分查找，先找到对应的槽，然后在槽内最多 8 个数据行中进行遍历即可，从而大幅提高了查询效率，这时一个页的核心结构就完成了！

例如要查找主键为 6 的行，先比对槽中记录的主键值，定位到最后一个槽 2，再从最后一个槽中的第一条记录遍历，第二条记录就是我们要查询的目标行。

多页存储情况

以 innodb 为例，实际上存储的时候所有叶子节点都是数据页，而非叶子节点是管理数据页的索引页，如下图所示：（图中页目录指针应该指向每组的末尾数据才对，而图中画成了指向每组的开头数组，这个要注意一下！）

从上图我们也可以看出，其实 mysql 中 InnoDB 存储引擎的索引结构，就是我们数据结构所学的 B+ 树结构！

使用 B+ 树结构，意味着有什么优势呢❓❓❓

1. B+ 树中数据都是存放在叶子节点中的，也就是说非叶子节点中没有存放数据，只有目录项，这意味着非叶子节点可以存储更多的目录项，而只要目录页一多的话，那么这棵树，就会越趋向于 ”矮胖型“ 的树，即深度很小的树，换言之就是 IO 次数更少。
2. B+ 树的叶子节点是以链表的形式串联起来的，范围查询非常方便。（且对于没有索引的字段进行全文扫描的时候也是很方便的）
3. 在相同树高的情况下，查找任一元素的时间复杂度都一样，性能均衡。

• 使用平衡二叉树搜索树的缺陷：
  • 平衡二叉树搜索树的高度是 logn，这个查找次数在内存中是很快的。但是当数据都在磁盘中时，访问磁盘速度很慢，在数据量很大时，logn 次的磁盘访问，是一个难以接受的结果，因为深度太大了，这样子会导致 IO 次数过多而效率低！
• 使用哈希表的缺陷：
  • 哈希表的查找时间复杂度很优秀，为 O(1)，但是一些极端场景下某个位置冲突很多，导致访问次数剧增，也是难以接受的。并且哈希表对于范围查找的支持不是很友好，这点就很打击了！