Mysql的页结构详解

1.数据库的存储结构：页

索引结构为我们提供了搞笑的查找方式，索引信息和数据记录都在保存在文件上的，准确地说，是保存在“页”结构中。

1.1磁盘与内存的基本交互单位：页

InnoDB将数据划分为若干个页，InnoDB中的页的默认大小是16kb。页是磁盘与内存交互的最小单位，也就是说，每次内存从磁盘读取数据，最少会读取一个页的内容，相应地，每次内存往磁盘写数据，也是最少一个页。通常情况下，一个页中往往会有多条记录，当我们要查询某个页中的一条记录时，内存会将这一页的数据都完整地加载过来，也就是说数据库IO操作的最小单位就是页。

1.2页结构描述

页a，页b，页c…这些页可以不在物理空间上保持连续，只需要通过双向指针进行关联，保持逻辑上的连续即可。每个数据页的记录都会按照主键值从小到大组成一个单向链表。每个页都会为其记录生成一个页目录 ,通过主键查找某条记录的时候，可以在页目录中通过二分查找快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

1.3页大小

在InnoDB引擎中，页的默认大小是16kb，我们可以通过如下命令来进行查看：show variables like 'innodb_page_size';

1.4页的上层结构

在数据库中，除页结构之外，还存在区（Extent）、段（Segment）和表空间(tableSpace)的概念。关系如下图：

区(Extent)是页的上级结构，通常来说，一个区中会分配64个连续的页。一个页是16kb，一个区也就是64*16kb=1mb。
段(segment)是区的上级结构，由一个或多个区组成，区在文件系统是一个连续分配的空间(在InnoDB中是64个连续的页)，但是在段中不需要保证区和区是物理上连续的。段是数据库中的分配单位，不同类型的数据库对象以不同的段形式存在。当我们创建表、索引的时候，就会创建相应的段。比如我们创建一张表，就会创建一个表段；创建一个索引，就会创建一个索引段。
表空间(tableSpace)是一个逻辑容器，表空间存储的对象是段，在一个表空间会有一个或多个段，但是一个段只会属于一个表空间。数据库由一个或多个表空间组成，表空间从管理上划分，又可以分为 系统表空间、用户表空间、撤销表空间、临时表空间等。

2.页的内部结构

页如果按类型进行划分的话，可以分为 数据页（保存B+树节点）、系统页、undo页、事务数据页等。其中我们最常使用的是数据页。
数据页16kb的存储空间被分为7个部分，分别是文件头（File Header）、页头（Page Header）、最大最小记录（infimum和supremum）、用户记录（User Records）、空闲空间（Free Space）、页目录（Page Directory）和文件尾（File Tailer）。
页结构的示意图如下所示：

第1部分：文件头（File Header）和文件尾（File Tailer）

首先是 文件通用部分，文件头和文件尾。

文件头（38字节）

主要作用：描述各种页的通用信息。比如页的编号，其上一页、下一页是谁等。
结构：

文件头 重要参数描述

FIL_PAGE_OFFSET(4字节)

页号，每一个页都有自己的唯一页号，类似我们的身份证，通过页号，InnoDB可以定位到唯一的页。

FIL_PAGE_TYPE(2字节)

代表页的当前类型。
下面是所有类型，常用的用粗体标示。

FILE_PAGE_PREV(4字节)和FILE_PAGE_NEXT(4字节)

页在物理空间上不一定是连续的，需要通过每个页节点保存其上一个页及下一个页的页号，来形成双向链表，以保证页在逻辑上的连续性。

FILE_PAGE_SPACE_OR_CHECKSUM(4字节)

代表当前页的校验和。所谓校验和，就是针对某两个比较长的字符串，我们要比较两个字符串是否相等的时候，不需要对两个字符串的每个字符进行一个一个的比较，只需要通过一定的算法，将两个字符串转换成较短的两个字符串，比较这两个字符串是否相等就行了，如果这两个短的字符串不行等，那么原本的两个字符串也肯定不相等。这样可以一定程度缩短校验时间。

