MySQL InnoDB存储引擎

本文最后更新于 2025年9月5日凌晨

存储引擎用于组织表中的数据，为Server层提供读写数据的接口

需要考虑的问题

数据存储介质：硬盘，内存

数据组织结构： B-树，B+树，哈希表

支持的数据库功能：事务，行锁，外键，缓存

存储使用的数据结构

数据库分类

关系型数据库：数据以表的方式组织，表与表之间通过外键关联

非关系型数据库：以文档方式，KV方式等组织数据

数据的组织

通过数据库所需实现的功能来进行数据结构选型

线性表

数组

数组的查询/修改都是 O（1）复杂度的数据操作，但是在新增/删除时，需要进行大量的数据迁移工作。

操作	时间复杂度	备注
单条查询	O（1）	随机访问
范围查询	O（1）	随机访问
新增	O（n）	涉及到数据插入后的后续数据迁移
删除	O（n）	涉及到数据插入后的后续数据迁移
修改	O（1）	…

链表

链表的特点是在新增/删除/修改时，只需要修改被修改节点的前后元素指针，但是查询过程需要依次查询所有元素

操作	时间复杂度	备注
单条查询	O（n）	链表需要从头部或者尾部依次查询
范围查询	O（n）	…
新增	O（n）	直接向目标位置插入修改前后node的指针
删除	O（n）	需要执行查询过程
修改	O（n）	需要执行查询过程

散列表

hash表

hash表通过模运算，将数据散列排布到结构中，这让它的新增，删除，修改以及单条查询性能优秀，但是条目间的关系较难处理。

操作	时间复杂度	备注
单条查询	O（1）	通过模运算直接查询到对应的槽位
范围查询	O（n）
新增	O（1）	…
删除	O（1）	…
修改	O（1）	…

树结构

二叉树

实现简单，代码量少，中序遍历天然支持范围查询，内存占用相对较小，但是最坏情况下退化成链表，性能急剧下降，不适合频繁插入删除的场景，无法保证稳定的查询性能

操作	时间复杂度	备注
单条查询	O(log n) ~ O(n)	平衡时O(log n)，退化成链表时O(n)
范围查询	O(log n + k)	k为结果集大小，中序遍历天然有序
新增	O(log n) ~ O(n)	需要先查找插入位置
删除	O(log n) ~ O(n)	需要查找节点并处理子树重组
修改	O(log n) ~ O(n)	先查找再修改

AVL树

AVL树查询性能最稳定，严格的O(log n)，范围查询效率很高，适合读密集型工作负载，插入删除时旋转操作较多，写入性能相对较差，实现复杂度高，维护成本大，对于频繁更新的场景不够友好

操作	时间复杂度	备注
单条查询	O(log n)	严格平衡，高度差不超过1
范围查询	O(log n + k)	k为结果集大小，有序遍历效率高
新增	O(log n)	可能需要最多2次旋转来重平衡
删除	O(log n)	可能需要O(log n)次旋转
修改	O(log n)	先查找再修改

红黑树

红黑树读写性能均衡，插入删除时旋转次数少，实现复杂度适中，被广泛应用（如Linux内核、Java TreeMap），适合读写混合的工作负载，相对AVL树，写入性能更好，但是查询性能略逊于AVL树（但差距很小），相比BST实现复杂度较高，内存开销略大（需要存储颜色信息）

操作	时间复杂度	备注
单条查询	O(log n)	近似平衡，最坏情况下高度为2log(n+1)
范围查询	O(log n + k)	k为结果集大小
新增	O(log n)	最多3次旋转完成重平衡
删除	O(log n)	最多3次旋转完成重平衡
修改	O(log n)	先查找再修改

B树

相比于二叉树，B树通过在每一层增加更多的节点，减少了结构的整体层高，进而减少了查询时整体的I/O次数，提高了查询效率。但是由于在节点上进行数据存储，导致节点的大小较大，同时查询效率不稳定。

操作	时间复杂度	备注
单条查询	O(log_m n)	m为树的阶数，相比二叉树减少了树高
范围查询	O(log_m n + k)	k为结果集大小，但需要回溯父节点
新增	O(log_m n)	可能涉及节点分裂，影响多个层级
删除	O(log_m n)	可能涉及节点合并或重新分布
修改	O(log_m n)	先查找再修改

B+树

B+树在B树的基础上，选择将素有数据存储在叶子节点提供了更好的一致性。

