亲宝软件园·资讯

展开

MySQL索引页结构

程序员小潘 人气:0

1. 前言

「页」是InnoDB管理存储空间的基本单位,也是内存和磁盘交互的基本单位。也就是说,哪怕你需要1字节的数据,InnoDB也会读取整个页的数据,下次读取的数据如果恰巧也在这个页里,就能命中缓存了。写也是一样的,写数据前要先把页加载到内存,然后在内存中修改,该页被记为「脏页」,脏页淘汰之前必须刷盘。

InnoDB有很多类型的页,它们的用处也各不相同。比如:有存放undo日志的页、有存放INODE信息的页、有存放Change Buffer信息的页、存放用户记录数据的页等等。今天我们要聊的,就是最基础也是最重要的,存放用户记录数据的「索引页」。

2. 索引页结构

InnoDB默认的页大小是16KB,在初始化表空间之前可以在配置文件中进行配置,一旦初始化完成就不可再变更了。查看页大小的命令如下,显示的是字节数。

SHOW VARIABLES LIKE 'innodb_page_size';

索引页结构如下图所示:

image.png

索引页由七部分组成,其中Infimum和Supremum也属于记录,只不过是虚拟记录,这里为了与用户记录区分开,还是决定将两者拆开。

名称大小描述
File Header38字节所有页的通用文件头信息
Page Header56字节索引页特有的页头信息
Infimum+Supremum26字节页中虚拟的最小、最大记录
User Records变长用户记录数据
Free Space变长空闲空间
Page Directory变长页目录,加速页内数据检索效率
File Trailer8字节所有页的通用文件尾信息,校验页是否完整

2.1 File Header

File Header是所有页都有的一个通用的结构,占用固定的38字节,它记录了页的一些通用的状态信息,例如:页的页号、Checksum、把页串联成双向链表的指针、页的类型等等。

名称大小描述
FIL_PAGE_SPACE_OR_CHECKSUM4字节新版本中代表页的校验和Checksum
FIL_PAGE_OFFSET4字节页号
FIL_PAGE_PREV4字节上一个页的页号
FIL_PAGE_NEXT4字节下一个页的页号
FIL_PAGE_LSN8字节页面最后被修改时的LSN值
FIL_PAGE_TYPE2字节页的类型
FIL_PAGE_FILE_FLUSH_LSN8字节仅在系统表空间的第1个页中使用,代表文件至少被刷新到了对应的LSN值
FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID4字节页数据哪个表空间

FIL_PAGE_SPACE_OR_CHECKSUM

基于当前页计算出的校验和(Checksum),可以把它看作是哈希值,校验和不同,则两个页数据肯定不同。它的作用是InnoDB在脏页刷盘时,有可能会遇到页刷到一半断电的情况,页的头和尾部分分别记录校验和,只有当头尾的校验和一致的时候,才代表磁盘上的页是完整的,否则就是一个损坏的页。

FIL_PAGE_OFFSET

页号,页的唯一标识,全局递增的数字,InnoDB通过页号来定位唯一的一个页。4字节存储,意味着一个表空间最多可以有232个页,按照一个页16KB计算,则一个表空间最多支持64TB的数据。

FIL_PAGE_PREV & FIL_PAGE_NEXT

一个页大小才16KB,一张表数据其实是由N多个页构成的,页与页之间在物理上可以是不连续的,但是逻辑上要连续,FIL_PAGE_PREV和FIL_PAGE_NEXT分别指向当前页的上一个页和下一个页的页号,通过这两个指针将索引页串联成了一个双向链表。记录与记录之间是单向的,页与页之间是双向的!

FIL_PAGE_LSN

页面最后被修改时,对应的LSN值。LSN的全称是Log Sequence Number,日志序列号。它是一个递增的数字,和事务相关,这里不作赘述。

FIL_PAGE_TYPE

当前页的类型,InnoDB为了不同的目的设计了很多不同类型的页,索引页的固定值是0x45BF

FIL_PAGE_FILE_FLUSH_LSN

仅在第1个页中使用,用来判断数据库是正常关闭还是异常宕机。

FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID

仅记录当前页数据哪个表空间。

2.2 Page Header

Page Header是索引页特有的结构,占用固定的56字节,它记录了索引页中记录相关的状态信息。

