索引介绍

1. 索引基本介绍：索引到底是什么

索引（Index）是数据库在表数据之外维护的一份有组织的辅助结构。它的目标不是存更多业务信息，而是回答一个更关键的问题：

给定查询条件，如何更快定位到目标行。

如果没有索引，数据库通常只能：

从头到尾扫描整张表。
对每一行做条件判断。

而有了索引之后，数据库可以先在索引里缩小范围，再决定要不要回表取完整数据。

索引的核心本质是：

用额外空间换查询效率
用写入维护成本换读取性能

所以索引从来不是“越多越好”，而是一个典型的工程权衡。

1.1 索引能解决什么问题

索引最常加速的是这些操作：

WHERE 过滤
JOIN 连接
ORDER BY 排序
GROUP BY 分组
DISTINCT 去重
范围查询（如 >, <, BETWEEN）

1.2 索引带来的代价是什么

索引不是免费午餐，常见代价包括：

占用额外磁盘空间和缓存空间
INSERT、UPDATE、DELETE 时要同步维护索引
索引越多，写放大越明显
优化器候选路径更多，统计信息不准时可能选错索引
不合理索引会带来更多页分裂、碎片、锁竞争

一句话总结：

索引优化的是读
索引牺牲的是写和空间

2. 索引格式介绍：一条索引记录到底长什么样

“格式介绍”如果从数据库原理角度来讲，最关键的是两层：

索引条目（Index Entry）格式
索引页（Page）格式

2.1 索引条目的基本组成

从抽象上看，一条索引记录通常包含两部分：

索引键（Key）
行定位信息（Row Locator）

其中：

索引键决定“按什么顺序组织”
行定位决定“命中后怎么找到真实数据”

例如：

单列索引：name
联合索引：(user_id, created_at)

在联合索引中，比较顺序按列从左到右逐列比较，这也是最左前缀原则的根源。

2.2 行定位信息是什么

不同数据库、不同引擎，对“定位信息”处理方式不同。

常见有 3 类：

直接存整行数据
典型是聚簇索引叶子节点。
存物理地址或行标识
例如某些数据库会存 RID/TID。
存主键值
InnoDB 二级索引就是这种方式。
命中二级索引后，再根据主键去聚簇索引取整行，这就是“回表”。

2.3 索引页格式：为什么数据库总在讲 Page

磁盘数据库真正昂贵的通常不是一次比较，而是一次随机 I/O。

所以数据库不会把索引组织成“一个节点一个磁盘读写”，而是按页（Page） 为单位管理：

一次 I/O 读一页
一页里放很多条索引记录
页内再做二分或目录查找

以 InnoDB 为例：

页通常是 16KB
B+ 树的每个节点本质上就是一个索引页
非叶子页存键和子指针
叶子页存键和数据行或主键值

这也是数据库索引讨论中“扇出（fan-out）”“树高”“页分裂”“页合并”这些词频繁出现的原因。

2.4 为什么格式会影响性能

索引记录格式和页格式，直接影响：

一页能放多少条记录
树的高度
查询需要多少次 I/O
插入时是否容易页分裂
二级索引是否容易膨胀

所以数据库索引的设计，本质上是在做：

页容量
树高度
有序性
写入维护成本

这几个因素之间的平衡。

3. 索引分类：从不同维度怎么划分

索引不能只按一种方式分类。工程里通常至少从 3 个维度来理解：

按底层数据结构
按逻辑功能
按物理存储方式

3.1 按底层数据结构分类

类型	是否有序	典型优势	典型短板	常见场景
B 树 / B+ 树	有序	等值、范围、排序	写入有页分裂成本	关系型数据库通用索引
Hash	无序	等值查询快	不支持范围和排序	内存引擎、KV 场景
Bitmap	位图	多条件组合过滤强	不适合高频更新	数仓、低基数分析
倒排索引	term 有序	全文检索	不擅长数值范围	搜索、日志、文本
R-Tree	空间层次	空间查询强	不适合单维全序排序	GIS
LSM-Tree	有序文件 + 合并	写入吞吐高	Compaction 成本高	RocksDB / HBase / Cassandra

3.2 按逻辑功能分类

这是开发最常接触的一类。

普通索引
只负责加速查询，不提供唯一性约束。
唯一索引
保证索引键值唯一。
主键索引
唯一标识一行数据。
在 InnoDB 中还承担聚簇组织作用。
联合索引
多列共同组成一个索引。
需要遵循最左前缀原则。
全文索引
面向文本检索。
空间索引
面向地理空间对象。

3.3 按物理存储方式分类

这个维度在 MySQL，尤其是 InnoDB 里非常重要。

聚簇索引（Clustered Index）
叶子节点直接存放整行数据。
一张表通常只能有一个聚簇组织方式。
二级索引 / 非聚簇索引（Secondary Index）
叶子节点不存整行，而是存二级键 + 主键值。
取非索引列时通常需要回表。

3.4 MySQL 中常见索引类型速查

结合开发场景，MySQL 中最常提到的是：

主键索引
唯一索引
普通索引
联合索引
前缀索引
全文索引
空间索引
聚簇索引
二级索引
覆盖索引