操作	时间复杂度	备注
单条查询	O(log_m n)	必须查找到叶子节点
范围查询	O(log_m n + k)	k为结果集大小，叶子节点链表遍历效率极高
新增	O(log_m n)	只在叶子节点存储数据，分裂影响相对较小
删除	O(log_m n)	只需要在叶子节点删除数据
修改	O(log_m n)	只需要修改叶子节点的数据

总结

对于存储设计来说需要考虑以下问题

数据的组织形式：有结构的数据存储/文档/日志
数据的存储位置：内存/磁盘
数据的存储结构：线性表/哈希表/查找树

以MySQL 为例，MySQL的目标是提供高性能海量数据的结构化查询，那么就意味着

以结构化的存储方式，对插入的条目进行存储
以磁盘为主，缓存为辅的方式，进行数据存储
使用B+树，中间层只存储索引信息，而在叶子节点中存储行数据，同时保证了查询效率和查询一一致性。

B树的组织过程

10, 20, 30, 40, 50, 60, 70, 80, 90
假设B树的度数(degree) = 3，即：

每个节点最多有 2个关键字 (degree-1)
每个节点最多有 3个子节点 (degree)
非根节点至少有 1个关键字

步骤1: 插入 10

1
2

[10]

根节点，直接插入。

步骤2: 插入 20

1
2

[10,20]

节点未满，直接插入。

步骤3: 插入 30

1 2	`[10,20,30] ← 节点已满，需要分裂！`

分裂过程：

选择中间元素 20 作为分裂点
20 上升为新的根节点
10 和 30 分别成为左右子节点

   [20]
  /    \
[10]   [30]

步骤4: 插入 40

   [20]
  /    \
[10]   [30,40]

40插入到30的右边，节点未满。

步骤5: 插入 50

   [20]
  /    \
[10]   [30,40,50]  ← 右子节点满了，需要分裂！

分裂过程：

中间元素 40 上升到父节点
30 和 50 分别成为新的左右子节点

   [20,40]
  /   |   \
[10] [30] [50]

步骤6: 插入 60

   [20,40]
  /   |   \
[10] [30] [50,60]

步骤7: 插入 70

   [20,40]
  /   |   \
[10] [30] [50,60,70]  ← 最右节点满了，需要分裂！

分裂过程：

中间元素 60 要上升到父节点
但父节点 [20,40] 已经满了！

    [20,40,60]  ← 根节点也满了，需要分裂！
   /   |   |   \
[10] [30] [50] [70]

根节点分裂：

中间元素 40 成为新根
[20] 和 [60] 成为左右子节点

      [40]
     /    \
   [20]   [60]
  /  |    |   \
[10][30] [50] [70]

步骤8: 插入 80

      [40]
     /    \
   [20]   [60]
  /  |    |   \
[10][30] [50] [70,80]

步骤9: 插入 90

      [40]
     /    \
   [20]   [60]
  /  |    |   \
[10][30] [50] [70,80,90]  ← 又满了！

最后一次分裂：

      [40]
     /    \
   [20]   [60,80]
  /  |    |  |  \
[10][30] [50][70][90]

最终B树结构

        [40]                    ← 根节点
       /    \
    [20]    [60,80]            ← 内部节点
   /  |     |  |  \
[10][30]  [50][70][90]         ← 叶子节点

平衡性: 所有叶子节点在同一层

有序性: 每个节点内关键字有序，子树间也保持大小关系

度数限制: 每个节点最多2个关键字，最多3个子节点

最小填充: 除根节点外，每个节点至少1个关键字

B+树的增删过程

相对于B树， B+树的非叶子节点不保存具体的数据，而只保存key(索引)，而所有的数据最终都会保存到叶子节点，因为所有数据必须要到叶子节点才能获取到，所以每次数据查询的次数都一样，这样一来B+树的查询速度也就会比较稳定

B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时更方便

B+树全节点遍历更快：B++树遍历整棵树只需要扫描所有的叶子节点即可

初始B+树状态

假设已有一棵B+树（阶数=3）：

          [30]
         /    \
      [20]    [40]
     /  |      |  \
[10:张三] [20:李四] [30:王五] [40:赵六, 50:钱七]
    ↔     ↔      ↔       → NULL

插入 (25,”新员工”)

1. 定位插入位置

1
2
3

25 > 30? NO → 走左子树
25 > 20? YES → 走右分支 → 到达 [20:李四] 叶子节点

