学习《MySQL是怎样运行的》，感谢作者！

不同类型的页简介 #

页是InnoDB管理存储空间的基本单位，1个页的大小一般是16KB

InnoDB为了不同目的设计多种不同类型的页，包括存放表空间头部信息 的页、存放Change Buffer 信息的页、存放INODE信息的页、存放undo 日志信息的页

这里说的是存放表中记录的那种类型的页，这种存放记录的页称为索引页（INDEX页）

暂时称之为数据页

数据页结构快览 #

1个页有16KB，这部分存储空间被划分为了多个部分（7部分），不同部分有不同的功能

记录在页中的存储 #

每插入一条记录，从Free Space申请一个记录大小的空间，并将这个空间划分到UserRecords部分。当FreeSpace部分的空间全部被UserRecords部分替代掉后，意味着该页用完。如果再插入，就需要申请新的页

记录头信息的秘密 #

mysql> CREATE TABLE page_demo(
      c1 INT,
      c2 INT,
      c3 VARCHAR(10000),
      PRIMARY KEY(c1)
      ) CHARSET=ascii ROW_FORMAT=COMPACT;
Query OK, 0 rows affected (0.03 sec)

简化一下（忽略其他非讲解的部分信息）

#插入4条记录
mysql> INSERT INTO page_demo VALUES(1,100,'aaaa'),(2,200,'bbbb'),(3,300,'cccc'),(4,400,'dddd');
Query OK, 4 rows affected (0.01 sec)
Records: 4  Duplicates: 0  Warnings: 0

UserRecords部分的存储结构

deleted_flag #

标记当前记录是否删除：0表示没有被删除，1表示记录被删除

被删除的记录不从磁盘溢出，因为移除后还需要在磁盘上重新排列其他的记录，带来性能消耗
被删除掉的记录会组成一个垃圾链表，记录在这个链表中占用的空间称为可重用空间，如果之后有新纪录插入到表中，就可能覆盖掉被删除的记录所占用的存储空间
delete_flag设置为1和将被删除的记录加入到垃圾链表其实是两个阶段，后面介绍undo日志会详细讲解删除操作的详细执行过程

min_rec_flag #

B+树每层非叶子节点中的最小的目录项记录都会添加该标记

n_onwed #

heap_no #

• 记录一条一条亲密无间排列的结构称之为堆（heap）。把一条记录在堆中的相对位置称之为heap_no

• 为了管理这个堆，每一条记录在堆中的相对位置称为heap_no。

• 页面前面的记录heap_no比后面的小，且每新申请一条记录的存储空间，该条记录比物理位置在它前面的那条记录的heap_no大1

• 由上可知，4条记录的heap_no为2，3，4，5

• InnoDB的设计者自动给每个页添加了两条记录（称之伪记录或虚拟记录）。一条代表页面中的最小记录（也称Infimum记录美 [ɪn'faɪməm]），一条代表页面中的最大记录（也称Supremumsu'pri: m en)。这两条伪记录也算作堆的一部分

  比较完整记录的大小就是比较主键的大小

  规定，用户的任何记录都比Infimum记录大，比supremum记录小

Infimum和Supremum记录 #

单独放在一个称为Infimum和Supremum的部分

堆中记录的heap_no值在分配之后就不会发生改动了（即使删除了堆中某条记录）

record_type #

表示当前记录的类型，0表示普通记录（上面自己插入的记录是），1表示B+树非叶节点的目录项记录（后面索引会讲到），2表示Infimum记录，3表示Supremum记录

next_record #

表示从当前记录的真实数据到下一条记录的真实数据的距离

如果该属性值为正数， 说明当前记录的下一条记录在当前记录的后面: 如果该属性值为负数，说明当前记录的下一条记录在当前记录的前面

下一条记录，指的是按照主键值由小到大的顺序排列的下一条记录
Infimum的下一条记录是本页中主键值最小的用户记录，本页中主键值最大的用户记录的下一条记录就是Supremum记录