4. 索引常用数据结构介绍

数据库索引底层结构不是随便选的，而是围绕访问模式做取舍。

4.1 为什么数据库不会直接用数组

有序数组查找很快，可以二分，时间复杂度是 O(log N)。

但问题是：

插入和删除代价太高
需要移动大量元素
数据量大时磁盘改动非常重

所以数组更适合“静态有序集合”，不适合频繁增删改的数据库索引。

4.2 为什么普通二叉搜索树不够

二叉搜索树的查询、插入、删除理论上也可以做到 O(log N)，但前提是树足够平衡。

问题在于：

如果数据按有序顺序插入
树会退化成链表
时间复杂度退化到 O(N)

这对数据库来说不可接受。

4.3 为什么会出现红黑树、B 树、B+ 树

它们本质上都在解决“树不能退化”的问题，但重点不同：

红黑树：
主要解决内存中的平衡查找问题。
B 树：
主要解决磁盘场景下“树太高，I/O 太多”的问题。
B+ 树：
在 B 树基础上进一步优化范围查询、页利用率和磁盘访问模式。

5. B 树介绍

5.1 B 树是什么

B 树（B-Tree）是一种多路平衡查找树，不是二叉树。

它的核心特点是：

一个节点可以有多个子节点
一个节点里可以存多个键
所有叶子节点都在同一层
节点大小通常和磁盘页大小匹配

这使得树从“高瘦”变成“矮胖”。

5.2 B 树的结构特点

每个节点存多个 key
key 在节点内有序排列
节点间通过多个子指针连接
内部节点和叶子节点都可以存数据

这点和 B+ 树很不一样。

5.3 B 树的优点

树的高度比二叉树低很多
单次查询需要的 I/O 次数更少
适合磁盘存储
等值查询效率高

5.4 B 树的缺点

内部节点既存 key 又存 data，导致一个页里能放的 key 变少
扇出下降，树高可能比 B+ 树更高
范围查询不够友好
顺序扫描通常不如 B+ 树自然

5.5 B 树范围查询为什么不如 B+ 树

因为 B 树的数据分布在所有层级节点中。

做范围查询时：

不能像 B+ 树那样只在叶子层顺序扫
可能要反复回到父节点，再跳去其他子树

这对磁盘 I/O 和实现复杂度都不够友好。

6. B+ 树介绍

6.1 B+ 树是什么

B+ 树是 B 树的一种变体，也是 MySQL InnoDB 最经典的索引结构。

它最核心的定义有 3 条：

所有数据都只存放在叶子节点
非叶子节点只存放键和子指针
叶子节点之间通过链表连接

6.2 B+ 树的结构特点

非叶子节点只负责导航，不存放真实行数据
叶子节点存放完整记录或行定位信息
叶子节点天然有序
叶子节点链表支持顺序遍历
所有查询最终都会落到叶子层

6.3 B+ 树为什么更适合数据库

核心原因是 4 个：

非叶子节点更轻，一个页能容纳更多 key。
扇出更大，树更矮，随机 I/O 更少。
叶子节点链表让范围查询和排序非常高效。
查询路径更稳定，所有查询都走到叶子层，延迟更可预测。

6.4 B+ 树的时间复杂度为什么是 `O(log_m N)`

这里的 m 可以简单理解为 一页大约能指向多少个子页，也就是常说的扇出。

计算思路其实很直观：

第 1 层最多管 m 个子节点
第 2 层最多管 m × m = m² 个子节点
第 3 层最多管 m³ 个子节点

如果整棵树能容纳 N 条记录，那么树高 h 大致满足：

m^h >= N

把它反过来写，就是：

h ≈ log_m N

而一次查找，本质上就是从根节点一路往下走到叶子节点，走几层，通常就要做几次页访问，所以时间复杂度就是：

O(log_m N)

可以把它理解成：

普通二叉树每层只能分成 2 条路，所以树会比较高
B+ 树每层能分成很多条路，所以树会非常矮

举个很通俗的例子：

假设一个非叶子页平均能指向 1000 个子页
那么 3 层大约就能管理 1000³ = 10 亿级别的数据范围

这就是为什么数据库里明明数据很多，但 B+ 树查找通常只需要很少几层，落到工程上就是：

比较次数是对数级别
更重要的是磁盘 I/O 次数也很少

这也是大家常说“B+ 树查找效率高，不是因为它比较神奇，而是因为它足够矮”。

6.5 MySQL InnoDB 中的 B+ 树

InnoDB 的 B+ 树有两个非常重要的实现形态：

聚簇索引
叶子节点存整行数据。
二级索引
叶子节点存二级键 + 主键值。

这直接带来两个工程结论：

主键越长，所有二级索引都会越大。
如果查询列都在二级索引里，就可以避免回表，形成覆盖索引。

6.6 B+ 树的缺点

B+ 树也不是完美的。

常见代价包括：

写入时可能发生页分裂和页合并
随机主键会导致插入离散、页分裂更频繁
维护多个二级索引会显著增加写放大
不适合全文、多维空间这类非单维有序场景

7. 红黑树介绍

7.1 红黑树是什么

红黑树（Red-Black Tree）是一种自平衡二叉搜索树。