2. 插入到叶子节点

1
2
3

插入前: [20:李四]
插入后: [20:李四, 25:新员工]

3. 最终结果

          [30]
         /    \
      [20]    [40]
     /  |      |  \
[10:张三] [20:李四,25:新员工] [30:王五] [40:赵六, 50:钱七]
    ↔         ↔           ↔       → NULL

插入成功 - 节点未满，无需分裂

删除场景：删除 (50,”钱七”)

1. 定位删除位置

1
2
3

50 > 30? YES → 走右子树
50 > 40? YES → 走右分支 → 到达 [40:赵六, 50:钱七] 叶子节点

2. 从叶子节点删除

1
2
3

删除前: [40:赵六, 50:钱七]
删除后: [40:赵六]

3. 最终结果

          [30]
         /    \
      [20]    [40]
     /  |      |  \
[10:张三] [20:李四,25:新员工] [30:王五] [40:赵六]
    ↔         ↔           ↔       → NULL

删除成功 - 节点仍满足最小关键字要求

复杂删除场景：删除 (40,”赵六”)

1. 删除后节点变空

1
2
3

删除前: [40:赵六]
删除后: [空]  ← 触发合并操作！

2. 与左兄弟合并

1
2
3

左兄弟: [30:王五]
合并后: [30:王五]  （原本的40节点消失）

3. 更新内部节点索引

内部节点 [40] 需要删除，与 [20] 合并：

修改前:
          [20]    [40]
         /  |      |  \

修改后:
          [20, 30]
         /   |   \

4. 最终结果

      [20, 30]
     /   |   \
[10:张三] [20:李四,25:新员工] [30:王五]
    ↔         ↔           → NULL

InnoDB

innodb中主要存在两块存储区域

内存存储：将一些热点数据加载到内存中，提高整体的查询和响应速度

硬盘存储：将数据持久化存储到硬盘中

引擎处理流程

磁盘结构

表

表空间

独立表空间与共享表空间

1	`SET GLOBAL innodb_file_per_table -- 通过命令设置创建表的表空间策略`

独立表空间：每张表有一个独立的表空间，file_per_table表空间属于独立表空间

共享表空间：多张表共用一个表空间，其中系统表空间属于共享表空间

在Mysql 中创建的表结构默认情况下会以”.idb”文件存储到 /mysql/datadir/ 文件下

在一个Mysql进程中可以管理多个表空间

CREATE TABLESPACE ts Engine = InnoDB ;
-- 设置表空间
CREATE TABLESPACE ts ADD DATAFILE 'ts.idb' Engine = InnoDB ;
-- 指定表空间名称创建
CRAETE TABLE new_table (c INT PRIMARY KEY) TABLESPACE ts ;
-- 为创建的数据表指定表空间

其他表空间结构

System Tablespace : 共享表空间，并允许存放多个表数据

File-Per-Table Tablespaces : 独立表空间

General Tablespaces : 共享表空间

Undo Tablespaces : 用于事务处理

Temporary Tablespaces : 临时表空间

Redo log : 用于数据恢复

页

在InnoDB中页扮演了两种角色

在B+ 树中，作为最终的叶子节点
在链表中，作为链表结构有序的组织了行数据

页处理.png

数据的插入过程与表分裂

1. 索引导航与位置定位
当数据插入表时，InnoDB通过B+树索引进行层级导航：从根索引页开始，根据键值比较逐层向下查找，最终定位到应当存储该数据的目标数据页（叶子节点）。

2. 页容量检测与分裂机制

在目标数据页中检测剩余容量。当页空间不足以容纳新插入的完整行记录时，触发页分裂操作：

从表空间分配器申请新的数据页
选择适当的分裂点，将原页中的部分数据和新插入数据重新分布到新页中
更新页间的双向链表指针，维护叶子层的逻辑有序性
同步更新父级索引页，添加新的键值边界以反映分裂后的数据范围

3. 多层有序性保障
B+树的设计通过两个层面确保数据有序性：

索引层面：每个索引页的键值严格对应其子树的数据范围边界
叶子层面：所有数据页通过双向指针形成有序链表，支持高效的范围查询和顺序扫描

页结构