名称大小描述
PAGE_N_DlR_SLOTS2字节页目录中的槽数量
PAGE_HEAP_TOP2字节未使用的空间最小地址,User Records和Free Space分界点
PAGE_N_HEAP2字节本页中的记录的数量(包括虚拟记录和删除记录)
PAGE_FREE2字节第一个删除的记录地址,后续删除的记录会形成链表。
PAGE_GARBAGE2字节已删除记录占用的字节数
PAGE_LAST_INSERT2字节最后插入记录的位置
PAGE_DIRECTION2字节记录插入的方向
PAGE_N_DIRECTION2字节同一个方向连续插入的记录数量
PAGE_N_RECS2字节该页中记录的数量(不包括虚拟记录和删除记录)
PAGE_MAX_TRX_ID8字节修改当前页的最大事务ID,仅在二级索引中使用
PAGE_LEVEL2字节当前页在B+树中所处的层级
PAGE_INDEX_ID8字节索引ID,表示当前页属于哪个索引
PAGE_BTR_SEG_LEAF10字节B+树叶子段的头部信息,仅在B+树的Root页定义
PAGE_BTR_SEG_TOP10字节B+树非叶子段的头部信息,仅在B+树的Root页定义

不用每个属性都了解,我们挑几个比较重要的看看。

PAGE_N_DlR_SLOTS

一个页内可能有上千条记录,挨个遍历的话效率太慢了。为了提高页内记录的检索效率,InnoDB将页内的记录划分为多个组,组里最大的那条记录相较于页的地址偏移量会记录到「Page Directory」部分,每个组都对应一个槽,槽的大小是固定的2字节。该属性记录的就是页内槽的数量。

PAGE_HEAP_TOP

Free Space的起始位置,它是User Records和Free Space分界点。一个全新的页一开始是没有User Records部分的,每插入一条记录,都要向Free Space申请空间,Free Space耗尽就代表页满了。

PAGE_FREE

DELETE命令删除记录时,InnoDB并不会真的将记录从磁盘中删除,而是在记录的头信息里打个标记,然后将其加入到「垃圾链表」中。PAGE_FREE指向的就是垃圾链表的表头记录。后面删除的记录,也会自动加入到链表里。

PAGE_DIRECTION & PAGE_N_DIRECTION

PAGE_DIRECTION表示最后一条记录插入的方向,比上一条记录值大则记为右边,反之则是左边。PAGE_N_DIRECTION表示同一方向连续插入的记录数,方向变了该值就会重置。

PAGE_LEVEL

InnoDB组织数据的形式就是B+树,树中的节点就是索引页,PAGE_LEVEL代表当前页在B+树中所处的层级。InnoDB规定,叶子节点层级为0,然后向上递增。

2.3 User Records

Infimum和Supremum也属于记录,只是为了与用户记录区分开才划分成了两部分,我们先看User Records。

用户记录存放在User Records部分,一个全新的页一开始全是Free Space,是没有User Records部分的。每插入一条记录都需要到Free Space申请一块空间,并将其划分到User Records用来存放用户记录。当Free Space耗尽也就代表当前页已经用完了,再有新记录需要插入,就需要申请一个新的页了。

image.png

还记得MySQL的行格式吗?它决定了记录在磁盘里的存储格式。以COMPACT为例,存储格式如下图:

image.png

记录头信息里的字段比较关键,以防大家忘记,我这里再贴一下:

名称大小(Bit)说明
预留位11没有使用
预留位21没有使用
deleted_flag1记录删除标记
min_rec_flag1B+树非叶子节点的最小目录项标记
n_owned4同一页内同一组里最大的记录会记录组里的记录数量,其余记录该值为0
heap_no13当前记录在页面堆里的相对位置
record_type3记录类型。0:普通记录,1:B+树非叶子节点目录项记录,2:Infimum记录,3:Supremum记录.
next_record16下一条记录的相对位置

记录头信息的最后2字节用来连接下一条记录,将页内所有记录串联成一个单向链表。所以我们隐藏变长字段长度列表和NULL值列表,记录的格式应该是这样的:

image.png

