（转载）从MySQL InnoDB 物理文件格式深入理解索引

1 年前

小盒子

声明： 本文转载自 http:// neoremind.com

InnoDB物理文件的基本结构

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

系统表空间（system tablespace）。文件以 ibdata1、ibdata2 等命名，包括元数据数据字典（表、列、索引等）、double write buffer、插入缓冲索引页（change buffer）、系统事务信息（sys_trx）、默认包含 undo 回滚段（rollback segment）。
用户表空间。innodb_file_per_table=true 时，一个表对应一个独立的文件，文件以 db_name/table_name.ibd 命名。行存储在这类文件。另外还有 5.7 之后引入 General Tablespace，可以将多个表放到同一个文件里面。
redo log。文件以 ib_logfile0、ib_logfile1 命名，滚动写入。主要满足ACID特性中的 Durablity 特性，保证数据的可靠性，同时把随机写变为内存写加文件顺序写，提高了MySQL的写吞吐。
另外还可能存在临时表空间文件、undo 独立表空间等。

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

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

表空间的格式

除了 redo log 以外，刚刚提到的表空间，包括系统表空间、用户表空间、undo 独立表空间、临时表空间，他们的格式都是一样的，只是里面的 page 各有不同。 本文主要介绍独立用户表空间的结构，进而深入解析索引 。

表空间（tablespace）有一个 32 位的 spaceid，用户表空间物理上是由 page 连续构成的，每个 page 的序号是一个 32 位的 uint， page 0 位于文件物理偏移量 0 处，page 1 位于 16384 偏移量处。由此推出 InnoDB 单表最大 2^32 * 16k = 64T。

表的所有行数据都存在页类型为 INDEX 的索引页（page）上，为了管理表空间，还需要很多其他的辅助页，例如文件管理页 FSP_HDR/XDES 、插入缓冲 IBUF_BITMAP 页、 INODE 页等。

2009年，INNOBASE 分享了关于 InnoDB 的物理结构，里面一张广为流传的图如下。

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

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

图中是系统表空间，因此存在 rollback segment，独立表空间则没有。
leaf node segment 实际是 InnoDB 的 inode 概念，一个 segment 可能包含最多32个碎片 page、0 个extent（用于小表优化），或者是非常多的 extent，我猜测作者图中画了 4 个 extent 是在描述表超过 32MB 大小的时候一次申请 4 个 extent。
一个 extent 在默认 16k 的 page 大小下，由 64 个 page 组成，page 大小由 UNIV_PAGE_SIZE 定义，所以 extent 不一定由 64 个 page 组成。

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

文件管理页

文件管理页的页类型是 FSP_HDR 和 XDES（extent descriptor），用于分配、管理 extent 和 page。

默认一个 extent（1MB大小）管理 64 个物理连续的 page（16k），extent 是 InnoDB 高效分配扩容 page 的机制。如果 page 更小（例如8k，4k），则仍然要保证 extent 最小 1M ，page 数就会相应变多；如果 page 变大（例如32k），则仍然是 64 个 page。

FSP_HDR/XDES 页在表空间中的位置和内部结构如下。

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 状态：

FREE（空）
FREE_FRAG（至少一个被占用）
FULL_FRAG（满）
归某个 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如下。

当一个 Extent 中所有 page 都未被使用时，挂在 FSP_FREE list base node上，可以用于随后的分配；
有一部分 page 被写入的 extent，挂在 FREE_FRAG list base node 上；
全满的 extent，挂在 FULL_FRAG list base node 上；
归属于某个 segment 时候挂在 FSEG list base node上。

当 InnoDB 写入数据的时候，会从这些链表上分配或者回收 extent 和 page，这些 extent 也都是在这几个链表上移动的。

INODE 页

一般而言，INODE 一定会出现在文件的 page 2 上，如果管理的索引过多，才会分配更多的 INODE 页。夹在 page 2 INODE 页和 page 0 FSP_HDR 中间，IBUF_BITMAP 页暂不展开。

INODE页结构如下。

segment 是表空间管理的逻辑单位。INODE 页就是用于管理 segment 的，每个 Inode entry 负责一个segment。

下面会讲到， MySQL 的数据是按照 B+ tree 聚簇索引（clustered index）组织数据的，每个 B+ tree 使用两个 segment 来管理 page，分别是 leaf node segment（叶子节点segment）和 non-leaf node segment（非叶子节点segment）。这两个 segment 的 Inode entry 地址记录在 B+ tree 的 root page 中 FSEG_HEADER 里面，而 root page 又被分配在 non-leaf segment 第一个碎片页上（fragment array）。

