InnoDB数据存储结构

一. InnoDB的数据存储结构：页

索引是在存储引擎中实现的，MySQL服务器上的存储引擎负责对表中数据的读取和写入工作。不同存储引擎中存放的格式一般不同的，甚至有的存储引擎比如Memory都不用磁盘来存储数据，这里讲讲InooDB存储引擎的数据存储结构。

1.1 磁盘与内存交互基本单位：页

InnoDB将数据划分为若干个页，InnoDB中页的大小默认为16KB。  

以 页 作为磁盘和内存之间交互的 基本单位，也就是一次最少从磁盘中读取16KB的内容到内存中，一次最少把内存中的16KB内容刷新到磁盘中。也就是说，在数据库中，不论读一行，还是读多行，都是将这些行所在的页进行加载。也就是说，数据库管理存储空间的基本单位是页（Page），数据库I/O操作的最小单位是页。一个页中可以存储多个行记录。

1.2 页结构概述

页a、页b、页c...页n这些页可以不在 物理结构上相连，只要通过双向链表相关联即可。每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表，每个数据页都会为存储在它里边的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应的分组中的记录即可快速找到指定的记录。

1.3 页的上层结构

• 区（Extent）是比页大一级的存储结构，在InnoDB存储引擎中，一个区会分配 64个连续的页。因为InnoDB中的页大小默认是16KB，所以一个区的大小是64*16KB=1MB。  
• 段（Segment）由一个或多个区组成，区在文件系统是一个连续分配的空间（在InnoDB中是连续的64个页），不过在段中不要求区与区之间是相邻的。段是数据库中的分配单位，不同类型的数据库对象以不同的段形式存在。当我们创建数据表、索引的时候，就会相应创建对应的段，比如创建一张表时会创建一个表段，创建一个索引段。  
• 表空间（Tablespace）是一个逻辑容器，表空间存储的对象是段，在一个表空间中可以有一个或多个段，但是一个段只能属于一个表空间。数据库由一个或多个表空间组成，表空间从管理上可以划分为 系统表空间、用户表空间、撤销表空间、临时表空间等。

二. 页的内部结构

页结构的示意图如下：

作用分别如下：

2.1 第1部分：文件头部 和 文件尾部

File Header

描述各种页的通用信息。（比如页的编号、其上一页、下一页是谁等）

• FIL_PAGE_SPACE_OR_CHKSUM：代表当前页面的校验和（checksum）。文件头部和文件尾部都有该属性。
  • 校验和：就是对于一个很长的字节串来说，我们会通过某种算法来计算一个比较短的值来代表这个很长的字节串，这个比较短的值就称为校验和。在比较两个很长的字节串之前，先比较这两个长字节串的校验和，如果校验和都不一样，则两个长字节串肯定是不同的，所以省去了直接比较两个比较长的字节串的时间损耗。
  • 作用：为了检测一个页是否完整（也就是在同步的时候有没有发生只同步一半的尴尬情况，比如突然断电了），这时可以通过文件尾的校验和（checksum 值）与文件头的校验和做比对，如果两个值不相等则证明页的传输有问题，需要重新进行传输，否则认为页的传输已经完成。
• FIL_PAGE_OFFSET：每一个页都有一个单独的页号，就跟你的身份证号码一样，InnoDB通过页号可以唯一定位一个页。

• FIL_PAGE_TYPE：代表当前页的类型。

• FIL_PAGE_PREV 和 FIL_PAGE_NEXT：InnoDB都是以页为单位存放数据的，如果数据分散到多个不连续的页中存储的话需要把这些页关联起来，FIL_PAGE_PREV和FIL_PAGE_NEXT就分别代表本页的上一个和下一个页的页号。

File Trailer 

• 前4个字节代表页的校验和：这个部分是和File Header中的校验和相对应的。

• 后4个字节代表页面被最后修改时对应的日志序列位置（LSN）：这个部分也是为了校验页的完整性的，如果首部和尾部的LSN值校验不成功的话，就说明同步过程出现了问题。

2.2 第2部分：空闲空间、用户记录 和 最小 最大记录

第二个部分是记录部分，页的主要作用是存储记录，所以 “最大和最小记录” 和 “用户记录” 部分占了页结构的主要空间。

Free Space 

• 我们自己存储的记录会按照指定的行格式存储到User Records部分。但是在一开始生成页的时候，其实并没有User Records这个部分，每当我们插入一条记录，都会从Free Space部分，也就是尚未使用的存储空间中申请一个记录大小的空间划分到User Records部分
• 当Free Space部分的空间全部被User Records部分替代掉之后，也就意味着这个页使用完了，如果还有新的记录插入的话，就需要去申请新的页了，即页分裂。

User Records 

• User Records中的这些记录按照指定的行格式一条一条摆在User Records部分，相互之间形成单链表
• 记录的格式叫行格式

Infimum、Supremum

• 这两条记录（最大、最小记录）不是我们自己定义的记录，所以它们并不存放在页的User Records部分，他们被单独放在一个称为Infimum + Supremum的部分，如图所示：

2.3 第3部分：页目录 和 页面头部

Page Directory

因为单向链表的检索效率不高，最差的情况下需要遍历链表上的所有节点才能完成检索。因此在页结构中专门设计了页目录这个模块，专门给记录做一个目录，通过二分查找法的方式进行检索，提升效率。

• 将所有的记录分成几个组，这些记录包括最小记录和最大记录，但不包括标记为“已删除”的记录
• 最小记录单独作为1组；其余组尽量平分
• 页目录用来存储每组最后一条记录的地址偏移量，这些地址偏移量会按照先后顺序存储起来
• 每组的地址偏移量也被称之为槽（slot），每个槽相当于指针指向了不同组的最后一个记录

