更多优质内容
请关注公众号

Mysql怎么运行的系列(三)InnoDB存储结构之行结构和页结构-张柏沛IT博客

正文内容

Mysql怎么运行的系列(三)InnoDB存储结构之行结构和页结构

栏目:数据库 系列:mysql怎么运行的 发布时间:2022-05-02 16:09 浏览量:672

下图所示是一个ibd文件的逻辑结构。

 

· Tablespace

表空间,用于存储存储一个或多个ibd数据文件(记录和索引),一个ibd文件包含多个段(segment)。

每个表空间都具有一个唯一的表空间id。

Mysql 5.6版本默认所有InnoDB的所有表数据会放在一个系统表空间 ibdata1。

5.7版本之后,每个表的数据默认单独放到一个独立表空间内。但每张表的独立表空间只存放数据页、索引页和写缓冲BitMap页,其他信息如回滚页、插入缓冲索引页、二次写缓冲仍放在系统表空间。所以即使每个表的数据单独放到自己的独立表空间,系统表空间也会不断增大。

 

· Segment

段,用于管理多个区(Extent),根据段类型可以分为数据段(Leaf node segment)、索引段(Non-leaf node segment)和回滚段(Rollback segment)等。

数据段包含B+树的叶子节点页、索引段包含B+树的非叶子节点页,一个表至少会有1个数据段和1个索引段。每多创建一个索引,会多两个segment(即数据段和索引段)。

段申请空闲内存空间时会按一个区申请(1 extend = 64 pages,1extend大小为1M)。但是innodb的一个表初始大小为96K,而不是1M,因为每个段一开始不会直接申请一个区,而是先用若干个碎片页存放数据,用完这些也才按1个区64个连续页来申请。

 

· Extent

区,一个区固定包含64个连续的页,大小为1M。当表文件空间不足,不会一页页的分配,而是直接分配一个区大小的空闲空间给ibd文件。

 

· Page

页,用于存储多个行记录(Row),一页大小为16K。

页类型有多种,如数据页、索引页、undo页、系统页、事务数据页、大的BLOB对象页等。

我们最常提及的数据页是指B+树的叶子节点页,索引页是指B+树非叶子节点页。

 

· Row

行,包含记录的字段值、事务ID(trx id)、滚动指针(roll pointer)、字段指针(field pointer)、行ID(row id)等信息。

 

 

 

 

InnoDB的行格式

表的行格式决定了它的行是如何物理存储的,这会反过来影响查询和DML的性能。如果单个page页能容纳更多行,查询可以更快,缓冲区能容纳的行越多,写入更新时所需的IO更少。

 

常见的行格式有四种:

redundant、compact、dynamic 和 compressed。

 

 

· compact行格式

 

 

a. 变长字段长度列表

它存储一条记录中所有变长字段(varchar、varbinary、text、blob类型)的长度,并且是逆序存放。

例如某一行记录,有c1/c2/c3这3个varchar(10)的字段,内容分别是 aaaa/bbb/d,那么变长字段长度列表为 01 03 04。变长字段长度列表中的每个长度可以用1字节(当变长字段值的长度小于255字节)或2字节(当变长字段值的长度大于255字节)表示。

 

b. NULL标志位

一条记录中的某些列的值是 NULL,row不会真的存储这些null(意思是null不占空间),而是用“NULL标志位” 把值为 NULL 的列统一管理。

系统会统计表中允许存储 NULL 的列有哪些,将每个允许 存储 NULL 的列对应一个 二进制位,二进制位按照列的顺序逆序排列,位为1表示某列的值是null,0表示不为null。

NULL标志位占用的位个数会补足到满足整数字节。

 

c. row 记录头信息

固定占5字节。其中比较重要的几个信息如下:

deleted_flag 

标记该记录是否被删除;

 

n_owned(重要) 

一个页的所有记录会被分为多个组,每个组有一个记录是“带头大哥”,其余的记录都是"小弟",“带头大哥"记录的 n_owned 代表该 组的记录条数,"小弟"记录的 n_owned 值都为0;

 

heap_no

表示当前记录在页面堆中的相对位置(用来表示该记录是本页的第几个记录)。之所以说是堆,是因为一个页中的记录与记录之间是紧密排列的。

 

next_record

下一条记录的相对位置(本记录指向下一条记录的链表指针,它是一个相对偏移量)。

 

record_type

本记录的类型,0 是普通记录也就是页的user record区中的记录、 1是B+树非叶子节点的目录项记录、2是infimum记录、3是supremum记录。

 

min_rec_flag

表示该记录是不是B+树非叶子节点中的最小的目录项记录。

 

 

e. 隐藏列

每个记录还有一些隐藏列。


row_id:行id,当用户没有自己设置主键或唯一键的时候,系统会自动生成一个 6 字节的唯一行ID作为主键;如果用户设置了主键,则row_id就不会存在;

trx_id:事务ID;

roll_pointer:回滚指针;


 

 

 

