0%

MySQL之InnoDB存储引擎:数据页

众所周知,MySQL的InnoDB存储引擎中内存与硬盘交互的基本单位是页。具体地,有数据页(又称为索引页)、Undo页、系统页、溢出页等类型。而所谓数据页,即是用来存放数据记录

abstract.png

概述

数据页包含以下七个部分。如下图所示,未标明所占空间大小的部分表示其所占空间不固定。其中Infimum、Supremum部分所占空间与该数据页所使用的raw format行格式有关(例如在compact行格式下,其占用 2x(5+8)=26 个字节)。其中对于File Header、File Trailer部分而言,是各类型页通用的部分

figure 1.jpeg

File Header

描述当前页通用的状态信息

Page Header

描述数据页特有的状态信息

Infimum、Supremum

InnoDB插入的两条虚拟记录——即Infimum最小记录、Supremum最大记录

User Records

存储用户插入的记录数据,即用户记录

Free Space

剩余空间

Page Directory

Page Directory页目录中包含若干个槽,每个槽中会存储某个数据记录在该页的地址偏移量

File Trailer

用于检验当前页的完整性

File Header 文件头

File Header文件头部,该部分固定使用38个字节。如前所述,该部分在各类型页中是通用的。故其只是用于描述当前页的一些基本状态信息,而不涉及数据页这一类型下的相关信息。下面对File Header中的各属性依次做相关解释、说明

  • FIL_PAGE_SPACE_OR_CHKSUM

当前页面的校验和(Checksum),其占用4个字节

  • FIL_PAGE_OFFSET

当前页的页号,其占用4个字节。InnoDB存储引擎通过页号即可找到该页面。具体地,页号从0开始编号,将页号乘上数据页的大小(对于非压缩的页,MySQL中默认大小为16KB)即可得到该页的地址偏移量

  • FIL_PAGE_PREV

前一个数据页的页号,其占用4个字节

  • FIL_PAGE_NEXT

后一个数据页的页号,其占用4个字节。可以看到通过FIL_PAGE_PREV、FIL_PAGE_NEXT属性,各数据页之间实际上形成了一个双向链表。值得一提的是,并不是所有类型的页都使用FIL_PAGE_PREV、FIL_PAGE_NEXT这两个属性。主要是数据页类型(FIL_PAGE_INDEX)的页使用该字段

  • FIL_PAGE_LSN

当前页最后一次修改时对应的日志序列位置(Log Sequence Number),其占用8个字节

  • FIL_PAGE_TYPE

当前页的类型,其占用2个字节。常见的有

  1. 0x0002: FIL_PAGE_UNDO_LOG(Undo日志页)
  2. 0x0003: FIL_PAGE_INODE(段信息节点)
  3. 0x0004: FIL_PAGE_IBUF_FREE_LIST(Insert Buffer空闲列表)
  4. 0x0005: FIL_PAGE_IBUF_BITMAP(Insert Buffer位图)
  5. 0x0006: FIL_PAGE_TYPE_SYS(系统页)
  6. 0x0007: FIL_PAGE_TYPE_TRX_SYS(事务系统页)
  7. 0x0008: FIL_PAGE_TYPE_FSP_HDR(表空间头部信息)
  8. 0x0009: FIL_PAGE_TYPE_XDES(拓展描述页)
  9. 0x000A: FIL_PAGE_TYPE_BLOB(溢出页)
  10. 0x45BF: FIL_PAGE_INDEX(索引页,即数据页)
  • FIL_PAGE_FILE_FLUSH_LSN

仅在系统表空间的一个页中定义,代表文件至少被刷新到了对应的LSN值,其占用8个字节

  • FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID

当前页所属的表空间,其占用4个字节

Page Header 页面头

前面我们介绍了描述页通用信息的File Header部分,这里我们来看看Page Header部分,其描述的就是数据页类型的状态信息。下面对Page Header中的各属性依次做具体解释、说明

  • PAGE_N_DIR_SLOTS

描述Page Directory页目录中槽的数量,其占用2个字节。对于一个刚刚新建的空数据页而言,其初值为2即有2个槽,分别指向Infimum最小记录、Supremum最大记录

  • PAGE_HEAP_TOP

Free Space剩余空间的起始地址,其占用2个字节

  • PAGE_N_HEAP