它通过颜色规则和旋转操作，保证树不会严重失衡。

7.2 红黑树的核心性质

经典规则包括：

每个节点非红即黑。
根节点是黑色。
所有叶子空节点视为黑色。
红色节点的子节点必须是黑色。
任一节点到其所有叶子节点路径上的黑节点数相同。

这些规则保证它的高度始终控制在 O(log N) 量级。

7.3 红黑树的优点

查找、插入、删除复杂度稳定在 O(log N)
旋转和调平成本可控
特别适合内存数据结构
实现成熟，工程上非常常见

7.4 红黑树的缺点

本质还是二叉树，扇出只有 2
数据量一大，树高明显高于 B 树 / B+ 树
如果每层都对应一次磁盘 I/O，磁盘访问次数会很多
范围查询虽然能做，但不如 B+ 树叶子链表高效

7.5 红黑树更适合什么场景

红黑树更适合：

内存结构
高频插入删除
需要有序集合但不依赖磁盘页模型的场景

典型例子：

Java TreeMap
Java TreeSet
C++ map
C++ set

8. B 树、B+ 树、红黑树三者的区别详细介绍

8.1 从“树的形态”看区别

红黑树：
二叉树，每个节点最多 2 个孩子。
B 树：
多路平衡树，一个节点可以有多个孩子。
B+ 树：
也是多路平衡树，但内部节点只存索引，数据集中在叶子层。

结论是：

红黑树更“高”
B 树、B+ 树更“矮胖”

8.2 从“数据存在哪”看区别

红黑树
每个节点都可能存 key 和 value。
B 树
内部节点和叶子节点都存数据。
B+ 树
只有叶子节点存数据，内部节点只存 key。

这会直接影响：

页能放多少 key
树高
查询路径

8.3 从“磁盘 I/O”看区别

这是数据库为什么更偏爱 B+ 树的关键。

红黑树
扇出只有 2，节点层数很多。
数据量大时，需要更多 I/O。
B 树
多路结构降低树高，I/O 显著减少。
B+ 树
内部节点更轻，同样页大小下扇出更大。
通常树高比 B 树还低。

所以从磁盘友好性看：

B+ 树 > B 树 > 红黑树

8.4 从“范围查询”看区别

红黑树
可以中序遍历做范围查询，但需要频繁访问树节点。
B 树
也能做范围查询，但数据分散在不同层级，遍历不够连续。
B+ 树
先定位到起始叶子节点，再沿叶子链表顺序扫描即可。

所以范围查询能力：

B+ 树最强
B 树次之
红黑树更偏内存场景，不适合磁盘范围扫描

8.5 从“查询稳定性”看区别

红黑树
查询路径与树高相关，稳定在 O(log N)。
B 树
可能在内部节点就命中数据，也可能走到叶子。
B+ 树
所有查询都走到叶子层，路径长度更稳定。

对数据库来说，路径稳定意味着：

响应时间更可预测
缓存和预读策略更容易设计

8.6 从“内存 / 磁盘适配性”看区别

红黑树
更适合内存数据结构。
B 树
适合磁盘页管理。
B+ 树
最适合以页为单位、强调范围扫描和顺序访问的数据库索引。

8.7 一张表总结三者区别

维度	红黑树	B 树	B+ 树
结构	自平衡二叉树	多路平衡树	多路平衡树
扇出	2	大于 2	大于 2，通常更大
数据存储	所有节点	所有节点	仅叶子节点
内部节点是否存数据	是	是	否
树高	较高	较低	通常最低
磁盘 I/O	较多	较少	最少
等值查询	好	好	好
范围查询	一般	较好	最好
顺序扫描	一般	一般	最好
典型场景	内存有序集合	外存索引	数据库索引

9. 为什么 MySQL 采用 B+ 树作为索引

这个问题本质上是在问：

为什么不是红黑树
为什么不是普通 B 树
为什么是 B+ 树

9.1 为什么不是红黑树

因为红黑树虽然平衡，但它仍然是二叉树。

这意味着：

扇出很小
树高很高
数据量大时磁盘 I/O 太多

数据库最怕的是随机 I/O 多，而不是单次比较多，所以红黑树不适合作为磁盘数据库主索引。

9.2 为什么不是普通 B 树

B 树已经比红黑树更适合磁盘了，但仍然有两个问题：

内部节点也存数据，导致一个页里能放的 key 更少。
范围查询和顺序扫描不如 B+ 树自然。

所以在数据库最常见的访问模式里，B+ 树通常更优。

9.3 为什么 B+ 树正好匹配数据库需求

数据库最常见的查询特征是：

等值查询很多
范围查询很多
排序和分页很多
数据落磁盘，I/O 成本高

B+ 树刚好匹配这些需求：

多路结构降低树高
内部节点只存 key，扇出更大
叶子链表支持范围扫描和排序
查询路径稳定，便于缓存和预读

所以对 MySQL InnoDB 来说，B+ 树是一个非常自然的工程选择。

10. MySQL 中索引的重点落地概念

10.1 聚簇索引与二级索引

InnoDB 中：

主键索引通常就是聚簇索引
二级索引叶子节点存的是主键值

因此：