· redundant行格式

字段长度偏移列表

记录所有字段值(包括隐藏字段)的偏移量(而不是长度,但长度可以根据偏移量计算长度),逆序存放。

例如 有7个字段,分别占 6 6 7 4 3 10 1个字节,那么它们的偏移量列表是 25 24 1A 17 13 0C 06。

 

其他信息和 compact 格式类似,不再赘述。

 

 

· 溢出页

我们知道B+树的一个页包括多个行,如果一个行的某些字段过长(如很长的varchar、char 或者 text类型),InnoDB就会单独分配独立于B+树之外的页面来存储这个字段的信息,这样的页被称为溢出页,它既不是数据页也不是索引页。这样的字段被称为页外列。

 

溢出页之所以叫溢出页是因为它不再B+树上,由B+树的行保存溢出页的指针。这样的好处是让B+树的一个节点能容纳更多页,减小树的高度。

 

B+树上的页是类型为 B-tree node 的页,而溢出页是页类型为 Uncompress BLOB 的页。对于一个长度为48000字节的varchar字段需要3个溢出页来存储。

 

对于 redundant 和 compact 作为行格式的表,如果某个列值的内容很多,会将该列值的前768字节存在B+树节点的页中,其余的部分存在溢出页。

溢出页的地址用20字节表示。对于大于786字节的固定长度的字段(text 或者 很长的char类型),Innodb会转为变长字段以便在页外存储。

 

 

 

· dynamic 和 compressed 行格式

dynamic和compressed这两种行格式和 compact是相同的,只不过在溢出页的处理上不同:这两种行格式会将内容很多的列值完全存到溢出页,而记录只包含指向溢出页的20字节指针。

 

compressd和dynamic具有相同的存储特性,而且增加了对数据的压缩支持。

 

mysql 5.7版本默认使用 dynamic 行格式。

REDUNDANT 是一种非紧凑的行格式,而 COMPACT、DYNAMIC 以及 COMPRESSED 行格式是紧凑的行格式,占用的存储空间更少。

 

 

 

 

InnoDB的页结构

InnoDB的数据页 和 索引页 结构如下(注意,其他类型的页不是这样的结构):

 

 

· 用户记录 和 User Records 堆

在页的 7 个组成部分中,用户存储的记录会按照指定的行格式存储到 User Records 部分。