File Header（38字节）
PAGE_OFFSET：表空间中页的偏移值，如果某表空间的大小是1GB，且页的大小是16KB，那么一共有65536个页，那么PAGE_OFFSET表示该页在所有页中的位置，如果PAGE_OFFSET=1，说明该页为表空间的第二个页。
PAGE_PREV和PAGE_NEXT：当前页的上一个页和下一个页，用于将页组织成双向链表
PAGE_TYPE： 表示页的类型，根据页存储的数据不同，将页分成不同的类型
SPACE_ID： 表示该页属于哪个表空间
PageHader (56字节)
用于记录页的状态信息
PAGE_N_RECS： 表示该页中包含多少记录
PAGE_LEVEL： 当前页在B+树中的层级，0表示叶子节点
最大最小记录：用于限定记录的边界，用于B+树确定数据边界
User Record： 实际存储行记录的部分
Free Space: 空闲结构，当某条记录被删除时，将其空间加入到空闲链表
Page Directory： 用于高效查找一个页中的某行记录
File Trailer: 存储校验和，用于检查数据是否完整

行结构

1	`[[变长字段的长度列表][NULL值标志位][记录头信息][列1数据][列2数据]...]`

变长字段的长度列表：记录VARCHAR结构的长度信息

NULL值标记位：用于标记哪些值为NULL使用一个bitmap，如果所有字段均不允许为NULL，则取消该字段

记录头信息

1	`[预留位1][预留位2][delete_mask][min_rec_mask][n_owned][heap_no][heap_no][record_type][next_record]`

delete_mask ：当前记录被删除的标志位

n_owened ：当前记录的所在组

record_type ：记录类型00：普通，01： B+树节点指针 10：最小记录 11：最大记录

next_record ：下一条记录的相对位置

隐藏列

DB_ROW_ID（6Bytes）：用于标识一条记录 → 存储主键的值。未指定时选择非空唯一值为主键值，如果没有，则会添加DB_ROW_ID字段作为主键。（用于构建B+树）

DB_TRX_ID（6Bytes）：事务ID

DB_ROLL_ID （7Bytes）：存储回滚指针

查询使用的行格式

SELECT * FROM information_schema.innodb_tables WHERE name = 'engine/t1'\G;
-- 查询使用的行格式
CREATE TABLE test(c INT) row_format=compact;
-- 指定行格式

数据查询过程

B+树阶段

将KEY与每一层的KEY进行比较。

当小于索引KEY 则向左子树进行查询，如果大于索引KEY则向右子树进行查询。

最终查询到符合查询范围的页的偏移信息

页阶段

Page Directory存储的是槽位指针，每个槽位对应一个记录组

记录按主键顺序存储，每组4-8条记录

使用二分查找定位到目标槽位，槽位指向的是该组内主键值最大的记录

行阶段

在确定的记录组内，通过记录头的next_record指针逐条遍历

比较每条记录的主键值

找到匹配记录或确定记录不存在

数据组织

系统表空间 (ibdata1) / 独立表空间 (*.ibd文件)

表段 (Table Segment)

**区 (Extent)**：1MB连续存储 (64个16KB页面)，当页面使用超过1MB后启用区分配
- **页 (Page)**：16KB数据组织单元
  - **页头 (38字节)**：页面元数据、校验信息
  - Page Directory：记录槽位指针数组，二分查找定位
  - 用户记录区：实际数据存储区域
  - 自由空间：未使用的页面空间
  - **行 (Row)**：
    - 变长字段长度列表：逆序存储字段长度
    - NULL值标记位：位图标识NULL字段
    - **记录头信息 (5字节)**：deleted_flag/next_record等控制信息
    - 隐藏字段：row_id(6字节)/trx_id(6字节)/roll_ptr(7字节)
    - 列字段数据：实际用户数据

索引段 (Index Segment)

非叶子节点段：B+树内部节点
叶子节点段：B+树叶子节点
区：同表段结构
- 页：索引页面，存储键值+指针/记录

回滚段 (Rollback Segment)

区：撤销日志存储
- 页：Undo页面，记录事务回滚信息

临时段 (Temporary Segment)

区：临时数据存储
- 页：排序、分组等操作的临时数据

缓存

InnoDB 使用Buffer Pool 来完成缓存处理

Free 链表：

维护空闲缓存页，快速的找到空闲缓存页

每当需要从磁盘中加载一个页到Buffer Pool中时，就从Free链表中取出一个空闲缓存页，并将该缓存页从Free链表中删除。

LRU链表：

维护已经在使用的缓存页，提高缓存命中率。

