InnoDB逻辑存储结构
数据页结构
页是InnoDB数据存储的最小单位，页类型为B-tree Node的页存放的就是表中行的实际数据。数据页由7个部分组成：
- File Header
- Page Header
- Infimum和Supremum Record
- User Records
- Free Space
- Page Directory
- File Trailer
File Header
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 | 页最后被修改的日志序列位置LSN |
| FIL_PAGE_TYPE | 2 | InnoDB页的类型，Ox45BF是数据页 |
| FIL_PAGE_FILE_FLUSH_LSN | 8 | 仅在表空间的一个页中定义，代表文件至少被更新到了该LSN值，对于独立表空间，该值为0 |
| FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID | 4 | 该页属于哪个表空间 |
| 名称 | 十六进制 | 描述 |
|---|---|---|
| FIL_PAGE_INDEX | 0x45BF | B-Tree页节点 |
| FIL_PAGE_UNDO_LOG | 0x0002 | undo log页 |
| FIL_PAGE_INODE | 0x0003 | 索引节点 |
| FIL_PAGE_IBUF_FREE_LIST | 0x0004 | Insert buffer空闲列表 |
| FIL_PAGE_TYPE_ALLOCATED | 0x0000 | 最新分配的页 |
| FIL_PAGE_IBUF_BITMAP | 0x0005 | Inset buffer 位图 |
| FIL_PAGE_TYPE_SYS | 0x0006 | 系统页 |
| FIL_PAGE_TYPE_TRX_SYS | 0x0007 | 事务系统数据 |
| FIL_PAGE_TYPE_FSP_HDR | 0x0008 | File Space Header |
| FIL_PAGE_TYPE_XDES | 0x0009 | 扩展描述页 |
| FIL_PAGE_TYPE_BLOB | 0x000A | BLOB页 |
Page Header
Page Header用来记录数据页的状态信息，由14部分组成，共占56个字节，其组成如下：
| 名称 | 大小(字节) | 描述 |
|---|---|---|
| PAGE_N_DIR_SLOTS | 2 | Page Directory中的slot数量 |
| PAGE_HEAP_TOP | 2 | 堆中第一个记录的指针 |
| PAGE_N_HEAP | 2 | 堆中的记录数 |
| PAGE_FREE | 2 | 可重用空间的指针 |
| 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 | 页在索引树的位置，0x00表示叶子节点 |
| PAGE_INDEX_ID | 8 | 索引ID |
| PAGE_BTR_SEG_LEAF | 10 | B-Tree非叶节点所在段的segment header，仅在root页定义 |
| PAGE_BTR_SEG_TOP | 10 | B-Tree页节点所在段的segment header，仅在root页定义 |
Infimum和Supremum Record
在InnoDB中，每个页都存在两个虚拟行记录，用来限定记录的边界。Infimum记录是比该页中任何主键值还要小的值，Supremum值比任何可能大的值还要大的值，在页创建时被建立，并且任何情况都不会被删除，占据着heap number中的0和1，因此我们插入数据时的heap number都是从2开始
User Record和Free Space
User Record即实际存储行记录的内容；Free Space即空闲空间，链表数据结构，在数据被删除时，该空间会加入到空闲列表中。
Page Directory
Page Diectory存放了记录的相对位置，可以称之为slot，不同的时InnoDB是一个稀疏目录，即一个slot中包含多个记录，Infimum的n_owned总是1，Supremum的n_owned取值范围为[1,8]，用户记录的取值范围为[4,8]。当记录被插入或删除时需要堆槽进行分裂和平衡的操作。
通过B-Tree本身并不能查找到具体的一条记录，只能找到记录所在的页，数据库把页加载到内存中，再通过Page Directory进行二叉查找。
File Trailer
为了检测页是否完整写入磁盘，InnoDB设置了File Trailer。File Trailer只有FIL_PAGE_END_LSN，占用8个字节。前4字节表示页的checksum值，后4字节和File Header的FIL_PAGE_LSN相同。将两个值与File Header中的FIL_PAGE_SPACE_OR_CHECKSUM和FIL_PAGE_LSN相比较，通过checksum函数判断是否一致，以此来确保页的完整性。默认配置下，InnoDB每次从磁盘读取一个页就会检测该页的完整性，是否发生Corrupt，存在一定的开销。
通过innblock工具，我们能看到第四个页是数据页，再通过hexdump来分析表空间文件得到16进制文件，数据页从0xc000(16K*3=0xc000)开始
[root@t-luhx02-v-szzb data]# /media/mysql/innblock ./test/test.ibd scan 16 |
File Header部分解析如下：
- 1b 3b 69 63：数据页的checksum值
- 00 00 00 03：页的偏移量，从0开始
- ff ff ff ff：前一个页，因为只有一个页，所以为0xfffffff
- ff ff ff ff：后一个页，因为只有一个页，所以为0xfffffff
- 00 00 00 00 22 e6 ba 8d：页的LSN
- 45 bf：页类型，0x45BF表示数据页
- 00 00 00 00 00 00 00 00：独立表空间为0
- 00 00 00 3f：3f转换为10进制也就是63，表示表空间文件的space id
Page Header部分解析如下：
- Page_N_DIR_SLOTS = 0x0002 表示Page Directory有2个槽，每个槽2个字节
- PAGE_HEAP_TOP = 0x00f4 表示空闲空间开始未知的偏移量，即0xc000+0x00f4=0xc0f4处开始
- PAGE_N_HEAP = 0x8005
- PAGE_FREE = 0x0000
- PAGE_GARBAGE = 0x0000
- PAGE_LAST_INSERT = 0x00dc
- PAGE_DIRECTION = 0x0002
- PAGE_N_DIRECTION = 0x0002
- PAGE_N_RECS = 0x0003
- PAGE_MAX_TRA_ID = 0x0000000000000000
- PAGE_LEVEL = 0x0000
- PAGE_INDEX_ID = 0x0000000000000060
- PAGE_BTR_SEG_LEAF = 0x0000003f0000000200f2
- PAGE_BTR_SEG_TOP = 0x0000003f000000020032
Infimum部分解析如下：
- 01 00 02 00 1f：recorder header，最后两位表示下一行记录位置的偏移量，即0xc063+0x001f=0xc082u，就能定位到第一条行记录
- 69 6e 66 69 6d 75 6d 00：只有一个Infimum列的伪列记录
Supremum部分解析如下：
- 04 00 0b 00 00：recorder header
- 73 75 70 72 65 6d 75 6d：只有一个Supremum列的伪列
通过recoder header的最后两个字节的下一行记录偏移量就可以得到该页中所有行的记录，再通过Page header的PAGE_PREV和PAGE_NEXT就可以知道上个页和下个页的位置，这样就能读到整张表所有的记录数据。
前面说了Page Directory有2个槽，每个槽2个字节，可以定位0000fff4到0000ff7
0000fff0 00 00 00 00 00 70 00 63 1b 3b 69 63 22 e6 ba 8d |.....p.c.;ic"...| |
需要注意的是，Page Directory是逆序存放的，因此可以看到00 63是最初行的相对位置，即0xc063，00 70是最后一行的相对位置，即0xc070，我们发现就是前面分析的Infimum和Supremum的recorder header的值。前面已经提到了InnoDB的slot是稀疏的，故还需要通过recorder header的n_owned进一步的判断，例如要查询a为b的记录，通过二叉树查找Page Directory的槽。
File Trailer部分解析如下：
0000fff0 00 00 00 00 00 70 00 63 1b 3b 69 63 22 e6 ba 8d |.....p.c.;ic"...| |
- 1b 3b 69 63：checksum值，通过与File Header中的checksum进行比较
- 22 e6 ba 8d：该值与File Header中的LSN后4个值相等
行记录格式
InnoDB存储引擎记录是以行存储的，提供了Compact、Redundant、Compressed和Dynamic四种格式来存放行记录数据。其中Compact和Redundant称为Antelope文件格式，Compressed和Dynamic称为Barracuda文件格式。5.7后默认为Barracuda文件格式，Barracuda包含了Antelope中的行格式，通过参数innodb_file_format控制，我们也可以为表单独指定ROW_FORMAT
Compact
| 变长字段长度列表 | NULL标志位 | 记录头信息 | 列数据 | 列数据 | ….. |
|---|
在compact格式中，将所有变长字段的真实数据长度都存放在变长字段长度列表，各变长字段占用的字节数按列的逆序存放。变长字段列表中，当列的数据字节比较小时，一个字节就可以用于表示；如果数据字节较多，就需要两个字节表示，变长字段的长度最大不可以超过2字节，这是因为VARCHAR类型的最大长度为65535。其具体的计算规则如下：
- 字符集对应的字节数记为W，例如UTF8为3个字节，gbk为2个字节
- 变长字段定义的最大字符数几位N
- 实际数据占用的字节数记为R
- N * W < 255，则只需要一个字节
- N * W > 255时，如果R<=127则需要一个字节，如果R>127则需要两个字节
为NULL的字段不记录变长字段列表
如果表中没有允许为NULL的列，NULL值列表就不存在了，每个允许为NULL的列对应一个二进制位，如果列为NULL值，记为1，非NULL的则记为0，二进制位依旧按照逆序排列，当记录大小不足一个字节时，在左侧加0补充
然后就是记录头信息，固定为40为位，占5字节
| 名称 | 大小 | 描述 |
|---|---|---|
| () | 1B | 未知 |
| () | 1B | 未知 |
| deleted_flag | 1B | 该行是否已被删除 |
| min_rec_flag | 1B | B+树的每层非叶子节点中的最小记录，标记为1 |
| n_owned | 4B | 该记录拥有的记录数 |
| heap_no | 13B | 索引堆中该条记录的排序记录，即插入顺序 |
| record_type | 3B | 记录类型。000表示普通，001表示B+树节点指针，010表示Infimumi(最小记录)，011表示Supremem(最大记录)，1xx表示保留 |
| next_record | 16B | 页中下一条记录的相对位置 |
最后就是实际存储每个列的数据，每行除了用户显示定义的列之外，还有transaction_id(事务ID)和roll_pointer(回滚指针)，大小分别为6字节和7字节，若表上没有定义主键，还将增加一个6字节的rowid列。
innodb表主键的策略是优先选择自定义主键，如果没有定义则选取一个唯一键作为主键，如果没有唯一键则利用隐藏列row_id作为主键
现在我们根据下面的表，来具体看看Compact格式的具体内容。我们可以通过hexdump来获取表空间文件信息
mysql> show create table test; |
- 04 0a 02 01：为变长字段长度列表并逆序，我们这里A、B、D都定义为varchar变长字段
- 00：NULL标志位，第一行没有NULL值
- 00 00 10 00 2e：Record Header，其中0x2e代表下一记录的偏移量，当前记录加上偏移量就是下条记录的起始位置
- 00 00 00 00 02 0f：自动创建的rowid
- 00 00 00 00 14 60：事务ID
- be 00 00 01 91 01 10：Roll Pointer
- 61：a列的数据，61对应a的ascii值的16进制
- 62 62：b列的数据，62对应的b的ascii值的16进制
- 63 63 63 20 20 20 20 20 20 20：c列的数据，62对应c的ascii值的16进制，定长字段不足时用0x20填充
- 64 64 64 64：d列的数据，64对应d的ascii值的16进制
在compact格式下，对于CHAR(N)类型的列，当列采用定长字符集时，该列占用的字节不会加到变长字段列表中，例如ascii字符集；如果采用变长字符集时，该列占用的字节数会记录到变长字段列表中，例如utf-8为1-3字节
Redundant
redundant是MySQL5.0之前使用的行格式
| 字段长度偏移列表 | 记录头信息 | 列数据 | 列数据 | …. |
|---|
Redundant行记录格式的头部是一个字段长度偏移列表，将记录所有列的长度信息都逆序存储到字段长度偏移列表，采用相邻数值的差值来计算各个列的长度。
不同于Compact行记录格式，Redundant的记录头占用48位，占6字节。
| 名称 | 大小 | 描述 |
|---|---|---|
| () | 1B | 未知 |
| () | 1B | 未知 |
| deleted_flag | 1B | 该行是否已被删除 |
| min_rec_flag | 1B | 如果该行位最小的记录，标记为1 |
| n_owned | 4B | 该记录拥有的记录数 |
| heap_no | 13B | 索引堆中该条记录的索引号，即插入顺序 |
| n_fields | 10B | 记录中列的数量 |
| 1byte_offs_flag | 1B | 偏移列表是1字节还是2字节 |
| next_record | 16B | 页中下一条记录的相对位置 |
1byte_offs_flag用于表示每个列的偏移量是使用1个字节还是2个字节，值为1时，表示1个字节存储，值为0时，表示使用2个字节存储。记录真实数据占用的字节不大于127(0x7F)时，1byte_offs_flag为1，当记录真实数据大于127，小于32767字节时，1byte_offs_flag为0。
由于redundant中并没有NULL值列表，因此将列对应的偏移量值第一位作为列是否为空的依据，如果第一位为1则为NULL，否则就不是NULL。因此1byte_offs_flag的计算方式是127(01111111)作为中间值，就是因为第一位用于标记NULL了。对于为NULL的列的类型是否为定长类型决定了NULL值的存储方式，如果是定长类型，字段数据通过0x00填充，如果为变长类型，则不占用任何数据存储空间
行溢出
MySQL VARCHAR类型可以存放65535个字节，但是实际上测试NOT NULL的情况下最大为65533，否则只能到65532
mysql> create table a(a varchar(65533)) charset=latin1 engine=innodb; |
如果没有设置SQL_MODE为严格模式，65535也能创建成功，只是通过show warning查看告警时会发现自动转换为text类型了。
最大长度也受字符集影响，例如utf-8下一个字符最大为3个字节，最大长度就不能超过21845。另外，该长度限制是针对一行记录所有字段的总和，如果有3个3000长度的varchar类型也是会存在报错的。
在针对大数据的情况下，对于Antelope文件格式，只会在数据页保留前768个字节的前缀数据，之后是20字节的偏移量，指向行溢出页，也就是Uncompressed BLOB Page；对于Barracuda，数据页只存放20个字节的指针，实际的数据都存放在off page中。
)