主键设计要短、稳定、尽量递增
查询能覆盖就覆盖，尽量减少回表

10.2 联合索引与最左前缀

联合索引 (a, b, c) 本质上按 (a, b, c) 字典序组织，所以天然支持：

a
a, b
a, b, c

但不天然支持跳过左侧前导列直接用后面的列缩小范围。

10.3 覆盖索引与回表

如果查询需要的列都在索引记录里，就不需要回到聚簇索引取整行，这就是覆盖索引。

它的价值很直接：

少一次甚至多次随机 I/O
对高频查询收益明显

10.4 前缀索引

长字符串字段直接建全长索引会让索引非常大。

MySQL 支持前缀索引，例如：

CREATE INDEX idx_email_prefix ON t_user(email(16));

它用更小空间换部分选择性，但注意：

前缀太短会导致区分度差
前缀索引通常不如完整索引稳定

11. 索引设计的工程原则

11.1 从查询出发，不要从字段出发

索引不是“哪个字段常用就给哪个字段建”，而是要围绕：

过滤条件
排序条件
分组条件
Join 条件
返回列

一起设计。

11.2 控制数量，避免过度索引

常见错误包括：

每个字段都建单列索引
联合索引和重复前缀索引同时存在
很少查询的列也建索引

这会带来明显写放大和存储浪费。

11.3 让查询“可走索引”

典型反例：

对索引列做函数
隐式类型转换
前导 % 的 LIKE
联合索引顺序不匹配

这些问题会让 B+ 树的有序性无法被优化器利用。

11.4 用 `EXPLAIN` 验证，而不是凭感觉

设计完索引后，应该用 EXPLAIN 看：

是否真的使用了预期索引
扫描行数是否合理
是否出现 Using filesort
是否发生大量回表

11.5 MySQL 索引什么情况下会失效

先说明一个容易混淆的点：

面试里说“索引失效”，通常不是指索引物理上没了。
更准确地说，是优化器没有使用索引，或者没有按我们期待的方式高效使用索引。

最常见的情况有下面这些。

11.5.1 对索引列做函数、表达式、运算

一旦把列本身改造了，B+ 树里原本的有序性就很难直接利用。

SELECT * FROM t_user WHERE YEAR(create_time) = 2025;
SELECT * FROM t_user WHERE salary + 1000 > 20000;
SELECT * FROM t_user WHERE id * 2 = 10;

更推荐改写成：

SELECT * FROM t_user
WHERE create_time >= '2025-01-01'
  AND create_time < '2026-01-01';

11.5.2 隐式类型转换

如果列类型和条件类型不一致，MySQL 可能会先做类型转换，再比较，这时就可能无法高效走索引。

-- phone 是 varchar
SELECT * FROM t_user WHERE phone = 13800138000;

-- user_id 是 int
SELECT * FROM t_order WHERE user_id = '1001';

实战里要尽量保证：

列是什么类型，参数就传什么类型
关联列的字符集、排序规则也尽量一致

11.5.3 `LIKE` 以 `%` 开头

B+ 树能利用的是“从左到右有序”这个特性，所以前缀匹配可以，前导模糊通常不行。

SELECT * FROM t_user WHERE name LIKE 'abc%';   -- 通常可以利用索引
SELECT * FROM t_user WHERE name LIKE '%abc';   -- 常见失效场景
SELECT * FROM t_user WHERE name LIKE '%abc%';  -- 常见失效场景

如果业务是全文包含匹配，通常要考虑：

全文索引
搜索引擎
额外的倒排检索方案

11.5.4 联合索引不满足最左前缀

联合索引 (a, b, c) 能高效支持的是：

a
a, b
a, b, c

但如果跳过最左列，后面的列通常无法单独利用这棵联合索引来缩小范围。

-- 已有联合索引 (a, b, c)
SELECT * FROM t WHERE b = 2;
SELECT * FROM t WHERE c = 3;
SELECT * FROM t WHERE b = 2 AND c = 3;

这些都属于典型的“没有满足最左前缀”。

11.5.5 联合索引中间遇到范围查询，右侧列可能失效

这也是面试特别爱问的一类。

假设有联合索引 (a, b, c)：

SELECT * FROM t
WHERE a = 1 AND b > 10 AND c = 3;

这里通常可以利用：

a
b

但 b > 10 是范围条件后，c 往往就不能继续用于索引过滤了，最多可能用于回表后再判断，或者只在某些场景参与 ICP。

可以把它理解成：

联合索引在范围条件右边的列，常常无法继续保持高效匹配能力

11.5.6 `OR` 两侧条件不都能走索引

OR 很容易让优化器放弃索引，尤其当一边能走索引、一边不能走索引时更明显。

SELECT * FROM t_user
WHERE name = 'Alice' OR age = 18;

如果 name 有索引，但 age 没索引，优化器就可能直接选择全表扫描。

这类 SQL 常见改写思路是：

给相关列都补上合适索引
或拆成两条 SQL 用 UNION ALL

11.5.7 过滤结果太多，优化器主动放弃索引

有时候不是“不能用”，而是 MySQL 觉得用了还不如不用。

例如：

表里大部分数据都满足条件
字段区分度很低
回表成本太高