如上，记录按照主键从小到大的顺序形成了一个单向链表
Supremum记录的next_record值为0，即没有下一条记录了，如果删除其中一条记录

Supremum记录的n_owned由5变成了4
InnoDB始终维护记录的一个单向链表，链表中的各个节点是按照主键值由小到大的顺序链接起来的

为啥next_record是指向记录头信息和真实数据之间的位置，而不是整条记录的开头。

1. 这个位置刚好，向左是记录头信息，向右是真实数据
2. 由于变长字段长度列表、NULL值列表中的信息都是逆序存放，这样可以使记录中靠前的字段和他们对应的字段长度信息在内存中的距离更近，提高高速缓存命中率

如果第2条记录被重新插入

PageDirectory（页目录） #

解释 #

直接遍历的话，时间复杂度太高

说明：
将所有记录（包括Infimum和Supremum记录，不包括已经移除到垃圾链表的记录划分为几个组

每个组的最后一条记录（组内最大的那条记录）相当于带头大哥，其余记录相当于小弟。

带头大哥记录的头信息中的n_owned属性表示改组内共有几条记录

操作：

将每个组中最后一条记录（组内最大记录）在页面中的地址偏移量(该记录的真实数据与页面中第0个字节之间的距离)单独提取出来，按顺序存储倒靠近页尾部的地方（这个地方就是PageDirectory）
页目录的偏移地址称为槽(Slot)，每个槽占用2字节，页目录由多个槽组成

1页有16KB，即16384字节，而2字节可以表示的地址偏移量为2^16-1=65535 >16384，所以用2字节表示一个槽足够了

举例 #

假设page_demo表中有6条记录（包括Infimum和Supremum）

注意，Infimum记录的n_owned值为1，Supremum记录的n_owned值为5
且槽对应的记录（值）越小，越靠近FileTrailer

用指针形式表示

划分依据
规定：对于Infimum记录所在的分组只能有1条记录，Supremum记录所在分组记录数在1_{8条之间，剩下的分组中记录的条数范围只能是4}8条
简化：

步骤：

1. 初始情况，数据页中只有Infimum和Supremum两条记录，分属两个分组
   页目录也只有两个槽：分别代表Infimum记录和Supremum记录在页中的偏移量

2. 之后每插入一条记录，都会从页目录中找到对应记录的主键值比待插入记录的主键值大并且差值最小的槽（从本质上看，槽是一个组内最大那条记录在页面中的地址偏移量，通过槽可以快速找到对应的记录的主键值)。然后把该槽对应的记录的n_owned值加1，表示本组内又添加了一条记录，直到该组中的记录数等于8

3. 当一个组中的记录数等于8后，再插入一条记录，会将组中的记录拆分成两个组，其中一个组中4条记录，另一个5条记录。且会在页目录中新增一个槽，记录这个新增分组中最大的那条记录的偏移量

4. 为了演示快速查找，再添加12条记录 ，总共16条

   一个槽占用2个字节，且槽之间是挨着的，每个槽代表的主键值都是从小到大排序的，所以可以使用二分法快速查找

   这里给槽编号：0，1，2，3，4。最低的槽就是low=0，最高的槽就是high=4
   

5. 假设我们要查找主键值为6的记录

   1. (0+4)/2=2，槽2代表的主键值8>6，所以high=2,low不变=0
   2. (0+2)/2=1，槽1代表的主键值4<6，所以low=1,high不变=2
   3. high-low=1，又因为槽记录的是最大值，所以不在槽1中，而是在槽2中
      沿着单项列表遍历槽2中的记录：如何遍历，先找到槽1的地址，然后它的下一条记录就是槽2中的最小记录 值为5，从值5的记录出发遍历即可（由于一个组中包含的记录条数最多是8，所以代价极小

