时隔三天， 开始第二部分的总结了， 第二部分主要是介绍 InnoDB 的数据存储结构， 主要对应“MySQL 是怎样运行的：从根儿上理解 MySQL”上面的第五章和第六章
首先需要知道一点， 数据在内存中的读写速度比磁盘上的读写速度快上好几个数量级， 所以当从表中获取记录时， 将磁盘上的数据读取到内存中， 当写入或者更新时，再将内存中的内容刷新到磁盘上。 InnoDB 将数据划分为若干个页， 以页作为磁盘和内存之间交互的基本单位， 页的大小一般为16KB。
InnoDB 行格式
InnoDB 我们都知道是以一条记录为单位向表中插入数据， 这个记录在磁盘上的存储方式称为 行格式 或者记录格式
行格式目前有4种：
- Compact
- Redundant
- Dynamic
- Compressed
Compact 格式
首先简单看一下默认的格式示意图
变长字段长度列表
并不是所有记录都有这个 变长字段长度列表 部分，比方说表中所有的列都不是变长的数据类型的话，这一部分就不需要有。
变长字段存储需要记录2部分内容：真正的数据内容和占用的字节数。
规则：把所有变长字段的真实数据占用的字节长度都存放在记录的开头部位，从而形成一个变长字段长度列表，各变长字段数据占用的字节数按照列的顺序逆序存放
注意变长字段的出现的几种可能：
- 字符集是定长的例如
ascii字符集， 但是定义了例如VARCHAR(M)的变长类型 - 字符集是变长的例如
utf8字符集， 但是定义了例如VARCHAR(M)的变长类型 - 字符集是变长的例如
utf8字符集， 但是定义了例如CHAR(M)的定长类型，这种情况，数据字节长度存储的范围为10M~30M,默认占用10M个字节，当更新小于等于10M时不用重新分配新的空间， 可以在该记录出直接更新， 如果大于10M会重新分配一个新的记录空间，导致原有的记录空间成为所谓的碎片。
因为统计的内容长度(十六进制)可能是1个字节(8位，内容长度255个字节)或者2个字节(内容长度大于255个字节)， 在读取的时候需要判断当前读取的字节结果是1个单独的字段长度还是半个字节长度，所以InnoDB在统计字符串有属于自己的规则
- W: 表示一个字符最多需要使用的字节数， 例如默认的
utf8的W是3，gbk字符集就是2 - M: 在定义变长类型例如
VARCHAR(M)来说，M表示最多存储的字符数 - 所以这个类型允许存储的最大字节数就是 M*W
- L: 实际存储的字符串字节数
具体规则如下：
- 如果M×W <= 255，那么使用1个字节来表示真正字符串占用的字节数。
- 如果M×W > 255，则分为两种情况：
- 如果L <= 127，则用1个字节来表示真正字符串占用的字节数。(1个字节首位为0)
- 如果L > 127，则用2个字节来表示真正字符串占用的字节数。(手动设置2个字节中第一个字节首位为1)
补充一下：1个页一般默认16KB，如果1个L特别大，一个页无法保存， 会把一部分数据放到溢出页，在变长字段长度列表处只存储留在本页面中的长度，所以使用两个字节也可以存放下来。。这一块我想表达的意思是，2个字节表示的最大值实际上存储不进1个页中， 所以首位可以手动设置为1。
根据规则回头验证一下， 读取一个位置实际内容长度时，如果可变字段允许存储的最大字节数小于255字节，读取1个字节；如果大于255字节，第一个字节首位是0(即小于127)，读取1个字节， 反之读2个字节。
变长字段长度列表中只存储值为 非NULL 的列内容占用的长度，值为 NULL 的列的长度是不储存的
NULL值列表
为了减少存储空间， 会统计所有空值的列。
- 首先统计表中允许空值的列
- 用1表示此列为空， 0表示非空。(二进制位按照列的顺序逆序排列)
- 规定NULL值列表必须用整数个字节的位表示，不足整个字节， 高位补0
记录头信息
它是由固定的5个字节组成。5个字节也就是40个二进制位
| 名称 | 大小（单位：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 | 表示下一条记录的相对位置 |
记录的真实数据
Mysql为了处理自己业务方便以及统计的需要， 添加了一些额外的列又称隐藏列。
| 列名 | 是否必须 | 占用空间 | 描述 |
|---|---|---|---|
| row_id(DB_ROW_ID) | 否 | 6字节 | 行ID，唯一标识一条记录 |
| transaction_id(DB_TRX_ID) | 是 | 6字节 | 事务ID |
| roll_pointer(DB_ROLL_PTR) | 是 | 7字节 | 回滚指针 |
在用户没有设置主键或者Unique键的情况下会添加此列
存储真实数据时， 例如CHAR(10)，字符集选择ascii, 共占有10个字节， 如果输入少于10个字符， 剩余位置会用空格补满，仍然占用10个字节位置。
Redundant 格式
首先简单看一下默认的格式示意图
相比与Compact格式， 在记录额外信息部分有 变长字段长度列表+NULL值列表+记录头信息 变成 字段长度偏移列表+记录头信息
Redundant的记录的真实数据
它与Compact的格式是一样的，也包括DB_ROW_ID,DB_TRX_ID,DB_ROLL_PTR三个额外的隐藏列信息
字段长度偏移列表
它需要将一条记录中所有列的长度信息都按照逆序存储到字段长度偏移列表， 但是它不是直接存储列的长度信息， 而是计算偏移， 两个相邻数值的差值来统计长度信息。
在Compact行格式中提到，计算变长字段长度CHAR(M)，根据字符集是定长或者变长字符集有选择的加入变长字段长度列表中，
而Redundant行格式， 在计算偏移时， 不区分字符集类型， 直接用一个字符需要的最多字节数和M的乘积作为占用的真实数据空间， 因此不会产生碎片。
字段长度偏移列表统计的长度信息是包括隐藏列信息的。
可以这样理解偏移长度,假设一条存储的记录如下：
25 24 1A 17 13 0C 06
| DB_ROW_ID | DB_TRX_ID | DB_ROLL_PTR | 列1 | 列2 | 列3 | 列4 | |
|---|---|---|---|---|---|---|---|
| 正常顺序的偏移长度 | 06 | 0C | 13 | 17 | 1A | 24 | 25 |
| 每一列列的真实长度 | 6 | 6 | 7 | 4 | 3 | 10 | 1 |
Redundant的记录头信息
相对与Compact的5个字节， Redundant它是由固定的6个字节组成。6个字节也就是48个二进制位
| 名称 | 大小（单位：bit） | 描述 |
|---|---|---|
| 预留位1 | 1 | 没有使用 |
| 预留位2 | 1 | 没有使用 |
| delete_mask | 1 | 标记该记录是否被删除 |
| min_rec_mask | 1 | B+树的每层非叶子节点中的最小记录都会添加该标记 |
| n_owned | 4 | 表示当前记录拥有的记录数 |
| heap_no | 13 | 表示当前记录在记录堆的位置信息 |
| n_field | 10 | 表示记录中列的数量 |
| 1byte_offs_flag | 1 | 标记字段长度偏移列表中每个列对应的偏移量是使用1字节还是2字节表示的 |
| next_record | 16 | 表示下一条记录的相对位置 |
相对于Compact行格式，
- 少了
record_type字段 - 多了
n_field和1byte_offs_flag2个字段
1byte_offs_flag 字段解析
根据Redundant行格式记录的列真实数据占用的总大小来判断是使用1个字节表示还是2个字节表示
- 当记录的真实数据占用的字节数不大于127（十六进制0x7F，二进制01111111）时，每个列对应的偏移量占用1个字节。
- 当记录的真实数据占用的字节数大于127，但不大于32767（十六进制0x7FFF，二进制0111111111111111）时，每个列对应的偏移量占用2个字节
- 当记录的真实数据大于32767时，本页中只保留前768个字节和20个字节的溢出页面地址（当然这20个字节中还记录了一些别的信息）。因为字段长度偏移列表处只需要记录每个列在本页面中的偏移就好了，所以每个列使用2个字节来存储偏移量就够了。
只要整条记录的真实数据占用的存储空间大小大于127，即使第一个列的值占用存储空间小于127，需要使用2个字节来表示该列对应的偏移量，所以这种行格式已经有些过时。
NULL处理
在1byte_offs_flag中提到数据不大于127，或者在127-32767字节数之间，或者大于32767(本页只保存768个字节和28个字节的溢出页地址)， 可以看到首位偏移值的首位都是0，这样的设计是因为， 列对应的偏移量值的第一个比特位作为是否为NULL的依据,该比特位也可以被称之为NULL比特位。
也就是说在解析一条记录的某个列时，首先看一下该列对应的偏移量的NULL比特位是不是为1，如果为1，那么该列的值就是NULL，否则不是NULL。 首位是不参与差值计算。
假设一条数据如下图
| 列1 | 列2 | 列3 | 列4 | |
|---|---|---|---|---|
| 列类型 | VARCHAR(10) | VARCHAR(10) NOT NULL | CHAR(10) | VARCHAR(10) |
| 列数据 | eeee | fff | NULL | NULL |
此时偏移长度的记录如下：
A4 A4 1A 17 13 0C 06
| DB_ROW_ID | DB_TRX_ID | DB_ROLL_PTR | 列1 | 列2 | 列3 | 列4 | |
|---|---|---|---|---|---|---|---|
| 正常顺序的偏移长度 | 06 | 0C | 13 | 17 | 1A | A4 | A4 |
| 换算成二进制 | 00000110 | 00001100 | 00010011 | 00010111 | 00011010 | 10100100 | 10100100 |
| 换算成十进制(移除首位) | 6 | 12 | 19 | 23 | 26 | 36 | 36 |
| 每一列列的真实长度 | 6 | 6 | 7 | 4 | 3 | 10 | 0 |
行溢出数据
首先需要知道一点，在真实的存储过程中，存储一个VARCHAR(M)(M代表字符， 根据选用的字符集， 决定 M 个字符需要的总的总的字节数)类型的列，需要保存的额外数据：
- 真实数据
- NULL值的标识， 如果该列有NOT NULL属性， 则没有这部分存储空间
- 真实数据占用的字节长度信息
以Compact为例，如果只有1列可以为空的表
每条记录需要额外27个字节
- 2个字节用于存储真实数据的长度
- 1个字节用于存储列是否是NULL值
- 5个字节大小的头信息
- 6个字节的row_id列
- 6个字节的transaction_id列
- 7个字节的roll_pointer列
因为1个页一般为16KB（16384个字节），一个VARCHAR(M),最多存储65532个字节， 导致一个页放不下一条记录。
对于Compact和Reduntant行格式来说，如果某一列中的数据非常多的话，在本记录的真实数据处只会存储该列的前768个字节的数据和一个20字节指向其他页的地址，然后把剩下的数据存放到其他页中，这个过程也叫做行溢出，存储超出768字节的那些页面也被称为溢出页。
Dynamic和Compressed 格式
在存储形式上和Compact差不多， 主要区别在于如何处理行溢出， 它们不会在记录的真实数据处存储字段真实数据的前768个字节，而是把所有的字节都存储到其他页面中，只在记录的真实数据处存储其他页面的地址
Compressed行格式和Dynamic不同的一点是，Compressed行格式会采用压缩算法对页面进行压缩，以节省空间。
InnoDB数据页结构
页是 InnoDB 管理存储空间的基本单位， 一个页的大小一般是16KB。
这一部分主要介绍一种页的类型–索引(INDEX)页。
| 名称 | 中文名 | 占用空间大小 | 简单描述 |
|---|---|---|---|
| File Header | 文件头部 | 38字节 | 页的一些通用信息 |
| Page Header | 页面头部 | 56字节 | 数据页专有的一些信息 |
| Infimum + Supremum | 最小记录和最大记录 | 26字节 | 两个虚拟的行记录 |
| User Records | 用户记录 | 不确定 | 实际存储的行记录内容 |
| Free Space | 空闲空间 | 不确定 | 页中尚未使用的空间 |
| Page Directory | 页面目录 | 不确定 | 页中的某些记录的相对位置 |
| File Trailer | 文件尾部 | 8字节 | 校验页是否完整 |
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字节 | 页属于哪个表空间 |
FIL_PAGE_SPACE_OR_CHKSUM
这个代表当前页面的校验和（checksum）。对于一个很长很长的字节串来说，我们会通过某种算法来计算一个比较短的值来代表这个很长的字节串，这个比较短的值就称为校验和
FIL_PAGE_OFFSET
每一个页都有一个单独的页号，就跟你的身份证号码一样，InnoDB通过页号来可以唯一定位一个页。
FIL_PAGE_TYPE(页的类型)
| 类型名称 | 十六进制 | 描述 |
|---|---|---|
| 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 | 索引页，也就是我们所说的数据页 |
FIL_PAGE_PREV和FIL_PAGE_NEXT
所有的页 是以双链表的形式串联起来，需要注意的是，并不是所有类型的页都有上一个和下一个页的属性
Page Header(页面头部)
一个数据页中存储的记录的状态信息,占有固定的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
两个虚拟的伪记录，分别表示页中的最小和最大记录，占固定的26个字节。这一部分会在 User Record 中详细介绍
User Records
真实存储我们插入的记录的部分，大小不固定。它每插入一条数据， 会从 Free Space 中申请一个记录大小的空间划分过来，当 Free Space 没有空间时， 就需要申请一个新的 页。
插入数据时， 假设使用 Compact行格式， 所有的记录在 User Records 中靠 记录头信息 串联起来
Infimum 和 Supremum 都是由5个字节的 记录头信息 和8个字节大小的固定部分组成
Infimum的记录头信息中的heap_no为0，record_type为2 (最小记录)Supremum的记录头信息中的heap_no为1，record_type为3 (最大记录)
后面插入的记录 heap_no 从2开始， record_type 为 0 (普通记录)
记录头信息中的 next_record
它表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量。比方说第一条记录的next_record值为32，意味着从第一条记录的真实数据的地址处向后找32个字节便是下一条记录的真实数据。
下一条记录 指得并不是按照我们插入顺序的下一条记录，而是 按照主键值由小到大的顺序的下一条记录。
- 规定
Infimum记录（也就是最小记录） 的下一条记录就是本页中主键值最小的用户记录 - 而本页中主键值最大的用户记录的下一条记录就是
Supremum记录（也就是最大记录）
其实可以这样理解， User Records中的数据按照主键从小到大形成单链表， Infimum 记录是表头， Supremum 记录是最后一个节点
注意： next_record 指针指向的是记录头信息和真实数据之间的位置， 向左读取就是记录头信息， 向右读取就是真实数据。
变长字段长度列表和NULL列表中信息是逆序， 这样可以使记录中位置靠前的字段和它们对应的字段长度信息在内存中的距离更近，可能会提高高速缓存的命中率。？？？
Free Space
页中尚未使用的部分，大小不确定。
Page Directory(页目录)
- 将所有正常的记录（包括最大和最小记录，不包括标记为已删除的记录）划分为几个组。
- 每个组的最后一条记录（也就是组内最大的那条记录）的头信息中的n_owned属性表示该记录拥有多少条记录，也就是该组内共有几条记录。
- 将每个组的最后一条记录的地址偏移量单独提取出来按顺序存储到靠近页的尾部的地方，这个地方就是所谓的Page Directory，也就是页目录（此时应该返回头看看页面各个部分的图）。页面目录中的这些地址偏移量被称为槽（英文名：Slot），所以这个页面目录就是由槽组成的。
记录头信息中 n_owned 只有槽统计分组中的数量。 而分组中的记录条数是有规定的：对于最小记录所在的分组只能有 1 条记录，最大记录所在的分组拥有的记录条数只能在 1~8 条之间，剩下的分组中记录的条数范围只能在是 4~8 条之间
页中的某些记录相对位置，也就是各个槽在页面中的地址偏移量，大小不固定，插入的记录越多，这个部分占用的空间越多。
File Trailer
这部分由8个字节组成，主要为保证从内存中同步到磁盘的页的完整性， 需要检测一个页是否完整。
- 前4个字节代表页的校验和
和File Header中的校验和相对应。当头部的校验和File Trailer中的校验和不一致，则意味着同步中间出了错。 - 后4个字节代表页面被最后修改时对应的日志序列位置（LSN）
在页的首部和尾部都会存储页中数据的校验和和页面最后修改时对应的LSN值，如果首部和尾部的校验和和LSN值校验不成功的话，就说明同步过程出现了问题。
总结
各个 数据页 可以组成一个 双向链表，而每个 数据页 中的记录会按照主键值从小到大的顺序组成一个 单向链表，每个 数据页 都会为存储在它里边儿的记录生成一个 页目录，在通过主键查找某条记录的时候可以在 页目录 中使用 二分法 快速定位到对应的 槽，然后再遍历该 槽 对应分组中的记录即可快速找到指定的记录