这时即使列上有索引，优化器也可能认为全表扫描更便宜。

典型场景如：

SELECT * FROM t_user WHERE gender = 1;
SELECT * FROM t_order WHERE status = 0;

如果这类字段只有少数几个取值，而且命中比例很高，索引收益就会很差。

11.5.8 使用 `!=`、`<>`、`NOT IN`、`NOT LIKE` 时效果往往很差

这类条件通常意味着“我要大部分数据，只排除少量数据”，因此优化器常常认为不值得走索引。

SELECT * FROM t_user WHERE status <> 1;
SELECT * FROM t_user WHERE name NOT LIKE 'abc%';
SELECT * FROM t_order WHERE user_id NOT IN (1, 2, 3);

要注意：

这不是绝对不能走索引
但它们非常容易让索引利用率变差，甚至直接退化成全表扫描

11.5.9 排序、分组没有和索引顺序对齐

即使 WHERE 用到了索引，ORDER BY / GROUP BY 也不一定能继续利用索引顺序。

比如联合索引是 (a, b, c)，但你写的是：

SELECT * FROM t
WHERE a = 1
ORDER BY c;

这时过滤可能能用到索引，但排序未必还能沿着索引顺序完成，最后可能出现 Using filesort。

11.5.10 统计信息不准，导致选错索引或不走索引

MySQL 是否走索引，本质上是优化器基于成本估算做决策。

如果统计信息过旧、不准确，就可能出现：

本来该走索引，却没走
本来该走 A 索引，却选成了 B 索引

所以排查“索引失效”时，不能只盯 SQL 写法，也要看：

EXPLAIN
表数据分布
统计信息是否新鲜

11.5.11 一段适合面试的总结

可以直接这样答：

MySQL 里所谓索引失效，通常不是索引不存在了，而是优化器没有按预期高效使用索引。常见场景包括：对索引列做函数或运算、隐式类型转换、LIKE 以 % 开头、联合索引不满足最左前缀、范围查询后右侧列失效、OR 条件破坏索引使用，以及字段区分度太低导致优化器主动放弃索引。判断是否真的失效，最终还是要结合 EXPLAIN 看执行计划。

12. 面试回答

可以直接这样答：

索引是数据库维护的一种辅助数据结构，本质上是把索引键映射到数据行定位信息，用空间和写入成本换读取性能。
数据库索引常见结构有 B 树、B+ 树、Hash、倒排索引等，而 MySQL InnoDB 之所以选择 B+ 树，核心是它更适合磁盘场景：非叶子节点只存键，扇出更大，树更矮，随机 I/O 更少；同时叶子节点链表让范围查询、排序和分页都很高效。
相比之下，红黑树虽然也是平衡树，但它是二叉树，树高高，不适合磁盘；普通 B 树虽然也适合磁盘，但内部节点还存数据，扇出不如 B+ 树，范围查询也不如 B+ 树自然。

13. InnoDB 索引底层存储格式详解

13.1 InnoDB 页的整体布局

InnoDB 所有磁盘数据都以 页（Page） 为最小 I/O 单位管理，默认页大小为 16KB。B+ 树的每一个节点就是一张页。一张索引页从头到尾由 7 个区域组成：

┌──────────────────────────────────────────────────────────────┐
│  File Header          (38 bytes)                             │
│  包含：space_id、page_no、prev_page、next_page               │
│        log_sequence_number(LSN)、page_type、checksum         │
├──────────────────────────────────────────────────────────────┤
│  Page Header          (56 bytes)                             │
│  包含：n_dir_slots、heap_top、n_recs、free_space_offset      │
│        garbage_offset、level（0 = 叶子层）、index_id …      │
├──────────────────────────────────────────────────────────────┤
│  Infimum Record       (13 bytes)                             │
│  虚拟最小哨兵记录，是页内链表的起始头节点                    │
├──────────────────────────────────────────────────────────────┤
│  Supremum Record      (13 bytes)                             │
│  虚拟最大哨兵记录，是页内链表的终止尾节点                    │
├──────────────────────────────────────────────────────────────┤
│  User Records                                                │
│  真实的索引记录，按索引键升序通过单向链表串联                │
│                          ▼ 向低地址增长                      │
├──────────────────────────────────────────────────────────────┤
│  Free Space                                                  │
│  尚未使用的空闲区域                                          │
├──────────────────────────────────────────────────────────────┤
│  Page Directory       (每个槽固定 2 bytes)                   │
│  稀疏目录：每 4~8 条记录设一个槽，存该记录在页内的偏移量     │
│                          ▲ 向高地址增长                      │
├──────────────────────────────────────────────────────────────┤
│  File Trailer         (8 bytes)                              │
│  checksum，与 File Header 配合验证页完整性                   │
└──────────────────────────────────────────────────────────────┘

页内记录的组织方式：

记录按键值升序通过记录头中的 next_record 指针串成单向链表，Page Directory 作为稀疏目录加速页内二分查找：