文件头 和 文件尾 都有FILE_PAGE_SPACE_OR_CHECKSUM这个属性。

作用：内存和磁盘是以页为最小单位进行数据交互的，如果某个页在内存中被进行了一定的修改，在修改完成后的某个时间点，会将内存中的页回写到磁盘中。如果某个页的数据在回写到一半的时候，突然断电了，造成了该页数据的不完整。那么如何校验一个页的数据是否传输完整呢？就是通过比较文件头和文件尾的FILE_PAGE_SPACE_OR_CHECKSUM。如二者的校验和(checksum)值不相等，则说明数据传输不完整，需要重新传输。否则就说明是完整传输。

具体流程：当一个页在内存中被进行了修改，在同步到磁盘之前，会现将校验和(checksum)计算出来，因为文件头(File Header)在页(page)之前，所以在页同步到磁盘之前，会先将文件头同步到磁盘，此时磁盘的校验和也会被同步过去。然后进行页数据的同步，页同步完后则会进行文件尾的同步。如果同步成功，那么文件头和文件尾的校验和应该是一致的。如果中间发生了断电之类的异常，导致数据只同步了一半，那么文件头的校验和是新的，文件尾的校验和是旧的，二者就会不一致，说明同步不完整。

FIL_PAGE_LSN(8字节)

页面最后被修改时对应的日志序列位置（Log Sequence Number）.

文件尾(8字节)

1. 前面4个字节代表页的校验和
   这部分主要是和File Header中的校验和进行验证
2. 后面4个字节代表页面最后被修改时对应的日志序列位置（LSN）
   这部分主要也是为了校验页的完整性，如果文件尾和文件头的LSN值校验不成功的话，说明同步过程出现了问题。

第2部分：最大最小记录、用户记录、空闲空间

空闲空间(Free Space)

我们存储的记录会按照指定的行格式存储到User Records(用户记录)中。但在最开始生成页的时候，其实是没有User Records这个部分的。每当我们插入一条记录，都会从Free Space的储存空间中申请一个记录大小的空间分配到User Records。当Free Space的空间完全被User Records替代的话，就说明这个页已经使用完了，后续新增记录需要申请新的页。

用户记录(User Records)

User Records中的记录按照指定的行格式一条一条的储存在User Records中，相互之间形成单链表。

最小最大记录(Infimum和Supremum)

记录如何比较大小呢？其实就是比较记录的主键值，比如我们插入4条记录，主键值分别是1,2,3,4.那么这条记录就是一次递增的。
InnoDB规定的最小记录和最大记录构造十分简单，就是5字节的记录头信息和8字节的一个固定部分组成。如下图：

这两条记录不是我们定义的，所以这两条记录不存储在User Records中，而是储存在Infimum+Supremum中。

第3部分：页目录(Page Directory)、页头(Page Header)

3.1 页目录

为什么要有页目录？

在页中，记录是以单链表的形式存在的，单链表的特性就决定了其在新增、删除是比较快的，但是对于查找是比较慢的，需要一个一个遍历，时间复杂度为O(n)。对于这种情况，在页结构中单独设计了页目录，专门给记录做目录，通过二分查找的方式进行数据检索，提升查询效率。

工作原理

1. 将所有记录分为几组，这些记录中包括最小和最大记录，但是不包括已经被标记删除的记录
2. 第1组，也就是最小记录所在的分组，只有最小记录这一条记录。最后一组，也就是最大记录所在的分组，会有1-8条记录。其余组的记录数量在4-8之间。
3. 每个组的最后一条记录会存储该组一共有多少条记录，作为n_owned字段的值。
4. 页目录用来存储每组最后一条记录的地址偏移量，这些地址偏移量会按照先后顺序存储起来，每组的地址偏移量也被称之为槽(slot)，每个槽相当于指针指向每个组的最后一条记录。