从MySQL InnoDB物理文件格式深入理解索引

1. InnoDB物理文件的基本结构

InnoDB的物理文件有很多种，包括：

1）系统表空间（system tablespace）。文件以ibdata1、ibdata2等命名，包括元数据数据字典（表、列、索引等）、double write buffer、插入缓冲索引页（change buffer）、系统事务信息（sys_trx）、默认包含undo回滚段（rollback segment）。

2）用户表空间。innodb_file_per_table=true时，一个表对应一个独立的文件，文件以db_name/table_name.ibd命名。行存储在这类文件。另外还有5.7之后引入General Tablespace，可以将多个表放到同一个文件里面。

3）redo log。文件以ib_logfile0、ib_logfile1命名，滚动写入。主要满足ACID特性中的Durablity特性，保证数据的可靠性，同时把随机写变为内存写加文件顺序写，提高了 MySQL 的写吞吐。

4）另外还可能存在临时表空间文件、undo独立表空间等。

MySQL一次IO的最小单位是页（page），也可以理解为一次原子操作都是以page为单位的，默认大小16k。刚刚列出的所有物理文件结构上都是以Page构成的，只是page内部的结构不同。

每个page包括最前面的38个字节的FilHeader，和结尾的8个字节的FilTrailer组成。

文章前一部分的图片直接引用 JCole的博客 ，中后方的图片大部分原创，用于更好的理解。

segment和extent是InnoDB内部用于分配管理页的逻辑结构，用于分配与回收页，对于写入数据的性能至关重要。

但这张图有所局限性，可能会产生误解：

1）图中是系统表空间，因此存在rollback segment，独立表空间则没有。

2）leaf node segment实际是InnoDB的inode概念，一个segment可能包含最多32个碎片page、0个extent（用于小表优化），或者是非常多的extent，我猜测作者图中画了4个extent是在描述表超过32MB大小的时候一次申请4个extent。

3）一个extent在默认16k的page大小下，由64个page组成，page大小由UNIV_PAGE_SIZE定义，所以extent不一定由64个page组成。

如果你觉得这几点不明白，那么坚持往下读。

FSP_HDR页都是page 0，XDES页一般出现在page 16384, 32768等固定的位置。一个FSP_HDR或者XDES页大小同样是16K，容量限制所能管理的extent必定是有限的，一般情况下，每个extent都有一个占40字节的XDES entry描述维护，因此1个FSP_HDR页最多管理256个extent（也就是256M，16384个page）。那么随着表空间文件越来越大，就需要更多的XDES页。

XDES entry存储所管理的extent状态：

1）FREE（空）

2）FREE_FRAG（至少一个被占用）

3）FULL_FRAG（满）

4）归某个segment管理的信息

XDES entry还存储了每个extent内部page是否free（有空间）信息（用bitmap表示）。XDES entry组成了一个双向链表，同一种extent状态的收尾连在一起，便于管理。

FSP_HDR和XDES的唯一区别，FSP Header只有在page 0 FSP_HDR中有值。

而FSP Header里面最重要的信息就是四个链表头尾数据（FLST_BASE_NODE结构，FLST意思是first and last），FLST_BASE_NODE如下。

id,VALUE
100,a
199,b
200,c
299,d
300,e
400,f
500,g
550,h
600,i
650,j
...

微观上把每个页节点内部展开成由infimum和supermum连接起来的有序单链表，结构如下。每层的页通过Fil Header相互连接。

这个案例图实际上想呼应丁奇老师 《MySQL实战45讲 》里的第五讲索引里面的图。

这张图是一张局部图，非叶子节点每个记录背后是node pointer，指向child page number，图中非叶子节点上有100，丁奇老师的讲解和绝大部分外部的资料实际都都是画了B+树上的一部分，丁奇老师图中300前面的指针实际就是300这个记录的node pointer，InnoDB的B+树会存储最小的一条记录，而不仅仅是一个指针。

6.4 Row Format

下面介绍具体每一行的结构。

InnoDB有如下4种row format，下图来自 MySQL官方文档 。

row format可通过innodb_default_row_format参数指定，也可以在建表的时候指定。

CREATE TABLE tab (
   id INT,
   str VARCHAR(50)
) ENGINE=InnoDB ROW_FORMAT=DYNAMIC;

REDUNDANT是比较老的格式，流行的版本中5.6默认是COMPACT，COMPACT比REDUNDANT要更节省空间，大概在20%左右。5.7版本DYNAMIC是默认格式，DYNAMIC在变长存储上做了更大的空间优化，对于VARBINARY, VARCHAR, BLOB和TEXT类型更友好，下面会更详细展开。COMPRESSED是压缩页。