Buffer Poll的大小是有限的。对于一些频繁访问的数据我们希望可以一直留在Buffer Pool中，而很少访问的数据可以在某些时机淘汰掉，从而保证Buffer Pool不会因为满了而导致无法再缓存新的数据

Flush链表：

维护被修改过的缓存页，快速知道哪些缓存页是赃的

表示此页已被使用且已被修改，其数据和磁盘中的数据已经不一致，当脏页上的数据写入磁盘后，内存数据和磁盘数据一致，那么该页就变成了干净页，脏页同时存在于LRU链表和Flush链表

预读导致的处理问题以及Buffer Pool 污染问题

预读问题

由于局部性，原理InnoDB 会将相邻的页预读到缓存池中，这样一方面被加载到缓存中的数据可能没有被使用，另一方面会导致热点数据被清理。进而导致反复加载。所以InnDB 设置了两片区域，Young/Old，LPU 优先使用Old区的缓存进行汰换，页面从Old区移动到Young区需要被使用并且满足时间间隔条件。

Buffer Pool污染

对于模糊搜索，会导致数据库进行页遍历操作，这时随着页的加载，LPU会逐渐清理掉链表中的页信息，最终导致这些临时的表信息挤压了热点页信息，优化方法是在Old区设置页被加载到页被使用的时间区间，当小于1000ms(可配置)就被使用的页结构，不会被加载到Young区

缓存中页查询过程

在缓存中，当页被加载到内存后，会将该页按表空间号和页号进行哈希计算，存储到对应的桶结构中，查询时，同样通过哈希向桶结构中查询，对应的页号信息。之后再在该页中使用槽位信息，进行二分查找，最终再目标组中使用遍历查询最终的行信息。

1. Buffer Pool层面 - 哈希定位页面

*// 第一步：在Buffer Pool中找到页面*
uint32_t hash = (space_id << 20) ^ page_no;     *// 哈希计算*
uint32_t bucket = hash % hash_table_size;       *// 确定桶号*
HashBucket* target_bucket = &hash_buckets[bucket];

*// 在桶的链表中查找目标页面*
for (BufferBlock* block = target_bucket->first_block; block; block = block->hash_next) {
    if (block->space_id == space_id && block->page_no == page_no) {
        return block;  *// 找到页面！*
    }
}

2. Page页面层面 - 槽位二分查找

*// 第二步：在页面内通过页面目录定位记录组*
Record* find_record_in_page(Page* page, uint32_t search_key) {
    *// 在页面目录中二分查找槽位*
    int left = 0, right = page->slot_count - 1;
    int target_slot = -1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        uint32_t slot_min_key = page->slots[mid].min_key;
        uint32_t slot_max_key = page->slots[mid].max_key;
        
        if (search_key >= slot_min_key && search_key <= slot_max_key) {
            target_slot = mid;  *// 找到目标槽位！*
            break;
        } else if (search_key < slot_min_key) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    *// 第三步：在槽位指向的记录组中遍历查找*
    return linear_search_in_group(page->slots[target_slot], search_key);
}

MySQL

#存储 #数据库 #中间件 #MySQL

MySQL InnoDB存储引擎

http://gadoid.io/2025/09/05/MySQL-InnoDB存储引擎/

作者

Codfish

发布于

2025年9月5日

许可协议

MySQL 索引类型上一篇

MySQL 命令行基础下一篇

MySQL InnoDB存储引擎

存储使用的数据结构

数据库分类

数据的组织

线性表

散列表

树结构

总结

B树的组织过程

步骤1: 插入 10

步骤2: 插入 20

步骤3: 插入 30

步骤4: 插入 40

步骤5: 插入 50

步骤6: 插入 60

步骤7: 插入 70

步骤8: 插入 80

步骤9: 插入 90

最终B树结构

B+树的增删过程

初始B+树状态

插入 (25,”新员工”)

删除场景：删除 (50,”钱七”)

复杂删除场景：删除 (40,”赵六”)

InnoDB

磁盘结构

表

页

页结构

行结构

数据查询过程

B+树阶段

页阶段

行阶段

数据组织

表段 (Table Segment)

索引段 (Index Segment)

回滚段 (Rollback Segment)

临时段 (Temporary Segment)

缓存

Free 链表 ：

LRU链表：

Flush链表：

预读导致的处理问题以及Buffer Pool 污染问题

预读问题

Buffer Pool污染

缓存中页查询过程

1. Buffer Pool层面 - 哈希定位页面

2. Page页面层面 - 槽位二分查找

Free 链表：