该数据页中的所有记录数量(含Infimum最小记录、Supremum最大记录、被删除的记录),其占用2个字节

  • PAGE_FREE

已被删除的记录的链表(即所谓的垃圾链表)的地址,其占用2个字节

  • PAGE_GARBAGE

已被删除的记录所占用的总字节数,其占用2个字节。该部分空间可被重用

  • PAGE_LAST_INSERT

最后一次记录插入的位置,其占用2个字节

  • PAGE_DIRECTION

最后一次记录插入的方向,其占用2个字节。具体地,若本次插入的记录的主键值比上次插入记录的主键值大,则记录插入的方向是右边;反之为左边

  • PAGE_N_DIRECTION

相同方向连续插入的记录数量,其占用2个字节。若本次记录插入的方向与之前的方向相反,则该值将被清零并重新计数

  • PAGE_N_RECS

该数据页中的有效记录的数量(不含Infimum最小记录、Supremum最大记录、被删除的记录),其占用2个字节

  • PAGE_MAX_TRX_ID

修改当前页的最大事务ID,该值仅在二级索引中定义。其占用8个字节

  • PAGE_LEVEL

当前页在B+树中所处的层级,其占用2个字节

  • PAGE_INDEX_ID

索引ID,表示当前页属于哪个索引,其占用8个字节

  • PAGE_BTR_SEG_LEAF

B+树叶子段的头部信息,仅在B+树的Root页定义,其占用10个字节

  • PAGE_BTR_SEG_TOP

B+树非叶子段的头部信息,仅在B+树的Root页定义,其占用10个字节

Infimum、Supremum 最小、最大记录

所谓Infimum、Supremum部分,其实很简单。其是InnoDB存储引擎自动向数据页插入的两条记录——Infimum最小记录、Supremum最大记录。由于这两条记录不是用户插入添加的,故通常其又被称作为伪记录(虚拟记录)

对于Infimum最小记录而言,其记录的数据内容部分固定为0x69 0x6E 0x66 0x69 0x6D 0x75 0x6D 0x00;类似地,对于Supremum最大记录而言,其记录的数据内容部分固定为0x73 0x75 0x70 0x72 0x65 0x6D 0x75 0x6D。聪明的朋友可能已经看出来了。实际上,上述两条伪记录的数据内容就是其记录名称(infimum、supremum)的ascii码值

而Infimum最小记录、Supremum最大记录的记录头部分则取决于该数据页所使用的raw format行格式

User Records 用户记录

该部分不言而喻相信大家都很清楚其作用,即是用来存储用户插入的数据记录的。这里我们以compact行格式的数据记录为例来展开介绍下

next_record字段

如我们之前所说的,在compact行格式下记录头信息的next_record字段指的是下一条记录的相对位置(地址偏移量)。但需要注意的是,其并不是指向下一条记录的起始部分,而是指向下一条记录的数据内容的起始部分。示意图如下所示

figure 2.jpeg

这其实也解释了为什么记录的额外信息部分(变长字段的长度列表、NULL值标志位)是按照列的顺序逆序排列的。因为此时数据内容部分中位置靠前的字段与其所对应的长度信息的相对距离更近。根据局部性原理可知,此举将可能会提高CPU高速缓存的命中率

比较记录的大小

聪明的朋友可能已经看出来了,User Records里的记录数据通过next_record字段本质上构成了一个单向链表。那么问题来了?这个链表的顺序是按照记录插入的顺序么?答案:不是。实际上对于记录来说,相互之间也是可以比较大小的。具体地,对于一条完整的记录而言,比较记录的大小就是比较主键的大小

例如我们依次顺序地插入记录1、记录2、记录3,其三条记录的主键依次为14、47、35。从下图可以看出,各记录next_record字段指向的是下一个比它大的记录,而非所谓的记录插入顺序。当其中记录发生变化(新增、删除、修改)时,该链表也会适时调整,以满足链表按记录从小到大的排序规则

figure 3.jpeg

特别的,针对这个记录链表而言无论其怎么变化,其表头、表尾永远是固定不变的,分别是Infimum最小记录、Supremum最大记录,这也是此两条伪记录的命名来源。可以看出这两条记录相当于是记录链表的哨兵节点

heap_no字段

