ySQL服务器上负责对表中的数据的读取和写入的工作的部分是存储引擎,而关于服务器会支持不同类型的服务器,如:InnoDB、MyISAM、Memory……

前言

不同的存储引擎都是为了实现不同的特性进行开发的,真实数据的存储在不同的存储引擎中存放的格式一般是不同的,有的存储引擎比如Memory都不用磁盘来存储数据,就跟NoSQL一样,服务器关闭后数据就不见了。InnoDB是MySQL的默认储存引擎,也是我们大家常用的存储引擎。

Mysql把页作为管理存储空间的基本单位,一个页的大小一般是16KB

InnoDB页

简介

InnoDB是一个将表中的数据存储到磁盘上的存储引擎,所以即使关机后重启我们的数据还是存在的。而真正处理数据的过程是发生在内存中的,所以需要把磁盘中的数据加载到内存中,如果是处理写入或修改请求的话,还需要把内存中的内容刷新到磁盘上。而我们知道读写磁盘的速度非常慢,和内存读写之间的差距就不再多说,所以当我们想从表中获取某些记录时,InnoDB存储引擎需要一条一条的把记录从磁盘上读出来么?不,那样会慢死,InnoDB采取的方式是:将数据划分为若干个页,以页作为磁盘和内存之间交互的基本单位,InnoDB中页的大小一般为 <strong>16</strong>KB。也就是在一般情况下,一次最少从磁盘中读取16KB的内容到内存中,一次最少把内存中的16KB内容刷新到磁盘中。

页结构

页的本质介绍一个大小为16KB大小的存储空间,页有很多种类型的,不同的类型有不同的作用;

用于存储记录的页被称为数据页 ,大小也为16KB,但是这16KB大小的存储空间被划分为多个部分,不同的部分当然有着不同的功能,结构如下:

从上面的图可以看到,InnoDB的页结构分为七个部分,下面用表格说明一下各个部分对应的作用:
名称 中文名 占用空间大小 简单描述
File Header 文件头 38字节 描述页的信息
Page Header 页头 56字节 页的状态信息
Infimum + SupreMum 最小记录和最大记录 26字节 两个虚拟的行记录(后面会说明)
User Records 用户记录 不确定 实际存储的行记录内容
Free Space 空闲空间 不确定 页中尚未使用的空间
Page Directory 页目录 不确定 页中的记录相对位置
File Trailer 文件结尾 8字节 结尾信息
下面会详细介绍他们的作用

页中的存储

当我们在存储数据的时候,记录会存储到User Records部分 。但是在一个页新形成的时候是不存在User Records 这个部分的,每当我们在插入一条记录的时候,都会从Free Space中去申请一块大小符合该记录大小的空间并划分到User Records,当Free Space的部分空间全部被User Records部分替换掉之后,就意味着当前页使用完毕,如果还有新的记录插入,需要再去申请新的页,过程如下:

记录头

对于User Records中的每一条记录的管理,MySQL做了很多的处理,究竟做出了什么处理呢,这需要从每条记录里面的记录的额外信息部分中的记录头信息说起 这是有关行格式的知识,关于行格式(指的就是一条记录的存储结构,有多种格式),有兴趣的可以去看一下InnoDB记录存储结构 这篇文章。

首先,创建一个表:
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)
mysql>;

如上所示,表中有三列,c1和c2用来存储整数的,c3用来存储字符串的。因为指定了主键为c1,所以MySQL就不会去创建那个隐藏的 row_id 列。指定了ascii字符集以及Compact的行格式,所以里面的每一条记录的行格式如下:

