剖析Mysql的page页
页是磁盘和内存之间交互的基本单位，通常一个页的占用16KB空间大小。页分为很多种，在Innodb中常见的数据页如下所示：
| 类型 | 描述 |
|---|---|
| 数据页 | 存储表中的数据记录 |
| 索引页 | 存储表的索引信息 |
| undo页 | 存储事务回滚信息 |
| redo页 | 存储事务提交信息 |
| 描述页 (FSP Page) | 存储表空间的元数据信息 |
| 描述页 (lnode Page) | 存储InnoDB文件系统的元数据信息 |
| BLOB页 | 存储BLOB和TEXT类型的数据 |
| 描述页(SYS_PAGE) | 存储系统表空间的元数据信息 |
| 描述页(IBUF_BITMAP_PAGE) | 存储insert buffer的位图信息 |
通常我们将存放表中数据记录的页称为数据页，将存放索引的数据页称为索引页，下图是数据页的结构图：
1、File Header
File Header针对各种类型的页都通用，主要是描述一些通用信息，如当前的页编号信息，当前页的上一页、下一页的信息等等。如下是File Header的具体信息：
InnoDB中以页为单位存放数据的，当存放某种类型的数据占用的空间非常大， In noDB会将数据使用不同的页来存储数据，存储的数据的页使用FIL_PAGE_PREV和FIL_PAGE_NEXT将数据的上一页和下一页的页号联系起来，如下图所示：
2、Page Header
用来记录该数据页中存储的记录的状态信息。如下所示的是Page Header中的信息：
| 字段 | 大小(单位：B) | 描述 |
|---|---|---|
| PAGE_N_DIR_SLOTS | 2 | 在页目录中的槽数量 |
| PAGE_HEAP_TOP | 2 | 还未使用的空间最小地址，也就是说从该地址之后就是Free Space |
| PAGE_N_HEAP | 2 | 本页中的记录的数量 (包括最小和最大记录以及标记为删除的记录) |
| PAGE_FREE | 2 | 第一个已经标记为删除的记录地址 |
| PAGE_GARBAG E | 2 | 已删除记录占用的字节数 |
| PAGE_LAST_INSERT | 2 | 最后插入记录的位置 |
| PAGE_DIRECTION | 2 | 记录插入的方向 |
| PAGE_N_DIRECTION | 2 | 一个方向连续插入的记录数量 |
| PA GE_N_RECS | 2 | 该页中记录的数量(不包括最小和最大记录以及被标记为删除的记录) |
| PAGE_MAX_TRX_ID | 8 | 修改当前页的最大事务ID，该值仅在二级索引中定义 |
| PAGE_LEVEL | 2 | 当前页在B+树中所处的层级 |
| PAGE_INDEX_ID | 8 | 索引ID，表示当前页属于哪个索引 |
| PAGE_BIR_SEG_LEAF | 10 | B+树叶子段的头部信息，仅在B+树的Root页定义 |
| PAGE_BTR_SEG_TOP | 10 | B+树非叶子段的头部信息，仅在B+树的Root页定义 |
3、行记录
行记录中存在一个记录头信息，这里我们以COMPACT行格式为例画出其记录头信息的图：
| 记录头信息中字段 | 描述 |
|---|---|
| deleted_flag | 逻辑删除标记（0未删除，1已删除） |
| min_rec_flag | B+树中每层非叶子结点中的最小的目录项记录。 |
| n_owned | 一个页面被分若干组后，最大的那个记录用于保存组中所有的记录条数。 |
| heap_no | 表示当前记录在页面堆中的相对位置。 |
| record_type： | 表示当前的记录类型： 0：普通记录。 1：B+树非叶子结点目录项记录。 2：表示Infimum记录。 3：表示Supremum记录。 |
| next_record | 表示下一条记录的相对位置，也就是链表。这个属性非常重要，它表示从当前记录的真实数据到下一个记录的真实数据的距离。指向记录头信息和主键列 |
Infimum ：伪行记录下边界，主要记录该页中比任何主键值都要小的值。
Supemum ：伪行记录上边界，主要记录该页中比任何主键值都要大的值。
这两条记录的构造十分简单，都是由5字节的记录头信息和8字节的一个固定部分组成，如下是其组成部分的：
由于这两条记录是Mysql自动生成的，所以并不存放在page页的User Records部分，而是被单独放在一个称为Infimum+Supremum的部分，下图展示了两个记录存储的信息：
最大记录和最小记录分别的heap_no值是1、0，那么真实的数据记录heap就是从2开始统计，如下是行数据之间的关系：
此时如果要删除一条数据的话，将记录删除后设置deleted_flag置为1，然后将上一条数据的next_record指针指向下一条记录，此时行数据之间的联系如下所示：
其实不管怎么对页中的记录做增删改操作，lnnoDB始终会维护一条记录的单链表，链表中各个节点是按照主键值由小到大的顺序连接起来的。
4、Free Space
Free Space表示的是空闲的空间，此部分的大小是不固定的，因为随着User Records变大，Free Space会不断变小。
5、Page Directory
数据记录在page页中是按照主键值从小到大的顺序串联成为的一个单向链表，因此查询只能以第一个节点开始依次向后遍历所有节点来查询。但是如果数据量比较大的时候就会出现查询性能问题，于是InnoDB提出了Page Directory来解决这个问题。
Page Directory分组规则：Infimum记录所在的分组只能有一条记录（该分组只有Infimum）；Supremum记录所在的分组只能在1～8条记录之间；剩下的其他记录所在的分组只能在4～8条记录之间。这样的目的在于除了第一组之外其余的组中数据基本是平均分配的。
Page Directory分组步骤：
（a）初始状态下（无User Records中的数据记录）一个页中只有两条数据，即Infimum和Supremum，所以应该分为两组。
（b）每当插入一条记录时，都会从目录中找到对应记录的主键值比待插入记录的主键值大的，添加数据然后把该槽对应的n_owned加1。
（3）在一个组中的记录等于8的情况下再次插入一条记录时，会将组中的记录拆分成两个组（一个组中4条记录，另一个组中5条记录）并且在拆分过程中会在Page Directory中新增一个槽，并记录分组中最大的那条数据的偏移量。如下图所示：
这个分组之后在一个数据页中查找指定主键值的记录的过程分为两步：
（a）通过二分法确定该记录所在槽，并找到该槽中主键值最小的那条记录
（b）通过记录的next_record属性遍历该槽所在组中的各个记录
通过二分查找的方式可以提高数据上数据的查询效率。
6、File Trailer
数据页需要被读写的，假设数据页在写了一半页的时候电源被拔掉了，此时就存在了数据的丢失问题，所以为了保证数据页的一个正确性，还引入了校验机制，这个就是File Trailer。File Traler由8个字节组成，分为2个小部分：第一个是前4个字节代表页的校验和；第二个是后4个字节代表页面被最后修改时对应的日志序列位置。
7、B+树的形成
假设现在数据量非常的大的情况下，如果要查询一条行数，最土的办法我们可将表空间里面的每一页都拉出来，依次判断里面的行数据是不是我们要找的行数据，如下所示：
如果数据量特别的大就存在查询性能慢的问题，因为每次查询都需要遍历所有的行数据。为了提高效率，我们可以在每一个数据页里面选出id最小的行数以及所在页的页号，将他们组成一个新的行数据，放到新生成的数据页中，如下所示：
这个新的数据页（page5）和之前的数据页（page1和page8）结构没有什么太大的区别，新生成的page页大小依然是16kb，同时为了与之前的数据做区分，新的数据页中加入页层级的信息并取个名字叫索引页，如下所示：
当查询id=3的数据，先在非叶子结点上的索引页（page5）上找到id=3位于哪个page页上，找到对应的page页之后再去其使用槽的方式二分查询数据。
当数据变多了后，我们可以再通过类似的方法再增加树的层级。值得注意的点是数据页的页号它在磁盘中不一定是连续的，即就是可能是分散的，如下图所示：
至此我们介绍完成了数据页的结构的基本知识。