记录是怎么排序的?
我们已经知道,页内的记录会自动串联成一个单向链表。那这个链表的编排顺序是什么呢?是按照记录的插入时间排序的吗?其实不是的,如果表有主键,会根据主键排序;没主键有唯一非空索引,会根据该索引排序;两者都没有,InnoDB会自动生成一个row_id列并根据该列进行排序。

若无特殊说明,本文均假定表有主键。

2.4 Infimum & Supremum

Infimum和Supremum是索引页内的两条虚拟记录,InnoDB规定所有索引页都会有这两条记录,而且所有的用户记录都比Infimum大,都比Supremum小。
记录头信息里的heap_no代表记录在堆里的相对位置,该值越小代表记录越靠前。细心的同学会发现,上图中的用户记录heap_no值是从2开始的,那0和1呢?不说你也肯定猜到了,就是被Infimum和Supremum占用了。Infimum和Supremum的heap_no值分别是0和1,它俩在所有用户记录的最前面。

Infimum和Supremum结构非常的简单,和用户记录一样也有头信息,真实数据部分是固定的字符串,如下图所示:

image.png

我们把这两条虚拟记录也加入到记录里面,完整的结构就是下面这样的:

image.png

Supremum记录的next_record属性为0,代表它已经没有下一条记录了。

2.5 Page Directory

Free Space没什么好说的,就是一块未被使用的空闲空间。

Page Directory也叫作「页目录」,它的目的是提高页内记录的检索效率。相较于一张表几千万的记录来说,一个页内几百上千条记录已经是很少很少了。可即便如此,它也有几百上千条啊,如果页内检索记录只能挨个遍历的话,那也太低效了。别忘了,页内的记录是根据索引值排好序的,我们可以巧用「二分法」来快速查找。

具体做法是:将页内所有非删除的记录划分为N个组,每个组里最后一条记录(即主键最大的记录)称作“大哥”,其余记录是“小弟”,“大哥”的n_owned属性记录了组内的记录数量。将“大哥”在页内的地址偏移量提取出来,按顺序依次从File Trailer部分往前写,每个地址偏移量占用2字节,称作一个「槽」,Page Directory就是由这些槽构成的。
InnoDB对于分组内的记录数量有一些规定:

由此可见,一个组里最多有8条记录,只要通过二分法快速定位到组,InnoDB也只需要遍历这8条记录,相较于遍历页内所有记录,效率要高的多。

image.png

2.6 File Trailer

File Trailer是所有页都有的通用结构,占用固定的8字节,它的主要作用就是为了校验页的完整性。磁盘的速度实在是太慢了,InnoDB不会每次写点数据都直接刷新到磁盘上,那样MySQL会慢死。而是将页作为刷盘的基本单位,数据修改时,先改内存里的页,稍后再将整个页的数据一次性刷新到磁盘里。但是这会带来一个问题,一个页16KB,刷到第10KB的时候磁盘断电了怎么办?重启后InnoDB如何判断磁盘里的页数据是完整的?

InnoDB是这么处理的,刷盘前根据页数据计算出一个Checksum,在页头和页尾都写一份。页刷盘的时候,先刷页头再刷页尾,当头尾两个Checksum值一致的时候,代表磁盘里的页是完整的,否则就表示页头刷了页尾没刷,那肯定是刷到一半出错了。

大小说明
4字节页的校验和Checksum
4字节页最后被修改时对应的LSN的后4个字节,正常情况下应该与File Header里的FIL_PAGE_LSN的后4个字节相同。

3. 总结

页是InnoDB存取数据的基本单位,默认页大小是16KB,InnoDB为了不同的目的设计了很多不同类型的页,本文重点分析了存放用户记录的索引页。页的头尾部分File Header和File Trailer是所有页都有的一个通用结构,它们记录了页的一些通用状态信息,和Checksum用来验证页的完整性。Page Header是索引页特有的结构,它记录了页内用户记录相关的状态信息。User Records部分用来存放用户记录。另外,由于页内的记录数量也不少,为了提高页内记录的检索效率,InnoDB在索引页中加入了Page Directory,它通过将记录分组,将组里最大的记录的地址偏移量形成一个个槽,Page Directory就是由这些槽构成的。检索数据时,使用二分法快速定位到槽所在的组,就可以避免遍历所有组的记录了。

加载全部内容

相关教程
猜你喜欢
用户评论