Infimum ──▶ [id=1 记录] ──▶ [id=3 记录] ──▶ [id=7 记录] ──▶ Supremum
                ↑                                 ↑
           Page Directory                   Page Directory
           (槽 #1，指向此)                  (槽 #2，指向此)

File Header 中的 prev_page 和 next_page 字段将同层的所有叶子页串成一条双向链表，这是 B+ 树支持范围扫描的物理基础。

13.2 行记录的 Compact 格式

InnoDB 最常用的行格式是 Compact（紧凑格式），每条用户记录物理上由 4 部分顺序拼接而成：

┌────────────────────────────────────────────────────────────────┐
│  ① 变长字段长度列表（逆序）                                    │
│     仅记录 VARCHAR / BLOB 等变长列的实际字节数                 │
│     按列声明顺序的倒序存储（最后声明的列的长度在最前）         │
├────────────────────────────────────────────────────────────────┤
│  ② NULL 标志位图                                               │
│     每个声明为 NULL 的列占 1 个 bit，bit=1 表示该列值为 NULL  │
│     列数 ≤ 8 时占 1 byte，以此类推                            │
├────────────────────────────────────────────────────────────────┤
│  ③ 记录头信息（固定 5 bytes）                                  │
│     · delete_mask  (1 bit)   ← 软删除标记                     │
│     · min_rec_mask (1 bit)   ← B+ 树非叶子层最左记录的标记    │
│     · n_owned      (4 bits)  ← 当前 Page Directory 槽拥有几条 │
│     · heap_no      (13 bits) ← 记录在堆空间中的编号           │
│     · record_type  (3 bits)  ← 0普通 / 1非叶子指针 / 2Inf / 3Sup │
│     · next_record  (16 bits) ← 指向下一条记录的相对偏移量     │
├────────────────────────────────────────────────────────────────┤
│  ④ 列数据                                                      │
│     聚簇索引叶子行还额外包含两个隐式系统列：                   │
│     · trx_id   (6 bytes)  ← 最近修改该行的事务 ID（MVCC 用）  │
│     · roll_ptr (7 bytes)  ← 指向 undo log 的回滚指针（MVCC 用）│
└────────────────────────────────────────────────────────────────┘

13.3 聚簇索引叶子页：结构示例

以如下表为例，贯穿后续所有示例：

CREATE TABLE t_user (
    id    INT          NOT NULL,
    name  VARCHAR(20)  NOT NULL,
    email VARCHAR(50)  NOT NULL,
    age   TINYINT      NOT NULL,
    PRIMARY KEY (id),
    INDEX idx_name (name)
);

插入一条记录：(id=1, name='Alice', email='alice@example.com', age=25)

该行在聚簇索引叶子页中的物理布局（Compact 格式）：

 偏移    字节数  字段                   值（十六进制 / 说明）
──────  ──────  ──────────────────────  ────────────────────────────────
 +0      1      变长长度: email         0x12  ← 'alice@example.com' 18 bytes
 +1      1      变长长度: name          0x05  ← 'Alice' 5 bytes
                ↑ 变长字段列表逆序：email 比 name 后声明，故先写
 +2      0      NULL 标志位图           （所有列 NOT NULL，位图为空）
 +2      5      记录头信息              01 00 00 10 28  ← heap_no=2,
                                        record_type=0（普通行）,
                                        next_record=下一条记录的偏移
 +7      4      id                     00 00 00 01  ← 主键值 1
 +11     6      trx_id                 ← 6 bytes，当前事务 ID
 +17     7      roll_ptr               ← 7 bytes，undo log 回滚指针
 +24     5      name                   "Alice"
 +29     18     email                  "alice@example.com"
 +47     1      age                    0x19  ← 值 25

同一叶子页内的多行按主键升序链接：

 Infimum
    │ next_record ──▶ [id=1 | trx_id | roll_ptr | 'Alice' | 'alice@...' | 25]
                          │ next_record ──▶ [id=3 | trx_id | roll_ptr | 'Bob' | 'bob@...'   | 30]
                                                │ next_record ──▶ [id=7 | trx_id | roll_ptr | 'Carol' | 'carol@...' | 28]
                                                                      │ next_record ──▶ Supremum

13.4 二级索引叶子页：与聚簇索引的关键区别

idx_name 的叶子行不存整行数据，只存索引键列（name）+ 主键值（id）：

 偏移    字节数  字段                   值
──────  ──────  ──────────────────────  ────────────────────
 +0      1      变长长度: name          0x05  ← 5 bytes
 +1      0      NULL 标志位图           （空）
 +1      5      记录头信息              record_type=0（普通行）
 +6      5      name                   "Alice"  ← 索引键
 +11     4      id                     00 00 00 01  ← 主键，用于回表

按 name 升序排列后，idx_name 叶子页链表形如：

 Infimum
    │──▶ [name='Alice', id=1]
             │──▶ [name='Bob',   id=3]
                      │──▶ [name='Carol', id=7]
                               │──▶ Supremum

回表路径（查询 WHERE name = 'Bob'）：

 ① 在 idx_name B+ 树中定位叶子层 name='Bob' 的记录
               ↓
 ② 读取该记录中的主键值：id = 3
               ↓
 ③ 用 id=3 去聚簇索引 B+ 树中再查一次
               ↓
 ④ 在聚簇索引叶子页取出完整行（包含 email、age 等列）

若 SELECT name, id FROM t_user WHERE name = 'Bob'，所需列 name 和 id 都在二级索引里，则不需要回表，这就是覆盖索引（Covering Index）。

13.5 非叶子（内部）页的记录格式

内部页负责导航，不存业务数据。每条内部记录只有两个字段：

分隔键（索引键值）：指向子树中的最小键（或分裂时上推的键）
子页页号（child_page_no）：4 bytes，指向下一层页

record_type = 1 表示这是非叶子节点的子页指针。

对 idx_name 内部页，一条记录示意：

 ┌──────────────────────────────────────┐
 │  record_type = 1（非叶子节点指针）   │
 │  name        = "Carol"               │  ← 分隔键
 │  child_page_no = 0x0023              │  ← 页号 35
 └──────────────────────────────────────┘
 含义：name >= 'Carol' 的记录全部在页号 35 的子页中

内部页的完整结构示意：

┌──────────────────────────────────────────────────────────┐
│  File Header / Page Header / Infimum / Supremum          │
├──────────────────────────────────────────────────────────┤
│  [key='Alice', page_no=20] ──▶ [key='Carol', page_no=23] │
│       ↑                              ↑                   │
│  name < 'Carol' 走 page#20     name >= 'Carol' 走 page#23│
└──────────────────────────────────────────────────────────┘

查询 name = 'Bob'： - 在内部页发现 'Alice' ≤ 'Bob' < 'Carol'，向 page#20 下降 - 在 page#20 叶子页内顺序查找直到找到 'Bob'

14. B+ 树维护操作详解

B+ 树在磁盘上以页为单位组织。每次插入或删除都可能触发页的分裂或合并，以维持树的平衡性和页的空间利用率。

14.1 正常插入：乐观插入

当目标叶子页有足够空间时，InnoDB 执行乐观插入（Optimistic Insert）：

只需对叶子页加写锁
在页内找到合适位置，将记录写入空闲区
更新 Page Header 中的空闲指针和记录计数

插入 id=4（目标叶子页仍有空闲空间）：

          Root [7]
          /       \
     Page#2       Page#3
   [1,3,5,_]    [7,9,11,_]  ← _ 表示空槽

插入 id=4 后（仅修改 Page#2，无结构变化）：

          Root [7]
          /       \
     Page#2       Page#3
   [1,3,4,5]    [7,9,11,_]

乐观插入是最常见的情况，只涉及 1 次页修改，代价最小。

14.2 叶子页分裂：悲观插入

当目标叶子页已满，InnoDB 执行悲观插入（Pessimistic Insert），触发叶子页分裂（Leaf Page Split）。

示例：向已满的 Page#4 插入 id=13（每页最多 4 条记录）

分裂前：

              Root [5 | 9]
             /      |      \
         Page#2   Page#3   Page#4
       [1,2,3,4] [5,6,7,8] [9,10,11,12]
           ↔          ↔           ↔        ← 双向链表

Page#4 已满，无法直接写入 id=13，触发分裂：

 Step 1: 申请新页 Page#5

 Step 2: 将 Page#4 的记录从中点分裂（各约 50%）
         Page#4 保留：[9, 10]
         Page#5 获得：[11, 12]    ← 新记录 13 也写入 Page#5

 Step 3: Page#4 ↔ Page#5 ↔ ... 双向链表重新串联

 Step 4: 将 Page#5 的最小键 11 上推到父页 Root
         Root 插入新分隔键 11，并增加指向 Page#5 的子指针

分裂后：

              Root [5 | 9 | 11]
             /    |      |      \
         Page#2  Page#3  Page#4  Page#5
       [1,2,3,4][5,6,7,8][9,10] [11,12,13]
           ↔         ↔       ↔         ↔

代价统计： 至少涉及 3 次页修改（旧叶子页 + 新叶子页 + 父页），加上 WAL 日志写入。

14.3 根页分裂：树长高

当分裂引发的上推键需要插入一个已满的父页，分裂向上级联。最极端的情况是根页也需要分裂，此时树的高度增加 1 层。

示例（内部节点最多 2 个键 / 3 个子指针）：

初始树，Root 已满：

          Root [3 | 7]
         /      |      \
     Page#2   Page#3  Page#4
     [1,2]   [3,4,5,6]  [7,8]
       ↔           ↔       ↔

向 Page#4[7,8] 插入 id=9，Page#4 已满：

 Step 1: Page#4 分裂 → Page#4=[7,8]，新建 Page#5=[9]
         上推分隔键 9 → 需要插入 Root[3|7]

 Step 2: Root 已满（2 个键），Root 也必须分裂：
         Root 当前 keys=[3, 7]，加入 9 后需承载 [3, 7, 9]
         取**中间键 7** 作为新根的唯一键
         左子树（InternalA）承载：keys=[3]，子页=[Page#2, Page#3]
         右子树（InternalB）承载：keys=[9]，子页=[Page#4, Page#5]

 Step 3: 创建新根 New Root，只含一个键 7，指向 InternalA 和 InternalB

根页分裂后（树高从 2 变为 3）：

                  New Root [7]
                 /             \
        InternalA [3]       InternalB [9]
          /       \            /       \
      Page#2    Page#3    Page#4    Page#5
      [1,2]   [3,4,5,6]   [7,8]      [9]
        ↔           ↔        ↔         ↔

根页分裂的关键特点：

普通叶子分裂不改变树高
只有根页分裂才使树增高一层
根分裂触发频率极低，但每次代价最高（需修改从根到叶的所有涉及页）

14.4 顺序插入的分裂优化

自增主键（AUTO_INCREMENT）场景下，数据总追加在最右侧叶子页。InnoDB 对此做了专门优化：

普通分裂（随机插入）——对半分：

 Page#4 分裂前（已满）：
 ┌────────────────────────────────┐
 │  key5 │ key6 │ key9 │ key14   │
 └────────────────────────────────┘

 分裂后：
 ┌──────────────────┐   ┌────────────────────────┐
 │  key5 │ key6     │   │  key9 │ key14 │ newKey  │
 └──────────────────┘   └────────────────────────┘
   旧页约 50% 满             新页约 50% 满

顺序末尾分裂（InnoDB 的优化）——旧页保满：

InnoDB 检测到插入位置是当前页的最后一条记录之后（即顺序追加），则把新记录单独写入一个全新空页，旧页不动：

 Page#4 分裂前（已满，插入点在最右端）：
 ┌────────────────────────────────┐
 │  9 │ 10 │ 11 │ 12             │ ← 全满 100%
 └────────────────────────────────┘

 顺序分裂后：
 ┌────────────────────────────────┐   ┌──────────────┐
 │  9 │ 10 │ 11 │ 12             │ ↔ │  13          │
 └────────────────────────────────┘   └──────────────┘
   旧页仍 100% 满                       新页只有 1 条（后续会继续填满）

这就是推荐使用自增主键的核心原因：页利用率高、极少出现"半空页"碎片、整体写入效率更好。

14.5 删除与页合并

阶段一：软删除

InnoDB 删除记录时不会立即回收页内空间，而是将记录头中的 delete_mask 置为 1：

 删除前：[id=9, delete_mask=0, ...数据...]
 删除后：[id=9, delete_mask=1, ...数据...]  ← 记录仍物理存在，但对查询不可见

阶段二：Purge 线程异步回收

后台 Purge 线程在确认所有活跃事务都不再需要该版本后（MVCC 可见性保证），真正清除记录，将其空间加回页内 free list。

页合并的触发条件：

当一张页的占用率降到 MERGE_THRESHOLD（默认 50%）以下时，InnoDB 尝试将该页与相邻兄弟页合并。

页合并示例（每页最多 4 条记录，合并阈值 = 2 条）：

合并前：

           Root [5 | 8]
          /      |      \
      Page#2   Page#3  Page#4
      [1,2,3]  [5,6]   [8,9]
        ↔         ↔        ↔

Purge 线程清除 Page#4 中已软删除的 id=9，Page#4 只剩 [8]（1 条 < 阈值 2），触发合并：

 检查左兄弟 Page#3：有 2 条记录 [5,6]
 合并后总计 3 条 [5,6,8]，未超过最大容量 4 → 可以合并

 Step 1: 将 Page#4 的记录 [8] 移入 Page#3
         Page#3 变为 [5,6,8]

 Step 2: Page#4 标记为空闲页，可被复用

 Step 3: 父页 Root 移除分隔键 8 和指向 Page#4 的子指针

合并后：

           Root [5]
          /       \
      Page#2     Page#3
      [1,2,3]   [5,6,8]
        ↔            ↔

若左兄弟太满无法合并，则执行"借位（记录重分配）"：

 Page#3=[5,6,7,8]（已满），Page#4=[9]（低于阈值）

 不能合并（合并后 5 条 > 最大 4），改为借位：
   从 Page#3 末尾借走 key=8 给 Page#4
   Page#3 → [5,6,7]
   Page#4 → [8,9]
   同时更新父页中 Page#4 对应的分隔键（由 9 改为 8）

14.6 分裂与合并对性能的影响

分裂的主要影响：

每次分裂涉及多页修改，会产生更多 WAL（Redo Log）写入，加剧写放大
分裂后两页各约 50% 满，存储利用率短期下降
若该表有多个二级索引，每次主键分裂还会触发各二级索引的同步维护
高并发写入时，分裂涉及的页范围更广，锁竞争加剧

合并的主要影响：

需要同时锁住两个相邻叶子页和父页，持锁窗口相对较长
频繁删除触发的合并也会在所有二级索引上产生级联维护

工程最佳实践：

问题	根本原因	建议做法
页分裂频繁，写入慢	随机主键导致插入分散在所有页	使用自增主键或趋势递增的雪花 ID
空间利用率低，碎片多	随机分裂后页长期处于半满状态	定期 `OPTIMIZE TABLE` 重建 B+ 树
二级索引写放大明显	索引过多，每次写要维护所有索引	精简索引，删除重复和低选择性索引
删除后表空间不收缩	软删除 + Purge 机制，物理空间滞后释放	监控 `information_schema.INNODB_TABLESPACES`，适时 Rebuild
合并引发锁竞争	批量随机删除触发大量合并	大批量删除改为分批次执行，错峰进行