一个 segment 由:

32个碎片页（fragment array）
FSEG_FREE
FSEG_NOT_FULL
FSEG_FULL

组成，这些信息记录在 Inode entry 里，可以简单理解为 Inode 就是 segment 元信息的载体。

FREE、NOT_FULL、FULL 三个 FLST_BASE_NODE 对象和 FSP_HDR/XDES 页里面的 FSP_FREE、FREE_FRAG、FULL_FRAG、FSEG 概念类似。这些链表被 InnoDB 使用，用于高效的管理页分配和回收。

至于碎片页上（fragment array），用于优化小表空间分配，先从全局的碎片分配 Page，当 fragment array 填满（32个槽位）时，之后每次分配一个完整的 Extent，如果表大于32MB，则一次分配 4个 extent。

因此可以回答 INNOBASE 图里面的 segment 概念了，只不过 segment 可能包含0或者多个（非常多的）extent。

把segment、extent、page概念串联起来

如下图所示。对照JCole博客的图可以更好的理解。

INDEX 数据索引页

B+树聚簇索引

索引（index）用于快速定位数据，对于 InnoDB 来说，主键和非主键都是索引，一切数据都存储在 INDEX 索引页中，索引即数据，数据即索引。

试想下，加速查询的方法很多，可以是：

哈希索引（hash），点查性能很好，需要解决冲突，区间查询也不友好。MySQL 只有自适应的哈希索引，数据组织的索引不会采用哈希索引。
有序数组（sorted array），更新麻烦，只适用于静态存储引擎。
二叉查找树（binary search tree），查询复杂度是 O(logN)，为了保持这棵树是平衡二叉树，更新的时间复杂度也是 O(logN)。

下图展示了各个存储介质的访问时延，从内存 100ns，到 NVME SSD 16us，到机械磁盘 3-10ms，二叉查找树最大的问题就在于随机IO，所以在机械盘时代，解决的思路就是减少随机 IO，自然而然想到的就是增加树的高度。因此 InnoDB 采用 N 叉平衡树组织索引和数据。

N叉数减少树的高度和随机IO次数，例如当 N=1200，树的高度可以控制在4层，管理 1200^3=17亿行。一般根节点在内存，所以最多3次磁盘 IO。不仅减少了随机 IO 次数还保证了查询的稳定性，所以说这种数据结构是一种 scales nicely 的解决方案。
新模型一些新的存储数据结构采用LSM-tree、跳表skiplist等不在本文讨论范围内。

既然多叉树可以满足查询性能，下面再来看索引和数据是否有必要放在一起呢？索引的组织形式可以是聚簇（clustered）和非聚簇（unclustered）的。

clustered index 将数据按照索引的顺序存储。通常来讲，索引和数据在一起，找到了索引也就找到了数据（但不一定强求）。

unclustered index 则将数据与索引分开结构，索引指向了具体的记录。索引相近的记录，在物理文件上相距可能很远。

一张 MySQL 表只有一个聚簇索引，聚簇索引可以看做主键，如果建表没有指定主键默认采用第一个 NOT NULL UNIQUE INDEX 当主键，否则默认 6字节的 ROW ID 做主键。总之 InnoDB 必须有一个 primary key。聚簇索引通常就是 B+树（B+ tree）结构，如下图所示。

使用B+树聚簇索引（B+ tree clustered index）的好处在于:

数据和索引顺序一致，充分利用磁盘顺序 IO 性能普遍高于随机 IO 的特性。
对于局部性查询也会大有裨益。
采用 B+树，叶子节点（leaf node）存储数据，非叶子节点（non-leaf node）只是索引，这样非叶子节点就会足够的小，因此数据很“热”，便于更好的缓存。
对于覆盖索引，可以直接利用叶子节点的主键值。

二级索引，就可以理解为非聚簇索引，也是一颗 B+树，只不过这棵树的叶子节点是指向聚簇索引主键的，可以看做“行指针”，因此查询的时候需要 “回表” 。

另外一些数据库采用堆表（heap）的方式组织数据和索引。

假设存在一张表，没有任何索引，B+树有三层，按照自增主键插入，可以用 alibaba/innodb-java-reader 工具生成 innodb file LSN heatmap，即 page的热力图，按照 page 被更新的 LSN（Logical Sequence Number）由小到大，由蓝变红，如下图所示。