下面的介绍都是基于COMPACT及其之后格式的。

row的格式在上面图中简单介绍过，由可选的两个标识+record header+body组成，具体如下。

1）Nullable field bitmap：可选标识，表明哪些列是NULL，如果没有nullable字段，就不存在。很多文章都没说清楚这部分，画个图就明白了，一个字节能表示8个nullable字段，超过8个字段就扩充到低字节。如下图所示，18个字段，9个可为空，如果其中某3个实际为空，则两个字节存储如图。

2）Variable field lengths：可选标识，变长字段长度，如果没有变长字段，就不存在。每个变长字段都用1-2个字节表示长度，根据列定义顺序逆序存放，其算法很多书里都提过，但是都有些省略，具体解析过程可以参考rem0rec.cc。如果小于等于127，则1个字节；大于127，高字节最低的1位表示是否有overflow page存储，剩余7位和低字节的8位，按照小尾端encoding组成变长长度。

3）record header：固定5个字节长度。

Info Flags：1个字节。低4位表示是否min_rec或者deleted。高4位表示num of records owned，与上面提到的page directory呼应，如果被page directory slot指向，则有值。

2个大尾端字节：低三位表示类型， 包括普通记录REC_STATUS_ORDINARY=0，非叶子节点记录REC_STATUS_NODE_PTR=1，起始虚拟记录REC_STATUS_INFIMUM=2，终点虚拟记录REC_STATUS_SUPREMUM=3。高5位表示heap no，即顺序位置。

2字节next record offset： 直接定位到下一个record的数据部分，也就是主键偏移量，而不是record header。

可以看出如果表结构没有变长字段，没有nullable字段，则不会存在冗余信息。5个字节长度的record header是必须有的，上面提到的infimum和supremum也是一种特殊的row，只不多对用户不可见。

4）索引：序列化后存储于此，例如int类型索引主键就占用4个字节。

对于聚簇索引的叶子节点，存储行。

对于二级索引的叶子节点，存储行的主键值。

对于聚簇索引和二级索引的非叶子节点，存储child page最小的key。

上面提到的infimum和supremum中就只存字符串在行数据里。

5）6字节事务ID和7字节回滚指针：

这两个值用来支持MVCC机制，事务ID是实现事务隔离级别的基础，而通过回滚指针指向undo log，可实现非锁定一致性读。

7）非主键列的数据：

对于聚簇索引的叶子节点，是按照表结构定义排列的columns，每种column类型都有自己的encoding方法。

对于二级索引的叶子节点，是行的主键值。

对于聚簇索引和二级索引的非叶子节点，是child page number。

每一列的解析在DataTypeHandler.cc源码里可以找到，有encoding和decoding的方法。比如int比较简单4个字节，对于varchar、text需要按照列或者表的charset encoding出来，对于varbinary、blob就是裸的二进制数据，对于datatime等时间相关的有相应的机制去做序列化。

对于变长字段，MySQL有一套规则可以存储在overflow page中，这个page是BLOB类型，也就是不在行所在的page中存储，这样可以优化空间，在索引页中存储最有价值的行信息，而不是在B+ tree中节点充斥着很大的列，进一步提高索引的存储效率；另外还支持了存储大于一页16k大小的数据。

一般情况下，对于变长字段，如果大于768字节，则启用off-page策略，索引页存储前768字节，然后外加20字节pointer信息包含space id，overflow page number，offset和存放在overflow page的字节数。对于DYNAMIC则做的更加极致，即可以做fully off-page，只存20字节的pointer信息，也可以对于小数据<=40 bytes 做inline，不off-page。overflow page是一个单链表，每个BLOB page都存储了一部分数据。在MySQL 8.0之后对于这个结构又做了进一步优化，可以随机访问大列的一部分，为此引入了LOB类型，感兴趣可以 参考链接 。

7. 总结

深入理解MySQL InnoDB表空间物理文件格式，对于更好的认识索引，有很大帮助。本文从独立表空间入手，展开介绍了extent、segment、inode等页管理和分配的概念，用实际的案例阐述了InnoDB B+树中每个节点的索引页结构，如何做点查和范围查询，索引页的内部结构，以及每个行的组成，查阅了不少资料以及MySQL源代码， alibaba/innodb-java-reader 这个开源项目，可以帮助读者更好的理解。

转载时请注明转自neoremind.com。