该字段表示的是记录在本页中的位置。由于Infimum最小记录、Supremum最大记录在用户插入的记录的前面,故分别为0、1。故对于用户记录而言,该值从2开始。同样以上图为例,记录1、记录2、记录3中该字段的值则分别为2、3、4

delete_mask字段

该字段为记录删除的标志位。当我们删除某记录时,不是直接从硬盘中删除,而是分为两个阶段

  1. delete mark阶段:将记录的该字段置为1
  2. purge阶段:将该记录加入所谓的垃圾链表

对于垃圾链表中记录所占用的空间即为所谓的可重用空间。这样下次当有新的记录添加进来时,即可通过覆盖的方式来复用这部分存储空间。当然,所谓的垃圾链表也是通过被删除记录的next_record字段作为指针来链接形成的

Free Space 剩余空间

该部分即为页面的剩余空间。具体地,User Records部分从上往下使用剩余空间,而Page Directory则从下往上使用剩余空间。示意图如下所示

figure 4.jpeg

Page Directory 页目录

前面我们说到数据页中的各记录实际上相当于一个单向链表,其中,最小记录、最大记录分别为表头、表尾。而链表的查找效率非常低,每次都需从表头开始进行遍历。为了提高查找效率,Page Directory页目录应运而生。首先将整个链表分为若干个部分(即分组),然后将分组内最后一条记录(即组内最大的记录)的地址(即其在数据页中的地址偏移量)存放在一个Slot槽中,各Slot槽根据其所指向的记录按从大到小的顺序在页目录中排列。示意图如下所示。这里为了简便,各分组内的记录没有全部画出来,而是只是在图中左侧指明该分组中记录的数量。其实关于分组中记录的数量是存储在该分组对应的Slot槽所指向的记录(即分组内最后一条记录,当然该记录也是分组内最大的记录)的n_owned字段

figure 5.png

这样我们在该页下如果需要根据主键来查找某条记录时,即可先利用Page Directory页目录中的各Slot槽,通过二分查找快速确定该记录所在的分组,然后再按链表进行遍历。可以看到通过页目录大大缩小了链表遍历查找记录时的范围,提高了效率。这也是该部分为啥被称之为目录的缘由

具体地关于如何分组,基本步骤如下

  1. 数据页初始化后,数据页里只有最小记录、最大记录两条记录,它们分别属于两个分组
  2. 当插入一条新记录到页中后,其所在槽的确定方法是,从Slot 0槽(该槽所指向记录显然是各槽所指向的记录中最小的)开始进行遍历,直至找到第一个 槽所指向的记录比该新记录大 的槽。随后将该槽所指向的记录的n_owned字段值加1,即该分组中多了一条记录
  3. 为了避免某个分组内记录数量过多(因为这样会导致,在该分组内的查找遍历范围较大),当分组内的记录数达到8时,此时如果再向其中插入一条记录,会导致此分组拆分为两个组,一个分组内4条记录,另一个分组内5条记录。当然增加了一个新分组,页目录中的槽数据也需要适时调整、维护,以保证页目录的有序、准确

前面我们提到,为了切实保证基于页目录的二分查找能够真正达到缩小链表遍历范围这一目的。我们需要对各分组下的记录数量做限制,而在InnoDB引擎中,具体规定如下

  1. 最小记录所在的分组只能有1条记录,即只有它自己
  2. 最大记录所在的分组的记录数量只能在1~8条记录之间
  3. 其他分组的记录数量只能在是4~8条记录之间

File Trailer 文件尾

该部分与File Header文件头一样,为各类型页所通用。其目的用于检验当前页的完整性。具体地其占用8个字节,前4个字节为校验和(checksum),后4个字节为页面被最后修改时相应的日志序列位置(LSN)

这里就基于校验和的完整性校验原理简单的介绍下。其实也很简单。在页从内存同步回硬盘之前,先计算好校验和(checksum),并赋给页的File Header文件头、File Trailer文件尾的校验和字段。在页从内存同步回硬盘后,如果该页从头到尾都被成功正确写入磁盘的话,则硬盘上该页的File Header文件头、File Trailer文件尾的两个校验和数据应该是一致的;反之,如果发现硬盘中该页的File Header文件头、File Trailer文件尾的两个校验和数据是不同的,则说明该页同步过程中发生了意外(比如断电)造成页只同步一部分到硬盘中了

请我喝杯咖啡捏~

欢迎关注我的微信公众号:青灯抽丝