可以看出 level2 的 root page 总是红色的，因为插入会频繁访问 root page，叶子节点由蓝变红，符合自增主键顺序写入的特性，这也间接证明了自增主键的优势，充分利用利用顺序IO，避免 B+树频繁分裂合并。灰色圈出来的两个 page 是 level=1 的非叶子节点，有两个，右侧节点从左侧分裂而来，因此持续一直“热”到写入结束。

把这个物理文件的变为逻辑的B+树结构，如下图所示。

索引页结构

索引页包含的信息如下：

主键、二级索引、行和列

B+树的每个节点都是一个INDEX索引页，其结构都是相同的。
对于聚簇索引，非叶子节点包含主键和 child page number，叶子节点包含主键和具体的行；
对于非聚簇索引，也就是二级索引，非叶子节点包含二级索引和 child page number，叶子节点包含二级索引和主键值。

行是由列组成的，各种列类型（column types）经过 encoding 编码后才组成了一行。

高效检索的数据结构

B+树结构可以用于快速做 point-query 和 range-query，索引页中必定包含高效检索的数据结构，实际使用的就是 sorted array 和 singly-linked-list，页内支持二分查找。同一层的页之间是 double-linked-list 双向链接的。

支持OLTP数据库特性相关信息

InnoDB 在读写方面，支持事务、行锁、MVCC 非锁定一致性读，ACID 特性，crash recovery 特性等，在索引页里同样包含一些属性支持这些特性。

索引页物理结构如下图所示。

Index header包含了页的一些元数据。

Num of directory slots：page directory slots 个数，用于二分查找检索初始化 sorted array size使用。
Heap top position：页把插入的数据看做数组，用于记录已使用空间的末尾，从这个位置到 page directory都是 free space。
Num of heap records & page format：低15位表示 Num of heap records，最高的一位表示类型，也就是 record format，包括 COMPACT、REDUNDANT 等，下文会提到。
First garbage record offset、Garbage space：表示删除数据 singly-linked-list 的起始 record和空间占用。
Last insertion position：最后插入数据的位置，用户快速顺序写入。
Page direction：插入方向，插入的数据与 Last insertion position 比的相对方位，包括 LEFT、RIGHT、NO_DIRECTION 等。
Num of inserts in page direction：同一方向连续插入的记录数。
Num of records：未删除的记录数，剔除掉 infimum 和supremum 记录。
Max trx. id：最大事务id，用于支持 MVCC。
Page level：B+树层数，叶子节点为0，非叶子节点递增。
Index id：索引id。

FSEG header 包含了指向叶子节点和非叶子节点的 Inode entry 的数据：Inode spaceid、Inode page no.、Inode offset。

infimum 和 supremum 是 system records，用于起始记录和结束记录，对用户不可见，把真正的 record 按照升序串起来成为单链表。这两个 record 和普通的 record 结构一样，都包含 record header 和 body，只不过它们的 body 分别是 “infimum\0” 和 “supremum” 字符串，不像真正的 record 由主键、所有列的值等组成。

例如图中的物理视图，表示按自增主键顺序插入的16条记录，它们的长度可能不一样，比如包含了 varchar 类型的列。把他们转化为逻辑视图，他们是一个有序单链表（sorted singly linked list），头尾就是 infimum 和 supremum 记录，串起来的指针在 record header 里面，record header 有2字节的 next record offset 指向下一条记录的相对物理偏移量。

通过这个有序单链表 InnoDB 就有能力在某个页中做检索查询，给定一个 key，从 infimum 顺序查找，直到到 supremum 结束，时间复杂度 O(N)。

那么有没有什么加速的办法呢？答案是利用 page directory。

page directory 从 Fil Trailer 开始从后往前写，里面包含槽位 slots，每个 slot 2个字节，存储了某些 record 在该页中的物理偏移量，例如图中最后面是 infimum record 的 offset，最前面是 supremum record 的 offset，中间从后往前是 r4，r8，r12 record 的 offset，一般总是每隔4-8个 record 添加一个 slot，这样 slots 就等同于一个稀疏索引（sparse index），加速页内查询的办法就是通过二分查找，查询 key 的时间复杂度可以降为 O(logN)，由于页都在内存里面，所以查询性能可控，内存访问延迟100ns左右，如果在 CPU 缓存中则可能更快。

在 heap top position 和 page directory 中间的都是 free space，用于 record 和 slot 从两端填充进去，对于删除的记录只是标记删除，实际空间回收再利用会延后进行。

索引页案例

把宏观的B+树和微观的页结构以一个案例说明下。

假设有如下的几条数据，

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