InnoDB数据存储架构剖析
1. InnoDB页的数据结构剖析
2. InnoDB整体的数据结构分析
3. InnoDB行存储详解
关于内存和数据结构这块应该是最晦涩难懂的，无论是我们平时工作的应用，又或是八股文，重点往往都不是这里。但也是学习数据库进阶不可缺少的部分。
在本文里，我们将进一步去了解在使用InnoDB引擎的前提下，MySQL是“如何存储数据”的。以及InnoDB是如何规划空间，合理设计存储空间来提升效率的。
大致的内容如下：
InnoDB数据结构剖析
现如今，InnoDB是MySQL的默认引擎，要搞清楚MySQL工作的内存结构，首先就是要了解InnoDB是如何存储数据的？
从空间结构来划分，InnoDB把内存划分为：表空间、段、区、页。我们知道，MySQL的I/O操作的最小单位是“页”，一页的默认大小是16K（一页可能会包含多行数据）。
但是一页除了数据之外，还夹杂了许多额外的信息
InnoDB页数据结构
InnoDB页的数据结构划分如下：
File Header（文件头）
主要描述页的通用信息，主要的有：页编号，页指针等。File Header的主要组成结构如下：
FIL_PAGE_SPACE_OR_CHECK: 页的校验和；页的完整性校验，这玩意基本上是所有说得出的协议都会有的了。保证页的完整，未丢失、修改
FIL_PAGE_OFFSET：页编号；类似数据库里的主键ID，全局唯一的
FIL_PAGE_PREV，FIL_PAGE_NEXT：页的上一页、下一页编码，分别对应两根指针。使用innoDB引擎时，索引的数据结构为B+树。其中，树的叶子节点还维护了一条双向链表。该链表就是通过Page中的File Header里的双指针来维护的，建立数据页逻辑上的连续。如下： 页和页之间不需要物理连续，本质上是逻辑连续
FIL_PAGE_LSN：页面被修改的日志序列位置
FIL_PAGE_TYPE：页的类型，表示这是什么页
FIL_PAGE_FILE_FLUSH_LSN：代表页被刷到了对应的LSN
FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID：页是属于哪个表空间下的
File Tailer（文件尾部）
文件尾部主要和文件头部做呼应，主要组成结构如下：
CHECK_SUM：页的校验和，和File Header中的CHECK相呼应
FIL_PAGE_LSN：页面最近被修改时的日志序列位置，和File Header中的PAGE_LSN相呼应
File Header和File Tailer前后相呼应，两个字段均和Header相对应，保证页的完整性
User Records
User Record存放具体的行数据，可将User Records细分为：Free Space和Used Space。对于刚刚申请的页来说，User Record为空的， 随着数据的不断插入，Free Space逐渐减少。插入流程如下：
如上图，页中的数据之间是采用链表连接的。随着数据的插入，Free Space逐渐减少，当Free Space == 0时，就需要申请新的空闲数据页。
Infimum + supremum
最小+最大记录；用于记录User Records中主键最大和最小的记录。如果往一张表中连续插入id = 1, 2, 3, 4, 5的记录。假设这五条记录都在同一数据页中，则Infimum + supremum记录如下：
Page Directory
页目录（快速定位页中的数据）；存放数据在页中的具体位置。和索引的作用类似，避免全页的数据扫描，通过目录定位的方式找到数据在页中的具体位置
如下，一页中有n条数据，需要查询记录Record_m（1 < m < n）。首先是通过B+树，找到记录所在的页Page_1，随后通过二分法的方式，查找页目录上的记录，准确定位数据。
Page Directory是如何生成的？
首先，页中的数据不是无序的，会按一定的规则进行分组，分组的规则如下：
- 第一组只会有一条记录，即（当前页的主键）最小记录
- 最后一组会有1-8条记录，包含（当前页的主键）最大记录
- 中间组的记录数量在4~8条之间
- 每个组的最后一条记录的头信息，会记录该组有多少条数据，存在一n_owned字段
页目录里都记录了啥：用来记录每一组的最后一条记录的地址偏移量，slot；每一个slot都会指向不同组的最后一条记录
往表中插入八条数据，id=1-8，假设这八条数据都在同一页，该页的页目录和分组情况如下：
一共分三组，id最小的记录单独一组，而三组对应了三个slot，分别保存在Page directory里。
现在，想要查找id = 3的记录，找到该页后，便是通过二分法，在Page Directory里找到slot_1，再顺着找到对应的分组，最后遍历组内成员找到记录。
Page Header
页头；描述当前数据页存储的记录状态信息，具体保存的信息如下：
总结
总的来说，可以将InnoDB页数据结构按功能划分为三个模块，分别是：页的通用、校验信息；数据记录、存储区域；数据存储的状态记录
InnoDB空间结构划分
我们知道，数据页是MySQL做I/O操作的最小单位，而InnoDB也不单只有页。将空间划分为：段、区、页、行。关系如下图：
表空间是由许多段组成的；而段是由许多区组成的；区是由许多页组成的；页当中存储着行数据。
看到这个，首先要搞明白一件事，为什么InnoDB要这么划分空间？即InnoDB空间结构划分缘由
为什么要有区？
若表中的数据量特别大的话，一页肯定是装不下的，需要分数据页存储。在InnoDB的页结构处，我们已知：页和页之间是通过File Header内的前后指针相连的，即逻辑连续。
如果一次B+树查询的数据量较大，需要涉及多个逻辑相邻的数据页，而这些数据页的物理位置如果相隔很远，会产生大量的随机IO。（不断地寻址，读取，消耗性能）
而InnoDB是如何解决的呢？
就是让逻辑相邻的数据页的物理位置也做到相邻，便可以使用顺序IO，一次性读取。因此，“区”就诞生了，一个区默认包含64页。大小为：64*16=1M
在最开始给索引分配数据空间时，直接按区分配（不是按页），让数据页的位置尽量做到物理和逻辑相邻。
为什么要有段？
“区”的存在解决了数据页之间物理位置上的不连续问题。假设内存全是按区分配，可能会出现如下问题：
我们知道页有叶子节点页和非叶子节点页。叶子节点页存放的是行数据（主键索引）或者是主键ID（普通索引）；而非叶子节点页存放的是指向页的指针。假设不区分，把所有页都放到区中，如下：
在范围扫描时，通过非叶子页，找到叶子页后，开始做数据的遍历，可能会出现跨区扫描的情景，万一横跨的物理距离较大，效率也是会大打折扣的。如下：
因此，为了避免跨区扫描，需要对其进行区别对待，将存在叶子节点的区集合为叶子节点段；将非叶子节点的区集合为非叶子节点段。
在日志篇中，我们讲了undo log的存放地址，表空间中开辟了专门一空间用于存放，这一空间就是“段”，也称为“回滚段”。MySQL的三大日志作用
需要注意的是：段只是逻辑上的概念，我们将哪几个区几个区合并在一起，称为段。在物理地址上，其实有可能是不连续的。段是由多个区，以及零散的页面组成的。
在InnoDB中，存在的常见的段有：
- 索引段；存放B+树中非叶子节点的区的集合
- 数据段：存放B+树中叶子节点的区的集合
- 回滚段：存放的是回滚数据版本的区的集合，事务的原子性以及MVCC的具体实现均是通过回滚段来完成的
段结构引发的内存问题
按“段”这样的结构划分，难免会产生内存碎片的问题。如果按之前的结构划分，表中创建一个索引时，必然会产生两个段（索引段和数据段），而段是逻辑上的概念，是以区为单位来申请的，一个区默认会占用1M。于是会产生一个问题，即使是存了几条数据的表，也要2M的存储空间，完全是浪费空间！ 如下：
因此，还额外提出了一个碎片区的概念，用于解决浪费内存的问题。
碎片区同样是会存放数据页。但是不同于普通的区，在一个碎片区中，不是所有的页都会属于一个段，有些页用于段A，有些页用于段B。为了不额外创建多余的区，把它们统一放在一起。
回归到一开始的问题，表中创建一个索引树时，这时候段是如何分配空间的呢？
因此，这样也能解释一开始说的：段是由多个区+碎片区中的零散页面组成
表空间的划分
回顾一开始的结构图可知，表空间下包含了多个段。而表空间也可细分为：独立表空间和系统表空间
独立表空间： 每张我们自己创建的业务表，都会生成一个独立的表空间。表和表之间的空间是独立的，互相隔离。数据和索引等信息都会保存在表空间里，表空间下的结构由：段、区、页组成。
系统表空间： MySQL中存在一些系统表，整个MySQL共同维护一份系统表空间。系统表空间记录了整个系统信息的页面。
- 表和独立表空间的关系
- 定义了大量系统表，主要是存放在information_schema和performance_schema里，系统表如下：
InnoDB表数据结构总结
InnoDB行格式介绍
在第一部分，我们分别梳理了InnoDB表空间的结构，粒度由大到小：表空间 -> 段 -> 区 -> 页。页并非是存储的最小单位（只是I/O的最小单位），页当中还存储着行数据，而行数据也有着不同的格式，存储方式，存储内存限制等，内容大纲如下，会在本篇章一一展开
行格式类型
在介绍MySQL的日志时，我们知道binlog的存储格式有三种，分别是statement，mixed，row。对于行格式，InnoDB也提供了4种格式存储，如下：
- Redundant：非紧凑型行格式，MySQL5.0以前用的行格式存储，现已被淘汰
- Compact：紧凑型行格式，能让一个数据页中尽可能地存储数据
- Dynamic和Compressed；紧凑型行格式，在Compact的基础上，做了一定的扩展。其中Dynamic也是MySQL5.7后的默认行格式
其中，我们着重关注紧凑型行格式，了解其数据结构，是如何能做到：存储更多数据
Compact行格式详解
当行存储格式为：Compact时，行数据存储的数据结构可划分为：变长字段长度列表，NULL值列表，记录头信息，记录的真实数据。 如下：
变长字段长度列表
该列表记录了表中该行所有变长字段的真实数据占用的字节长度。具体要如何理解这句话呢？
在MySQL中支持一些长度可变化的数据类型，例如VARCHAR，VARBINARY，TEXT等等，这些类型存储的数据的字节长度是不固定的。因此额外开辟了一个空间来存储这些数据所占用的真实字节长度。
假设存在一张表User，表的编码为ASCII字符集（一个字符占用一个字节），表中存在col1，col2，col4三个可变长度数据类型，均为VARCHAR类型，表中列存储的数据对应数据占用的内容长度关系如下：
该行数据的可变长度数据类型存储的内容分别为：test，test2，testtest，内容占用的字节长度分别为：4，5，8。 因此，变长字段长度列表为：040508，又因为长度值需要按照列的逆序存放。最终，变长字段长度列表为：080504。
NULL值列表
为了保持数据对齐的效果（作用有点像是Java中对象的组成部分：对其填充），避免在查询的时候出现混乱。因此额外开辟了一个空间来记录该行数据的非NULL和NULL值数据。记录的规则如下：
- 二进制的值为1：该列的值为NULL
- 二进制的值为0：该列的值不为NULL
假设存在一张表User，表存在三列：col1，col2，col4。三列的数据类型均为可为NULL的VARCHAR。假设表中存在两列数据，如下：
存储内容1，即行1的字段均不会NULL，因此该行的NULL值列表为：000
存储内容2，即行2的col2和col4为NULL，因此该行的NULL值列表为：110（同可变字段长度列表，按照列的逆序存放）
记录头信息
头信息记录了该行的一些基本信息，详细的数据结构如下：
delete_mask：标记当前记录是否被删除。0：否；1：是；在日志篇中我们提过，删除一条行记录时，会把该值标记为1，当事务回滚时，又会将该值重新标记为0
min_rec_mask：如果该行存储的是非叶子节点，并且是该节点所在的层的最小记录，则标记为1，否则为0
next_record：指向下一条行记录的指针。在前面我们详述页的数据结构时，有提到数据页中的行是逻辑连续的，即通过next_record指针指向
heap_no：记录当前记录在本页中的位置。当一张表连续插入4条数据，对应的heap_no为2，3，4，5。（0和1会自动跳过，分别用于表示该页的最大记录和最小记录）
n_owned：记录该行所在的组里有多少条数据，在介绍InnoDB数据页结构时，可知InnoDB会将数据页的数据做分组，便于通过Page directory做二分法查询数据。而组里的最后一条行记录中的n_own会记录该组中有多少条数据。
record_type：表示该条记录的属性。0：普通记录；1：B+树非叶子节点；2：最小记录；3：最大记录
真实数据
InnoDB有专门的空间来存储真实的行数据。真实的行数据包含：我们自己定义的业务数据，以及三列隐藏列，如下：
row_id： 行ID，唯一标识符
trx_id： 事务ID，用于MVCC可见性判断
roll_pointer： 回滚指针，保证事务的原子性以及用于MVCC可见性判断
为什么变长字段列表和NULL值列表要逆序存储？
在了解InnoDB的行存储结构之后，我们知道每一条行数据的变长字段列表和NULL值列表均是逆序存储的，为什么要这么设计呢？如下，是MySQL使用InnoDB引擎存储的完整的行数据结构顺序：
同一张数据页中，行和行之间是通过Record Head中的next_record连接的，连接的数据结构如下：
next_record的左边是记录头信息、NULL值列表、数据占用字节行数等基础信息，右边是真实数据。数据结构这样设计的好处就是可直接通过指针，将真实数据完整隔离开。
回到我们一开始的问题，为什么两个字段列表都要逆序存储？
结合上面的存储结构，我们细想便可知道逆序存储的目的是：从指针的左右蔓延开来，能让真实数据的行字段和其对应的字段长度信息（是否NULL，真实长度）能一一对应起来，在读取的时候尽可能地让行字段和其对应地字段长度信息都在同一个CPU cache里面，提高CPU cache的命中率
VARCHAR(N)的存储实战
对于记录的存储空间分配，MySQL有规定，一行记录（不包含隐藏列和记录头的信息）占用的字节长度最多不能超过65535个字节
当字段类型为VARCHAR(N)时，N的最大值为多少？
VARCHAR(N)字段类型的N表示的是字符数量，非字节大小！不同的字符集选择，字符所占用的字节也是不同的。
- 字符集为utf8mb4时，一个字符占用四个字节
- 字符集为utf8时，一个字符占用三个字节
- 字符集为gbk时，一个字符占用两个字节
- 字符集为ascii时，一个字符占用一个字节
单字段情况
创建一张表test，只有一个VARCHAR(N)类型的数据列，N取 65535，且表的字符集选为ascii，行格式为紧凑型的COMPACT
按理来说，字符集为ASCII，一个字符占用一个字节，VARCHAR(65535)刚好是足够的，能否顺利创建？如下：
提示storage overhead，创建失败了
分析情况： 当存储VARCHAR(N)类型的数据时，实际上是要分三部分存储，如下：
一、真实数据占用的字节数列表；如果变长字段允许存储的最大字节数小于255，值长度就用一个字节表示；如果是大于255，就用两个字节表示
二、仅当字段允许为NULL时，才会使用1个字节来存储NULL值列表（如果表中都是非NULL字段，就不需要NULL值列表）
三、存储的真实数据；真实数据占用的字节不能超过：65535 - 真实数据占用的字节数列表 - NULL值字段列表
将该情况套入上面的案例，我们可知：
- 字段类型为VARCHAR(65535)，因此会用2个字节来表示真实数据占用的字节数列表
- 字段“name”是允许为NULL的，因此需要1个字节来存储NULL值列表
- 结合在一起，真实数据占用的字节不能超过 65535 - 2 - 1 = 65532
为了验证我们的计算，将N改为65533，重新执行：
果不其然，创建失败了。将N改为65532，再执行一遍：
这次成功了！证明我们的计算是正确的
如果字符集改为utf8，一个字符占用三个字节，那么N就应该等于65532/3 = 21844
多字段情况
创建一张表test，有两个VARCHAR(N)类型的数据列，N分别取255和65278，且表的字符集选为ascii，行格式为紧凑型的 COMPACT，能否成功创建一张表？
ascii编码一个字符占用一个字节，其中 255 + 65278 = 65533 < 65535，但是结果还是失败了！
套用在单字段情况时的存储情况：
- 在多字段案例中，id的N为255，会用1个字节来表示；name字段的N为65278，大于255，会用2个字节来表示；总共占用3个字节
- 在多字段案例中，id和name的类型均不为NULL，因此NULL字段列表可以不需要
- 结合分析，真实数据占用的字节不能超过：65535 - 3 = 65532
我们将name中的N改为65277，如下：
成功建立！ （255 + 65527 + 3 = 65535 ≤ 65535）
行溢出现象
通过上文的分析，我们知道，MySQL的I/O操作的最小单位为页，而一页的大小默认为16K，即16384个字节；而一个允许为NULL的VARCHAR(N)类型的列，最多可存储65532字节。
此时尴尬的事情发生了。有可能一页还存储不了一行数据，发生了行溢出现象
不同的行格式，处理行溢出的方式也不同！
COMPACT处理行溢出
当行格式为COMPACT时，发生行溢出了，处理情况如下：
- 在记录的真实数据处（Page中的User Record），保留该列一部分的数据
- 把剩余的数据放到 “溢出页” 中
- 在真实记录处用20个字节存储指向溢出页的指针
Compressed、Dynamic处理行溢出
当行格式为Compressed or Dynamic时，发生行溢出，处理情况大致和COMPACT类似，不同的是：
- 在记录的真实数据处不会保留该列的真实数据
- 把真实数据全放在“溢出页”中
- 真实数据处只存放指向溢出页的指针