Page Header

• 为了能得到一个数据页中存储的记录的状态信息，比如本页中已经存储了多少条记录，第一条记录的地址是什么，页目录中存储了多少个槽等等，特意在页中定义了一个叫Page Header的部分，这个部分占用固定的56个字节，专门存储各种状态信息。

三. InnoDB行格式

我们平时的数据以 行 为单位来向表中插入数据，这些记录在磁盘上的存放方式也被称为行格式或者记录格式。InnoDB存储引擎设计了4种不同类型的行格式，分别是Compact、Redundant、Dynamic和Compressed行格式。

MySQL8的默认行格式：Dynamic

COMPACT行格式

在MySQL 5.1版本中，默认设置为Compact行格式。一条完整的记录其实可以被分为记录的额外信息和记录的真实数据两大部分。

变长字段长度列表（2字节）

MySQL支持一些变长的数据类型，比如VARCHAR(M)、TEXT等类型，这些数据类型修饰列称为变长字段，变长字段中存储多少字节的数据不是固定的，所以我们在存储真实数据的时候需要顺便把这些数据占用的字节数也存起来。在Compact行格式中，把所有变长字段的真实数据占用的字节长度都存放在记录的开头部位，从而形成一个变长字段长度列表。

注意：这里面存储的变长长度和字段顺序是反过来的。比如三个varchar字段在表结构的顺序是zhangsan(08)，lisi(04)，songhk(06)。那么在变长字段长度列表中存储的长度顺序就是06，04，08，是反过来的。

NULL值列表 

Compact行格式会把可以为NULL的列统一管理起来，存在一个标记为NULL值列表中。

之所以要存储NULL是因为数据都是需要对齐的，如果没有标注出来NULL值的位置，就有可能在查询数据的时候出现混乱。如果使用一个特定的符号放到相应的数据位表示空置的话，虽然能达到效果，但是这样很浪费空间，所以直接就在行数据得头部开辟出一块空间专门用来记录该行数据哪些是非空数据，哪些是空数据，格式如下：

• 二进制位的值为1时，代表该列的值为NULL
• 二进制位的值为0时，代表该列的值不为NULL

注：若为主键或者NOT NULL字段则会自动跳过，不用在NULL值列表中存储

记录头信息（5字节）

创建 page_demo

CREATE TABLE page_demo(->     c1 INT,->     c2 INT,->     c3 VARCHAR(10000),->     PRIMARY KEY (c1)-> ) CHARSET=ascii ROW_FORMAT=Compact;

这些记录头信息中各个属性如下：

简化后的行格式示意图： 

插入数据： 

INSERT INTO page_demo 
VALUES
(1, 100, 'song'), 
(2, 200, 'tong'), 
(3, 300, 'zhan'), 
(4, 400, 'lisi');

图示如下：

delete_mask

• 这个属性标记着当前记录是否被删除，占用1个二进制位。
  • 值为0：代表记录并没有被删除
  • 值为1：代表记录被删除掉了
• 这些被删除的记录之所以不立即从磁盘上移除，该位为 1 表示记录已被删除，但是该行的空间可以被重用，即在新的数据插入时可以覆盖原有的数据。

min_rec_mask

• B+树的每层非叶子节点中的最小记录都会添加该标记，min_rec_mask值为1。
• 我们自己插入的四条记录的min_rec_mask值都是0，意味着它们都不是B+树的非叶子节点中的最小记录。

record_type

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

heap_no

• 这个属性表示当前记录在本页中的位置。
• MySQL会自动给每个页里加了两个记录，由于这两个记录并不是我们自己插入的，所以有时候也称为伪记录或者虚拟记录。这两个伪记录一个代表最小记录，一个代表最大记录。最小记录和最大记录的heap_no值分别是0和1，也就是说它们的位置最靠前。

n_owned 

• 页目录中每个组中最后一条记录的头信息中会存储该组一共有多少条记录，作为 n_owned 字段。

next_record

• 记录头信息里该属性非常重要，它表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量。
• 比如：第一条记录的next_record值为32，意味着从第一条记录的真实数据的地址处向后找32个字节便是下一条记录的真实数据。
• 注意，下一条记录指得并不是按照我们插入顺序的下一条记录，而是按照主键值由小到大的顺序的下一条记录。而且规定Infimum记录（也就是最小记录）的下一条记录就是本页中主键值最小的用户记录，而本页中主键值最大的用户记录的下一条记录就是 Supremum记录（也就是最大记录）。下图用箭头代替偏移量表示next_record。

Dynamic和Compressed行格式

行溢出

一个页面存放不了一条记录

MySQL对一条记录占用的最大存储空间是有限制的，除BLOB或者TEXT类型的列之外， 其他所有的列（不包括隐藏列和记录头信息）占用的字节长度加起来不能超过65535个字节。

在MySQL 8.0中，默认行格式就是Dynamic，Dynamic、Compressed行格式和Compact行格式挺像，只不过在处理行溢出数据时有分歧：

• 在 Compac t和 Reduntant 行格式中，对于占用存储空间非常大的列，在记录的真实数据处只会存储该列的一部分数据，把剩余的数据分散存储在几个其他的页中进行分页存储，然后记录的真实数据处用20个字节存储指向这些页的地址（当然这20个字节中还包括这些分散在其他页面中的数据的占用的字节数），从而可以找到剩余数据所在的页。
• Dynamic 和 Compressed 两种记录格式对于存放在BLOB中的数据采用了完全的行溢出的方式。如图，在数据页中只存放20个字节的指针（溢出页的地址），实际的数据都存放在Off Page（溢出页）中。