先看一下行格式中每个属性代表的意思:
名称 大小(单位: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 表示下一条记录的相对位置
由于这里只是描述在User Records中记录头的作用,所以下面只会说明一些相关的属性以及c1、c2、c3列的信息(其他信息没画不代表它们不存在,只是为了理解上的方便省略了~),简化后的行格式示意图就是这样:

我们往表中插入几条数据:
mysql>; INSERT INTO page_demo VALUES(1, 100, 'aaaa'), (2, 200, 'bbbb'), (3, 300, 'cccc'), (4, 400, 'dddd');
Query OK, 4 rows affected (0.00 sec)
Records: 4 Duplicates: 0 Warnings: 0

mysql>;

下面看看几条记录在页中的User Records是以何种形式进行体现的,为了方便理解,下面的图中把记录中的头信息和实际的数据都用的十进制进行的表示(其实都是二进制):


 
下面说说,记录头中的各个部分代表的含义:

delete_mask

这个属性说的是当前这条记录是否被删除,当值为0的时候代表着没有被删除,为1的时候标志着被删除了。

是的,您没看错,当您执行删除一个记录的操作的时候,被删除的记录还存在页中,您对它进行了删除,它会把的

记录头中的这个属性设置为1,只是打了个标记。

原因

这些被删除的记录之所以不立即从磁盘上移除,是因为移除它们之后把其他的记录在磁盘上重新排列需要性能消耗,所以只是打个删除标记而已,而且这部分存储空间之后还可以重用,也就是说之后如果有新记录插入到表中的话,可能把这些被删除的记录占用的存储空间覆盖掉。

如果您想彻底的从磁盘上移除这些被删除的记录,可以使用这个语句:

optimize table '表名';

执行这个命令后服务器会重新规划表中记录的存储方式,把被标记为删除的记录从磁盘上移除。

min_rec_mask

有关索引的,暂时不说,后面说到索引会说明;

n_owned

下面会讲

heap_no

这个属性是表示的当前记录在当前页中的位置,上面的一张图如果您仔细看了的话,会发现它们的位置分别是2、3、4、5,那么问题来了? 0和1呢?

这是因为在每次创建的一页里面会自动的加入两条记录,这被称为伪记录 或者 虚拟记录 (因为不是我们自己插入的);

这两条伪记录一个代表着最小记录,一个代表着最大记录 ;

记录大小的比较是通过主键值来比较的。在上面我们插入的几条记录中的从小到大的顺序就是:1 &lt; 2 &lt; 3 &lt; 4,

这标志着这4条记录的大小依次递增。

不管我们插入了什么数据,页中的最小记录 和 最大记录 都是页生成时候的那两条伪记录。这两条伪记录的结构页相对简单,如下:

还记得页结构组成的七部分中一个部分叫Infimum + SupreMum ,这个部分用来存储最小记录和最大记录的,没错,就是这两条伪记录。

原因:由于这两条记录不是我们自己定义的记录,所以它们并不存放在页的User Records部分,他们被单独放在一个称为Infimum + Supremum的部分

由上面的图可以看出,最小记录和最大记录的heap_no的值分别为0和1,也就是说它们的位置最靠前。

record_type

这个属性表示当前记录的类型,一共有4种类型的记录,0表示普通记录,1表示B+树非叶节点记录,2表示最小记录,3表示最大记录。从图中我们也可以看出来,我们自己插入的记录就是普通记录,它们的record_type值都是0,而最小记录和最大记录的record_type值分别为2和3 ,关于1暂且不说;

next_record

这个属性表示这从当前记录真实数据到下一条记录的真实数据的地址偏移量 ;

假如有一条记录的next_record 的值为12,就标志着从这条记录的真实数据的地址往后找12个字节就是下一条记录的真实数据(链表)。也就是说页中的数据之间的联系是一个<strong>根据大小</strong>比较后从小指到大的<strong>单向链表</strong>。



规定 <strong>最小记录</strong> 的下一条记录就本页中主键值最小的记录,而本页中主键值最大的记录的下一条记录就是 <strong>最大记录</strong>(最大的那条伪记录) ,为了更形象的表示一下这个next_record起到的作用,我们用箭头来替代一下next_record中的地址偏移量:

从上面可以看出,最大记录 的 next_record 的值为0,代表着最大记录的下一条记录是不存在的,它也是链条中的最后一个节点。

当我们从页中删除一条数据后可以看看链表会发生那些变化:
mysql>; DELETE FROM page_demo WHERE c1 = 2;
Query OK, 1 row affected (0.02 sec)

mysql>;


删掉第2条记录后的示意图就是:

从上面可以看到:

当我们删除第二条记录后,链表中的变化最明显的就是各个节点之间的联系,它会把被删除数据的上一条记录和被删除数据的下一条数据进行关联(这条数据还是存在的,之前说的那个删除标记别忘了哦)。

  • 第2条记录并没有从存储空间中移除,而是把该条记录的delete_mask值设置为1。
  • 第2条记录的next_record值变为了0,意味着该记录没有下一条记录了。
  • 第1条记录的next_record指向了第3条记录。
  • 还有一点您可能忽略了,就是最大记录的n_owned值从5变成了4,关于这一点的变化我们稍后会详细说明的。

所以得到:不论我们怎么对页中的记录做增删改操作,InnoDB始终会维护一条记录的单链表,链表中的各个节点是按照主键值由小到大的顺序连接起来的。

下面我们再做一个操作,把删除的记录再次插入:
mysql>; INSERT INTO page_demo VALUES(2, 200, 'bbbb');
Query OK, 1 row affected (0.00 sec)
mysql>;

我们来看看发生了什么变化:

很明显的可以看到,InnoDB并没有因为新记录的插入而为它申请新的存储空间,而是直接复用了原来被删除记录的存储空间。

Page Directory

通过上面,我们知道到了页中记录是一个按照大小从下到大连续的单向链表,现在来想想,当我们根据主键查询一条记录的时候是怎样进行的,我们来看看;
SELECT * FROM page_demo WHERE c1 = 3;

上面是一条查询语句,我们想想它的执行方式可能是:

从最小记录开始,沿着链表一直往后找,总有一天会找到(或者找不到),在找的时候还能投机取巧,因为链表中各个记录的值是按照从小到大顺序排列的,所以当链表的某个节点代表的记录的主键值大于您想要查找的主键值时,如果这个时候还没找到数据的话您就可以停止查找了(代表找不到),因为该节点后边的节点的主键值都是依次递增。

上面的方式存在的问题就是,当页中的存储的记录数量比较少的情况用起来也没啥问题,但是如果一个页中存储了非常多的记录,这么查找对性能来说还是有损耗的,所以这个方式很笨啊。

我们来看看InnoDB 的处理方式:InnoDB 的处理方式相当于我们平时看书的时候,想看那一章的时候不会傻到去一页一页的找,而是通过目录去找到对应的页数,直接就定位过去了。说说InnoDB 这样处理的步骤吧:

  • 将所有正常的记录(包括最大和最小记录,不包括标记为已删除的记录)划分为几个组。

  • 每个组的最后一条记录的头信息中的n_owned属性表示该组内共有几条记录。

  • 将每个组的最后一条记录的地址偏移量按顺序存储起来,每个地址偏移量也被称为一个槽(英文名:Slot)。这些地址偏移量都会被存储到靠近页的尾部的地方,页中存储地址偏移量的部分也被称为Page Directory 。

比如说,现在表中有6条记录,InnoDB会把它们分成两组,第一组中只有一个最小记录,第二组中是剩余的5条记录,看下边的示意图:

从上面的图中可以看到:
  • Page Directory中有两个槽,也就是两个组,槽0的值是90,代表最小记录的地址偏移量;槽2的值是112,代表最大记录的地址偏移量;
  • 注意记录中的最小记录和最大记录,他们分别是1和5:
  •  
    • 最小记录的n_owned 的值为1,代表着以最小记录结尾的这个分组中只有1条记录,就是最小记录本身;
    • 同理,最大记录的n_owned 的值为5,代表着以最大记录结尾的这个分组中只有5条记录,这5条记录包括它本身,就是说除了它本身还有其它4条记录;

我们用图来表示一下:

上面的图中为了方便理解,暂时没管各条记录在存储设备上的排列方式了,单纯从逻辑上看一下这些记录和页目录的关系。真实的Page Directory 是在下面的。

再说说,为什么最小记录的n_owned值为1,而最大记录的n_owned值为5呢?它们是怎么分配的?

InnoDB 对每个分组中的记录条数是有规定的,对于最小记录所在的分组只能有 1 条记录,最大记录所在的分组拥有的记录条数只能在 18 条之间,剩下的分组中记录的条数范围只能在是 48 条之间。所以分组是按照下边的步骤进行的:

  • 初始情况下一个数据页里面只有最小记录和最大记录(伪记录),它们属于不同的分组,也就是两个;
  • 之后插入的每一条记录都会放到最大记录所在的组,直到最大记录所在组的记录数等于8条;
  • 当最大记录所在组中的记录数等于8条的时候,如果还有记录插入的话,就会将最大记录所在组平均分裂成2个组,这个时候最大记录所在组就只剩下4条记录,这里再把这条记录再放入最大记录所在组;
我们一口气又往表中添加了12条记录,现在就一共有16条正常的记录了(包括最小和最大记录),这些记录被分成了5个组,如图所示:

上图中,只保留了头信息中的n_owned和next_record属性,也省略了各个记录之间的箭头,没画不等于没有!

因为各个槽代表的记录的主键值都是从小到大排序的,所以我们可以使用二分法来进行快速查找。4个槽的编号分别是:0、1、2、3、4,所以初始情况下最低的槽就是low=0,最高的槽就是high=4。比方说我们想找主键值为5的记录,现在我们再来看看查找一条记录的步骤:

  • 首先得到中间槽的位置:(0 + 4)/2 = 2 ,所以得到槽2,根据槽2的地址偏移量知道它的主键值是8,因为8>;5,设置high=2 ,low不变;

  • 再次计算中间槽的位置:(0 + 2)/2 = 1 ,所以得到槽1,根据槽1的地址偏移量知道它的主键值是4, 因为4<5,设置low=1 ,high不变;

  • 因为high - low的值为1,所以确定主键值为5的记录在槽1和槽2之间,接下来就是遍历链表的查找了;

所以在一个数据页中查找指定主键值的记录的过程分为两步:

  • 通过二分法确定该记录所在的槽。

  • 通过记录的next_record属性组成的链表遍历查找该槽中的各个记录。

设计InnoDB的大叔们为了能得到一个数据页中存储的记录的状态信息,比如本页中已经存储了多少条记录,第一条记录的地址是什么,Page Directory中存储了多少个槽等等,特意在页中定义了一个叫Page Header的部分,它是页结构的第二部分,这个部分占用固定的56个字节,专门存储各种状态信息,具体各个字节都是干嘛的看下表:

名称 大小(单位:byte)
PAGE_N_DIR_SLOTS 2 在页目录中的槽数量
PAGE_HEAP_TOP 2 第一个记录的地址
PAGE_N_HEAP 2 本页中的记录的数量(包括最小和最大记录以及标记为删除的记录)
PAGE_FREE 2 指向可重用空间的地址(就是标记为删除的记录地址)
PAGE_GARBAGE 2 已删除的字节数,行记录结构中delete_flag为1的记录大小总数
PAGE_LAST_INSERT 2 最后插入记录的位置
PAGE_DIRECTION 2 最后插入的方向
PAGE_N_DIRECTION 2 一个方向连续插入的记录数量
PAGE_N_RECS 2 该页中记录的数量(不包括最小和最大记录以及被标记为删除的记录)
PAGE_MAX_TRX_ID 2 修改当前页的最大事务ID,该值仅在二级索引中定义
PAGE_LEVEL 2 当前页在索引树中的位置,高度
PAGE_INDEX_ID 8 索引ID,表示当前页属于哪个索引
PAGE_BTR 10 非叶节点所在段的segment header,仅在B+树的Root页定义
PAGE_LEVEL 10 B+树所在段的segment header,仅在B+树的Root页定义
如果大家认真看过前边的文章,那么大致能看明白这里头前边一半左右的状态信息的意思,剩下的状态信息看不明白不要着急,饭要一口一口吃,东西要一点一点学。在这里想强调以下PAGE_DIRECTION和PAGE_N_DIRECTION的意思。
  • PAGE_DIRECTION

    假如新插入的一条记录的主键值比上一条记录的主键值比上一条记录大,我们说这条记录的插入方向是右边,反之则是左边。用来表示最后一条记录插入方向的状态就是PAGE_DIRECTION。

  • PAGE_N_DIRECTION

    假设连续几次插入新记录的方向都是一致的,InnoDB会把沿着同一个方向插入记录的条数记下来,这个条数就用PAGE_N_DIRECTION这个状态表示。当然,如果最后一条记录的插入方向改变了的话,这个状态的值会被清零重新统计。

File Header

如果说Page Header描述的是页内的各种状态信息,比方说页里头有多少个记录了呀,有多少个槽了呀,那么File Header描述的就是页外的各种状态信息,比方说这个页的编号是多少,它的上一个页、下一个页是谁啦。File Header是InnoDB页的第一部分,这个部分占用固定的38个字节,下边我们看看这个部分的各个字节都是代表啥意思吧:
名称 大小(单位:byte) 描述
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值,独立表空间中都是0
FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID 4 页属于哪个表空间
对照着这个表格,我们看几个目前比较重要的部分:
  • FIL_PAGE_SPACE_OR_CHKSUM

    这个代表当前页面的校验和(checksum)。啥是个校验和?就是对于一个很长很长的字节串来说,我们会通过某种算法来计算一个值,这个值就称为校验和。这样在比较两个很长的字节串之前先比较这两个长字节串的校验和,如果校验和都不一样两个长字节串肯定是不同的(hashCode和equals),所以省去了直接比较两个比较长的字节串的时间损耗(和后面的File Trailer里面的那个相对应,看到后面您就明白了)。

  • FIL_PAGE_OFFSET

    每一个页都有一个单独的页号,就跟您的身份证号码一样,InnoDB通过页号来可以唯一定位一个页。

  • FIL_PAGE_TYPE

    这个代表当前页的类型,我们前边说过,InnoDB为了不同的目的而把页分为不同的类型,本集中介绍的其实都是存储记录的数据页,其实还有很多别的类型的页:

  • FIL_PAGE_PREV和FIL_PAGE_NEXT

    一张表中可以有成千上万条记录,一个页只有16KB,所以可能需要好多页来存放数据,FIL_PAGE_PREV和FIL_PAGE_NEXT就分别代表本页的上一个和下一个页的页号(双向链表)。

  • Page Header 的其它属性就不说了;

File Trailer

对于这个部分,我的理解比较简单,我们知道InnoDB 会把数据从内存刷新到磁盘,中间交互的单位是页 ,但是我们想想,假如再刷新到磁盘的时候出现了问题,这样的话怎么办呢?

这就是File Trailer 作用,这个部分由8个字节组成,可以分成2个小部分:

  • 前四个字节代表页的检验和:
  •  
    • 这个部分是和File Header中的校验和相对应的。每当一个页面在内存中修改了,在同步之前就要把它的校验和算出来,因为File Header在页面的前边,所以校验和会被首先同步到磁盘,当完全写完时,校验和也会被写到页的尾部,如果完全同步成功,则页的首部和尾部的校验和应该是一致的,反之意味着同步中间出了错;
  • 后四个字节代表日志序列位置(LSN)
    • 这个部分也是为了校验页的完整性的,可以先不用管这个属性。

总结

  1. InnoDB为了不同的目的而设计了不同类型的页,用于存放我们记录的页也叫做数据页
  2. 一个数据页可以被分为7个部分,分别是
    • File Header,表示文件头,占固定的38字节。
    • Page Header,表示页里的一些状态信息,占固定的56个字节。
    • Infimum + Supremum,两个虚拟的伪记录,分别表示页中的最小和最大记录,占固定的26个字节。
    • User Records:真实存储我们插入的记录的部分,大小不固定。
    • Free Space:页中尚未使用的部分,大小不确定。
    • Page Directory:页中的记录相对位置,也就是各个槽在页面中的地址偏移量,大小不固定,插入的记录越多,这个部分占用的空间越多。
  1. 每个记录的头信息中都有一个next_record属性,从而使页中的所有记录串联成一个单向链表。
  2. InnoDB会为把页中的记录划分为若干个组,每个组的最后一个记录的地址偏移量作为一个槽,存放在Page Directory中,所以在一个页中根据主键查找记录是非常快的,分为两步:
  3.  
    • 通过二分法确定该记录所在的槽。
    • 通过记录的next_record属性组成的链表遍历查找该槽中的各个记录。
  4. 每个数据页的File Header部分都有上一个和下一个页的编号,所以所有的数据页会组成一个双链表。
  5. 为保证从内存中同步到磁盘的页的完整性,在页的首部和尾部都会存储页中数据的校验和和LSN值,如果首部和尾部的校验和和LSN值校验不成功的话,就说明同步过程出现了问题。

最后

本文的大部分内容都是参考并使用的原文中的内容,只是在中间加入了一些自己的理解,并希望把它更清楚的表达出来,大家也可以去看看原文:
 InnoDB数据页结构