6. 总结
   通过二分法确定槽，找到槽所在分组中主键值最小的那条记录
   然后通过记录的next_record属性遍历该槽所在记录的各个记录

PageHeader（页面头部） #

页结构的第2部分，占用固定的56字节，专门存储各种状态信息
PageHeader的结构及描述

PAGE_N_DlR SLOTS - PAGE_N_RECS 的作用应该是清除的，这里有两个解释一下：
PAGE_DIRECTION：加入新插入的一条记录的主键值比上一条记录的主键值大，我们说这条记录的插入方向是右边，反之则是左边。用来表示最后一条记录插入方向的状态就是PAGE_DIRECTION
PAGE_N_DIRECTION：假设连续插入新记录的方向都是一致，InnoDB会把沿着同一个方向插入记录的条数记下来，用PAGE_N_DIRECTION表示。如果最后一条记录的插入方向发生了改变，这个状态的值会被清零后重新统计

其他的暂时不讨论

FileHeader（文件头部） #

PageHeader专门针对的是数据页记录的各种状态信息，比如页有多少条记录，多少个槽。
FileHeader通用于各种类型的页，描述了一些通用于各种页的信息，比如这个页的编号是多少，它的上一个页和下一个页是谁，固定占用38字节

校验和（checksum)：对于很长的字节串，通过某种算法计算出比较短的值来代编这个字节串，比较之前先比较这个字节串。省去了直接比较这两个长字节串的时间损耗
InnoDB通过页号来唯一定位一个页

页号（第n个号），4字节，2^(4*8)=2^32次方位 =4294967296 个页
4294967296 * (16KB/页) =64T，这也是InnoDB 单表限制的大小

页有好几种类型，前面介绍的是存储记录的数据页，还有其他类型的页

存放记录的数据页的类型其实是FIL_PAGE_INDEX，也就是索引页
前面说记录的存储结构时，所说的溢出页是FIL_PAGE_TYPE_BLOB
对于FIL_PAGE_PREV和FIL_PAGE_NEXT：当占用空间非常大时，无法一次性为这么多数据分配一个非常大的存储空间，如果分散到多个不连续的页中存储，则需要把这些页关联起来。FIL_PAGE_PREV和FIL_PAGE_NEXT就分别代表本数据页的上一个页和下一个页的页号。不是所有类型的页都有上一个页和下一个页属性的，不过数据页（FIL_PAGE_INDEX的页）有这两个属性，所以存储记录的数据页其实可以组成一个双向链表

FileTrailer（文件尾部） #

InnoDB存储引擎会把数据存储倒磁盘，但磁盘速度太慢，需要以页为单位把数据加载到内存中处理
如果在该页中的数据在内存中修改了，在修改后某个时间还需要把数据刷新到磁盘中，但在刷新还没结束的时候断电了怎么办。为了检测一个页是否完整（判断刷新时有没有之刷新了一部分），为每个页尾部添加一个FileTriler部分，由8个字节组成，又分两小部分

• 前4 字节代表页的校验和。这个部分与File Header 中的校验和相对应。每当一个页面在内存中发生修改时，在刷新之前就要把页面的校验和算出来。因为File Header 在页面的前边，所以File Header 中的校验和会被首先刷新到磁盘，当完全写完后，校验和也会被写到页的尾部。如果页面刷新成功，则页首和页尾的校验和应该是一致的。如果刷新了一部分后断电了，那么File Header 中的校验和就代表着己经修改过的页，而File Trailer 中的校验和代表着原先的页（因为断电了，所以没有完全写完），二者不同则意味着刷新期间发生了错误.
• 后4 字节代表页面被最后修改时对应的LSN 的后4 字节，正常情况下应该与FileHeader 部分的FIL_PAGE_LSN的后4 字节相同。这个部分也是用于校验页的完整性，不过我们目前还没说LSN 是什么意思，所以大家可以先不用管这个属性。

这个File Trailer 与File Header 类似，都通用于所有类型的页