InnoDB数据(索引)页<一>普通的用户记录结构
InnoDB
是一个将表中的数据存储到磁盘上的存储引擎,所以即使关机后重启我们的数据还是存在的。而真正处理数据的过程是发生在内存中的,所以需要把磁盘中的数据加载到内存中,如果是处理写入或修改请求的话,还需要把内存中的内容刷新到磁盘上。
读写磁盘的速度非常慢,和内存读写差了几个数量级,所以当我们想从表中获取某些记录时,InnoDB
存储引擎需要一条一条的把记录从磁盘上读出来么?不,那样会慢死,InnoDB
采取的方式是:将数据划分为若干个页,以页作为磁盘和内存之间交互的基本单位,InnoDB中页的大小一般为 16 KB。也就是在一般情况下,一次最少从磁盘中读取16KB的内容到内存中,一次最少把内存中的16KB内容刷新到磁盘中。
InnoDB
为了不同的目的而设计了许多种不同类型的页
。常见的页类型有数据页(索引页)、Undo 页、系统页、事务数据页等。本文主要分析的是数据页。
下面是对于数据页结构的简单描述:
名称 | 中文名 | 占用空间大小 | 简单描述 |
---|---|---|---|
File Header | 文件头部 | 38 字节 | 页的一些通用信息 |
Page Header | 页面头部 | 56 字节 | 数据页专有的一些信息 |
Infimum + Supremum | 最小记录和最大记录 | 26 字节 | 两个虚拟的行记录 |
User Records | 用户记录 | 不确定 | 实际存储的行记录内容 |
Free Space | 空闲空间 | 不确定 | 页中尚未使用的空间 |
Page Directory | 页面目录 | 不确定 | 页中的某些记录的相对位置 |
File Trailer | 文件尾部 | 8 字节 | 校验页是否完整 |
一、File Header
File Header表示页的一些通用信息,占固定的38字节。由下面这些内容组成的:
名称 | 占用空间大小 | 描述 |
---|---|---|
FIL_PAGE_SPACE_OR_CHKSUM | 4 字节 | 页的校验和(checksum值) |
FIL_PAGE_OFFSET | 4 字节 | 页号 |
FIL_PAGE_PREV | 4 字节 | 上一个页的页号 |
FIL_PAGE_NEXT | 4 字节 | 下一个页的页号 |
FIL_PAGE_LSN | 8 字节 | 页面被最后修改时对应的日志序列位置(英文名是:Log Sequence Number) |
FIL_PAGE_TYPE | 2 字节 | 该页的类型 |
FIL_PAGE_FILE_FLUSH_LSN | 8 字节 | 仅在系统表空间的一个页中定义,代表文件至少被刷新到了对应的LSN值 |
FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID | 4 字节 | 该页属于哪个表空间 |
数据页的文件头部中记录了上一页和下一页的地址,证明叶子结点形成的是**双向链表
**。
1.1 FIL_PAGE_SPACE_OR_CHKSUM:校验和
用于保证页同步完整
。File Trailer的前四个字节是和File Header的FIL_PAGE_SPACE_OR_CHKSUM值对应,每当一个页修改了同步页到磁盘的时候,就会先同步File Header的FIL_PAGE_SPACE_OR_CHKSUM。最后才会同步File Trailer前四个字节的FIL_PAGE_SPACE_OR_CHKSUM。如果整个页同步正常,那么最后这两个的校验和将是一致的,反之则说明同步异常。
1.2 FIL_PAGE_TYPE
标识该存储页的类型。InnoDB其他类型的页,具体如下:
类型名称 | 十六进制 | 描述 |
---|---|---|
FIL_PAGE_TYPE_ALLOCATED | 0x0000 | 最新分配,还没使用 |
FIL_PAGE_UNDO_LOG | 0x0002 | Undo日志页 |
FIL_PAGE_INODE | 0x0003 | 段信息节点 |
FIL_PAGE_IBUF_FREE_LIST | 0x0004 | Insert Buffer空闲列表 |
FIL_PAGE_IBUF_BITMAP | 0x0005 | Insert Buffer位图 |
FIL_PAGE_TYPE_SYS | 0x0006 | 系统页 |
FIL_PAGE_TYPE_TRX_SYS | 0x0007 | 事务系统数据 |
FIL_PAGE_TYPE_FSP_HDR | 0x0008 | 表空间头部信息 |
FIL_PAGE_TYPE_XDES | 0x0009 | 扩展描述页 |
FIL_PAGE_TYPE_BLOB | 0x000A | BLOB页 |
FIL_PAGE_INDEX | 0x45BF | 索引页,也就是我们所说的数据页 |
二、Page Header
Page Header是用来记录数据页的状态信息的,由14个部分组成,共占56个字节 。由下面这些内容组成的:
名称 | 占用空间大小 | 描述 |
---|---|---|
PAGE_N_DIR_SLOTS | 2 字节 | 在页目录中的槽数量 |
PAGE_HEAP_TOP | 2 字节 | 还未使用的空间最小地址,也就是说从该地址之后就是Free Space |
PAGE_N_HEAP | 2 字节 | 本页中的记录的数量(包括最小和最大记录以及标记为删除的记录) |
PAGE_FREE | 2 字节 | 第一个已经标记为删除的记录地址(各个已删除的记录通过next_record 也会组成一个单链表,这个单链表中的记录可以被重新利用) |
PAGE_GARBAGE | 2 字节 | 已删除记录占用的字节数 |
PAGE_LAST_INSERT | 2 字节 | 最后插入记录的位置 |
PAGE_DIRECTION | 2 字节 | 记录插入的方向 |
PAGE_N_DIRECTION | 2 字节 | 一个方向连续插入的记录数量 |
PAGE_N_RECS | 2 字节 | 该页中记录的数量(不包括最小和最大记录以及被标记为删除的记录) |
PAGE_MAX_TRX_ID | 8 字节 | 修改当前页的最大事务ID,该值仅在二级索引中定义 |
PAGE_LEVEL | 2 字节 | 当前页在B+树中所处的层级 |
PAGE_INDEX_ID | 8 字节 | 索引ID,表示当前页属于哪个索引 |
PAGE_BTR_SEG_LEAF | 10 字节 | B+树叶子段的头部信息,仅在B+树的Root页定义 |
PAGE_BTR_SEG_TOP | 10 字节 | B+树非叶子段的头部信息,仅在B+树的Root页定义 |
三、Infimum + Supremum
Infimum和Supremum是InnoDB
定义的特殊行记录,没有变长字段长度列表和NULL值列表,分别为最小记录与最大记录。
注意:最小记录和最大记录的记录头会有默认值
- Infimum:
heap_no=0
record_type=2
- Supremum:
heap_no=1
record_type=3
3.1 Infimum
3.2 Supremum
四、User Records
存储行格式
的地方,行格式的记录头信息
名称 | 大小(单位:bit) | 描述 |
---|---|---|
预留位1 | 1 | 没有使用 |
预留位2 | 1 | 没有使用 |
delete_mask | 1 | 标记该记录是否被删除 |
min_rec_mask | 1 | B+树的每层非叶子节点中的最小记录都会添加该标记 |
n_owned | 4 | 表示当前记录拥有的记录数 |
heap_no | 13 | 表示当前记录在记录堆的位置信息 |
record_type | 3 | 表示当前记录的类型,0 表示普通记录,1 表示B+树非叶子节点记录,2 表示最小记录,3 表示最大记录 |
next_record | 16 | 表示下一条记录的相对位置 |
-
delete_mask
删除标记为1记录不会立即从磁盘上移除,是因为移除它们之后把其他的记录在磁盘上重新排列需要性能消耗,所以只是打一个删除标记而已,所有被删除掉的记录都会组成一个所谓的
垃圾链表
,在这个链表中的记录占用的空间称之为所谓的可重用空间
,之后如果有新记录插入到表中的话,可能把这些被删除的记录占用的存储空间覆盖
掉。 -
next_record(
单链表
)表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量。
比方说第一条记录的next_record
值为32
,意味着从第一条记录的真实数据的地址处向后找32
个字节便是下一条记录的真实数据。注意:
下一条记录
指得并不是按照我们插入顺序的下一条记录,而是按照主键值由小到大的顺序的下一条记录。而且规定 Infimum记录(也就是最小记录)的下一条记录就是本页中主键值最小的用户记录未被删除的记录
(delete_mask = 0)会按照主键从小到大的顺序形成了一个单链表
五、Free Space
自己存储的记录会按照我们指定的行格式
存储到User Records
部分。但是在一开始生成页的时候,其实并没有User Records
这个部分,每当我们插入一条记录,都会从Free Space
部分,也就是尚未使用的存储空间中申请一个记录大小的空间划分到User Records
部分,当Free Space
部分的空间全部被User Records
部分替代掉之后,也就意味着这个页使用完了,如果还有新的记录插入的话,就需要去申请新的页了,这个过程的图示如下:
六、Page Directory
InnoDB
为了快速定位记录制作了一个类似书目录一样的页目录
6.1 页目录的过程
- 将所有正常的记录(包括最大和最小记录,不包括标记为已删除的记录)划分为几个组。
- 每个组的最后一条记录(也就是组内最大的那条记录)的头信息中的
n_owned
属性表示该记录拥有多少条记录,也就是该组内共有几条记录。 - 将每个组的最后一条记录的地址偏移量单独提取出来按顺序存储到靠近
页
的尾部的地方,这个地方就是所谓的Page Directory
,也就是页目录
(此时应该返回头看看页面各个部分的图)。页面目录中的这些地址偏移量被称为槽
(英文名:Slot
),所以这个页面目录就是由槽
组成的。
注意:
对于最小记录所在的分组只能有 1 条记录,最大记录所在的分组拥有的记录条数只能在 1~8 条之间,剩下的分组中记录的条数范围只能在是 4~8 条之间。
6.2 分组过程
- 初始情况下一个数据页里只有最小记录和最大记录两条记录,它们分属于两个分组。
- 之后每插入一条记录,都会从
页目录
中找到主键值比本记录的主键值大并且差值最小的槽,然后把该槽对应的记录的n_owned
值加1,表示本组内又添加了一条记录,直到该组中的记录数等于8个。 - 在一个组中的记录数等于8个后再插入一条记录时,会将组中的记录拆分成两个组,一个组中4条记录,另一个5条记录。这个过程会在
页目录
中新增一个槽
来记录这个新增分组中最大的那条记录的偏移量。
6.3查询记录的过程
过程分为两步:
通过二分法确定该记录所在的槽,并找到该槽中主键值最小的那条记录。
通过记录的 next_record 属性遍历该槽所在的组中的各个记录。
因为各个槽代表的记录的主键值都是从小到大排序的,所以我们可以使用所谓的二分法
来进行快速查找。4个槽的编号分别是:0
、1
、2
、3
、4
,所以初始情况下最低的槽就是low=0
,最高的槽就是high=4
。比方说我们想找主键值为6
的记录,过程是这样的:
- 计算中间槽的位置:
(0+4)/2=2
,所以查看槽2
对应记录的主键值为8
,又因为8 > 6
,所以设置high=2
,low
保持不变。 - 重新计算中间槽的位置:
(0+2)/2=1
,所以查看槽1
对应的主键值为4
,又因为4 < 6
,所以设置low=1
,high
保持不变。 - 因为
high - low
的值为1,所以确定主键值为5
的记录在槽2
对应的组中。此刻我们需要找到槽2
中主键值最小的那条记录,然后沿着单向链表遍历槽2
中的记录。但是我们前面又说过,每个槽对应的记录都是该组中主键值最大的记录,这里槽2
对应的记录是主键值为8
的记录,怎么定位一个组中最小的记录呢?别忘了各个槽都是挨着的,我们可以很轻易的拿到槽1
对应的记录(主键值为4
),该条记录的下一条记录就是槽2
中主键值最小的记录,该记录的主键值为5
。所以我们可以从这条主键值为5
的记录出发,遍历槽2
中的各条记录,直到找到主键值为6
的那条记录即可。由于一个组中包含的记录条数只能是1~8条,所以遍历一个组中的记录的代价是很小的。
七、File Trailer
为了校验页是否完整,每个页的尾部都加了一个File Trailer
部分,这个部分由8
个字节组成,可以分成2个小部分:
-
前4个字节代表页的校验和
这个部分是和
File Header
中的校验和相对应的。每当一个页面在内存中修改了,在同步之前就要把它的校验和算出来,因为File Header
在页面的前面,所以校验和会被首先同步到磁盘,当完全写完时,校验和也会被写到页的尾部,如果完全同步成功,则页的首部和尾部的校验和应该是一致的。如果写了一半儿断电了,那么在File Header
中的校验和就代表着已经修改过的页,而在File Trialer
中的校验和代表着原先的页,二者不同则意味着同步中间出了错。 -
后4个字节代表页面被最后修改时对应的日志序列位置(LSN)
转载自:https://juejin.cn/post/7216914115260301367