一开始生成页的时候,User Records 部分为空,每当插入一条记录时都会从 Free Space 部分(也就是尚未使用的存储空间〉申请一个记录大小的空间,并将这个空间划分到User Records 部分。

当 Free Space 部分的空间全部被 User Records 部分用完之后,如果还有新的记录插入,就需要去申请新的页 。这些用户插入的记录是用户记录。

 

 

· 用户记录的物理结构——堆

数据页 User Records 部分里的记录一条条紧密地排列着。因此User records区的数据结构是一个堆。堆里面的每一条记录在堆中的相对位置被记录在行头信息的 heap_no 中。

 

 

· Infimum 和 Supremum记录

heap_no为0和1的记录不是用户插入的记录,而是页中本来就存在的两条虚拟记录(Infimum 和 Supremum记录),这两条记录是堆里面最靠前的记录。

innodb规定lnfimum 记录是一个页中最小的记录(逻辑上最小), Supremum 记录是一个页中最大的记录(逻辑上最大),任何用户记录都比Infimum 记录大 ,比 Supremum记录小,Infimum 和 Supremum记录是没有主键值的。

 

Infimum 和 Supremum记录的长度是固定的,包括5字节的记录头信息和8字节的一个固定单词组成。而用户记录长度是不固定的。

 

 

· 软删除

页内的一条记录被删除时不会从磁盘移除,因为记录在页中时紧密排列的,如果真的删除中间的某条记录,那么后面的记录就要批量往前移动,这和删除数组中间的某个元素是一样的道理。

行的头信息有一个 delete_flag 位标识记录是否已删除。当要删除一个记录时,会做2件事情:将该记录的 deleted_flag置为1;每个页会维护一个垃圾链表,删除一个行时会将软删除的行链入垃圾链表。

所有被软删除的行所占的空间是可重用空间,之后有新记录插入该页就可以覆盖掉被删除的记录所占的空间。

 

 

· 用户记录的逻辑结构——单向链表

在物理上,页内的每条记录是紧密排列的,而且是无序的,一个新插入的记录在物理上可能位于旧记录的前面或者后面(位于前面是因为新记录重用了被删除记录的空间)。

在逻辑上,页内的所有记录按照主键从小到大的顺序形成一个单向链表,每个记录通过一个 next_record 作为单向指针指向下一个记录。

next_record 是记录的头信息的一个 2字节的具有正负号的相对偏移量,而且 next_record指向的是下一条记录真实数据开始的地方。

不指向记录开头而指向数据开头,这是因为该位置向左就记录头信息,向右就是数据,变长字段长度列表和NULL列表中的信息都是逆序存放的, 这样可以使记录中位置靠前的字段和它对应的字段长度信息在内存中的距离更近,可能会提高CPU高速缓存的命中率,两条指令所用到的内存地址都在高速缓存L1中。

Supremum记录(next_record)是单向链表的最后一个节点,Infimum记录则是第一个节点。

 

 

· 页目录 Page Directory

页目录的设计是为了实现在页内高效查找某个行。页目录的构建过程如下:

1、页内的所有未被删除的记录(包括Infimum 和 Supremum)按照索引顺序被划分位几个组,组内的记录也是按索引值升序排的。

每个组的最大的记录是“组长”,组内的其他记录是“组员”,组长头信息的 n_owned 属性表示组内有多少记录。

2、将每个组的组长的页内地址(即组长的真实数据开始位置与页中第0个字节的距离)提取出来,按顺序存储到靠近页尾部空间的页目录。页目录在逻辑上就是一个有序数组,数组中的元素称为槽(Slot)。每个槽占2字节。

 

如下所示

 

页目录的每一个槽本质上就指向每个分组(的组长)的指针,如下图所示,这是一个有16个用户记录的页,被分为5组:

分组规则如下:

1、初始情况,页只有两个分组(分别是lnfinmum 记录和 supremum 记录),页目录只有两个槽,分别代表 lnfinmum 记录和 supremum 记录在页 面中的地址偏移量。

Innodb规定 lnfinmum 所在分组只能有1条记录, Supremum 记录所在的分组的记录条数只能在1~8条之间,其余组的记录数 只能在 4~8 条之间。

2、之后每插入一条记录 都会从页目录中找到主键值比待插入记录的主键值大 并且差值最小的槽(用二分查找)。这个槽对应的组长的n_owned值加1。

3、当一个组中的记录数等于 8,再插入一条记录会将组中的记录拆分成两个组,其 中一个组 4 条记录,另一个组 5 条记录。页目录会新增一个槽。

插入的记录在物理上紧接着记录堆末尾(或堆中间某个可重用空间)放入,在逻辑上只需调整对应指针是记录链入链表中即可,复杂度为O(1)。页目录新增槽的复杂度为O(n),但页目录的元素不多可以忽略不记。

 

页内查找的过程如下(嫌我啰嗦的小伙伴们可以跳过)

例如想从上面16条记录中找 id = 6的记录,上图共有 5 个槽,用二分查找需要 low,high = 0, 4 两个指针从数组两边开始:

1、计算中间槽的位置。(0 + 4) / 2=2。查看槽 2 对应记录的主键值为 8,又因为 8> 6. 所以

设置 high=2,low 保持不变。

2、重新计算中间槽的位置 (0+2)/2= 1, 查看槽 1 对应记录的主键值为 4,又因为 4 < 6, 所以设置 low=1, high 保持不变。

3、再计算和比较一轮得知待插入的记录会插入槽2的分组中,但是槽2记录的是 id = 8 这条记录的地址,所以需要拿到槽1的值得到 id = 4 这条记录的地址,从它开始顺着链表指针往后遍历,找到id为6的记录。

组内遍历的次数最多是 8 次。

 

 

· 页面头部 Page Header

该头部记录页的信息,如页内记录数、 Free Space 在页面中的地址偏移、页目录槽数等。

 

 

· 文件头部 File Header

该头部通用于各种类型的页,存储了页号,页的前后指针等。

 

几个重要的属性如下

 

a. 校验和:页面的校验和,校验和就是用某种算法将一个很长的字符串变成一个很短的校验和串,用于判断页内数据是否出错或以外丢失,比较两个校验和 比 比较两个长字符串花的时间少很多。

 

b. 页号:页的唯一ID;

 

c. 页类型(看看就好,别记):

 

d.上一页和下一页指针:只有B+树的叶子和非叶子节点这种类型的页才有上一页和下一页指针。这里的指针是页号。通过这两个指针,页与页之间形成双向链表。

 

e. 页的LSN:页面被最后修改时对应的LSN(日志序列号)。

 

 

· 文件尾部 File Trailer

文件尾部是为防止脏页刷盘时断电或mysql故障导致页面不完整的情况。

尾部包含2部分:页的校验和(与文件头部的校验和一致)和LSN(和头部的LSN一致)。

当页数据被修改,这个修改会先在内存中的页生效,内存中的页会重新计算校验和与LSN并把这两个属性更新到文件头部和尾部。

页刷盘时,是按照操作系统的块(block)为单位刷盘的而不是按页(page)刷盘,刷盘从页头部开始。如果发生断电,一个页只有部分块刷盘成功,那么File Header的 校验和与LSN 肯定与 File Trailer的 校验和与LSN不同。

此时就会通过 redo log 文件恢复该页。




更多内容请关注微信公众号
zbpblog微信公众号

如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息

张柏沛IT技术博客 > Mysql怎么运行的系列(三)InnoDB存储结构之行结构和页结构

热门推荐
推荐新闻