极客教程

Appearance

共 2,554 字预计阅读约 9 分钟

MySQL 索引原理：为什么是 B+ 树 ​

更新时间：2026-08-24。本文是本站数据库域第一篇，回答一个最基础也最关键的问题：InnoDB 为什么用 B+ 树做索引，而不是红黑树、B 树或哈希表？

零、先建立全局认识 ​

一次带索引的查询，是用户态 → 存储引擎 → 磁盘三层协作的结果：

plantuml diagram

核心问题速览表：

问题一句话答案对应章节
索引到底是什么？一种把"全表扫描"降为"按路径查找"的有序数据结构一
为什么不是红黑树/B 树？红黑树树高太高、B 树叶子不串链表且页利用不极致，都做不了"磁盘友好 + 范围查询"二
B+ 树好在哪？高扇出压低树高、叶子链表面向顺序扫描、非叶子只存键三
聚簇 vs 二级索引？聚簇叶子存整行，二级叶子存主键（可能回表）四
为什么最左前缀会失效？B+ 树按复合索引的列顺序排序，跳过最左列就失去有序性五
如何验证？EXPLAIN 的 type / key / rows / Extra六

一、没有索引时发生了什么 ​

假设一张 1000 万行的表，行大小约 140 字节，InnoDB 默认页大小 16KB（16384 字节）。

  • 每页约能装 16384 / 140 ≈ 117 行
  • 全表需要 10_000_000 / 117 ≈ 85_000 页
  • 主键等值查询时，最坏情况要扫描全部 8.5 万页（页在磁盘上还要按 B+ 树走，InnoDB 中数据本身就是按主键组织的聚簇结构，此处为直观对比先简化）

数据量增长 vs 全表扫描成本：

数据量页数(16KB/页, 约140B/行)顺序读耗时(约1GB/s)随机读耗时(约1万IOPS, 每页1次IO)
1 万行~86 页~1.4ms~8.6ms
100 万行~8 500 页~136ms~0.85s
1000 万行~85 000 页~1.36s~8.5s
1 亿行~850 000 页~13.6s~85s

结论：数据量每涨一个数量级，全表扫描成本线性上涨；而走索引时，成本只与树高相关，与数据量几乎无关。这就是索引存在的意义——把 O(N) 降到 O(log N)，且这里的 log 底数非常大（几千），实际树高只有 3~4 层。

二、索引数据结构演进链 ​

理解 B+ 树为什么是"最终答案"，最好的方式是顺着演进链走一遍，看每一代结构为什么被淘汰。

1. 二叉查找树（BST） ​

plantuml diagram
  • 左子树 < 根 < 右子树，插入按序数据会退化成链表（最坏 O(N)）
  • 需要自平衡 → 引出 AVL / 红黑树

2. AVL 平衡二叉树 ​

  • 严格平衡：任意节点左右子树高度差 ≤ 1
  • 1000 万数据树高 log2(10_000_000) ≈ 24 层
  • 问题：树高 24 意味着最坏 24 次磁盘 IO，每次 IO 毫秒级，太慢

3. 红黑树 ​

  • 弱平衡（最长路径不超过最短路径 2 倍），插入删除旋转更少
  • 但树高仍是 ~2 * log2(N)，对磁盘场景没有本质改善
  • 它更适合内存中的 std::map、Linux 内核 CFS 调度器红黑树——内存访问是纳秒级，树高影响不大

4. B 树（多叉平衡树） ​

关键转变：一个节点不再只存一个键，而是存一组键（数组/页）。节点（页）越大，能装的键越多，树就越矮。

  • 所有节点都既存键又存数据/指针
  • 树高降到 3~4 层，一次查找 3~4 次 IO

5. B+ 树：最终选择 ​

B+ 树在 B 树基础上做了两个关键改造：

改造内容收益
① 非叶子节点只存键（不存数据/行指针）一个 16KB 页能装约 1000 个键扇出更大 → 树更矮
② 叶子节点串成双向链表范围查询从第一个命中叶子开始顺序遍历随机 IO → 顺序 IO

树高估算（为什么 3 层就够用）：

参数数值
页大小16KB
索引键（如 8 字节 bigint + 6 字节页指针）约 14B
每页可存键数（扇出 fanout）16384 / 14 ≈ 1170，工程上按约 1000 估算
第 1 层（根）覆盖约 1000 个指针
第 2 层覆盖1000 × 1000 = 100 万
第 3 层覆盖1000 × 1000 × 1000 = 10 亿

核心数字：树高 3 层 ≈ 支撑 10 亿行数据，即一次主键查询最坏只有 3 次磁盘 IO（且 root 页常驻内存，实际 2 次）。这就是 B+ 树最核心的竞争力。

数据结构横向对比：

结构树高(1000万数据)节点内数据范围查询磁盘 IO结论
二叉搜索树最坏 N 层（退化）1 键需中序遍历不可控淘汰
AVL 树~24 层1 键需中序遍历~24 次淘汰
红黑树~48 层1 键需中序遍历~48 次内存场景适用
B 树3~4 层键+数据中序遍历，跨层跳3~4 次过渡方案
B+ 树3~4 层非叶子只存键叶子链表顺序扫3~4 次，且多为顺序最终选择

三、B+ 树为什么是磁盘上的最优解 ​

1. 磁盘的最小读写单位是页 ​

  • 磁盘 IO 以"块/页"为单位，InnoDB 页默认 16KB
  • 无论只取 1 字节还是 1000 字节，一次 IO 的成本相同（寻道+旋转+传输）
  • 所以数据结构要尽量"一次 IO 干更多事"：一个页装尽可能多的键 → 就是扇出最大化

2. B+ 树的三个磁盘友好特性 ​

plantuml diagram
特性说明收益
高扇出非叶子只存键不存数据，页装更多键树高恒定 3~4 层，IO 次数恒定
叶子链表叶子按序串成双向链表范围查询 / ORDER BY 变成顺序扫描
局部性相邻键大概率落在同一页或相邻页利用磁盘预读（readahead），顺序 IO 比随机 IO 快 1~2 个数量级

3. 与本站底层知识的衔接 ​

B+ 树之所以"为磁盘而生"，底层依据正是本站存储域的量化结论：

本站文档与本主题的关系
存储设备性能随机读 vs 顺序读差 1~2 个数量级 → 索引设计目标是把随机 IO 变顺序 IO
Direct IO vs 页缓存数据库查询走页缓存，缓存命中时 B+ 树路径 0 IO
I/O 完整链路每次磁盘 IO 经过页缓存 → 块层 → 设备层的内核路径
缓存组织与访问局部性原理同样支撑"相邻键同页"的设计

一句话：B+ 树把"数据量大 → IO 多"的矛盾，用"树矮 + 顺序扫描"两个手段化解，前者靠高扇出，后者靠叶子链表。

四、InnoDB 的两种索引 ​

1. 聚簇索引（主键索引） ​

  • 叶子节点直接存整行数据，数据即索引
  • 每张表只能有一个（InnoDB 没有主键时自动用唯一键/隐藏 rowid 建聚簇索引）
  • 插入按主键顺序组织 → 主键最好是自增的（顺序写），用 UUID 会导致页分裂与碎片

2. 二级索引（辅助索引） ​

  • 叶子节点存主键值，不存整行
  • 每张表可以建多个
  • 查询过程：先在二级索引 B+ 树定位到主键 → 回表到聚簇索引再查一次
plantuml diagram

3. 覆盖索引 ​

  • 查询所需列全部包含在某个索引中，则无需回表
  • Extra 显示 Using index，是查询优化的高性价比手段
  • 典型例子：SELECT id, name FROM t WHERE name = 'alice'，如果建了 (name, id) 复合索引，命中的就是覆盖索引

两种索引对比：

维度聚簇索引二级索引
叶子内容整行数据主键值
数量每表 1 个每表多个
查找方式一次索引树查找可能两次（索引树 + 回表）
覆盖查询天然覆盖需包含全部查询列

五、最左前缀原则与索引失效 ​

1. 复合索引的本质 ​

复合索引 (a, b, c) 的 B+ 树按 (a, b, c) 字典序整体排序：先比 a，a 相同再比 b，b 相同再比 c。

这决定了：能用到索引的查询必须从 a 开始。WHERE b = ? 或 WHERE c = ? 时，b/c 在整棵树上无序，只能退化为扫描。

2. 常见失效场景 ​

场景示例原因对策
违反最左前缀复合索引 (a,b)，查 WHERE b = 1b 在树中无序调整索引列顺序，或为 b 单独建索引
中间列跳过的范围(a,b,c)，查 WHERE a=1 AND c=2a 确定后 c 无序建 (a,c) 或 (a,b,c) 但用等值 b
隐式类型转换WHERE phone = 13800138000（phone 是 varchar）列上发生函数/转换，索引序被破坏保证类型一致 '13800138000'
列上函数运算WHERE YEAR(create_time) = 2026无法对函数结果用索引改写为 create_time BETWEEN '2026-01-01' AND '2026-12-31'
前缀模糊WHERE name LIKE '%abc'通配符在开头，无法确定起点改写为 LIKE 'abc%'（可用索引）
OR 连接WHERE a = 1 OR b = 2（无 b 索引）OR 任一分支走不了索引则全表拆成 UNION ALL，或补索引
负向查询WHERE status != 1（区分度低时）优化器评估全扫更便宜看 EXPLAIN 确认，必要时改写

3. 判断口诀 ​

  • 等值在前、范围在后：范围列之后的列用不上索引
  • 索引列不做任何加工：函数、运算、隐式转换都会让索引失效
  • 索引覆盖所有查询列：避免回表（Using index）

六、用 EXPLAIN 验证 ​

sql
EXPLAIN SELECT id, name FROM user WHERE name = 'alice'\G
text
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: user
   partitions: NULL
         type: ref
possible_keys: idx_name
          key: idx_name
      key_len: 102
          ref: const
         rows: 1
     filtered: 100.00
        Extra: Using index
字段关注点说明
typeconst > ref > range > index > ALLALL 即全表扫描，最需警惕
key实际用到的索引NULL 说明没用上
key_len使用的索引长度复合索引可判断用到哪一列（如 len=102 表示只用到了 name）
rows预估扫描行数越小越好，与真实量差异大可查统计信息（ANALYZE TABLE）
ExtraUsing index（覆盖）、Using index condition（下推）、Using filesort/Using temporary（优化点）出现 filesort/temporary 是明显的优化信号

七、索引使用原则速查 ​

  1. 主键选自增整数：顺序写入，避免页分裂碎片
  2. 区分度高的列优先：如用户 id 好过性别
  3. 复合索引列顺序：等值列在前，范围列在后；把复用率高的列放最左
  4. 控制索引数量：每个索引都是一棵 B+ 树，拖慢写入（页维护+日志），写多读少的表慎加
  5. 优先覆盖索引：把高频查询的列塞进索引，消灭回表
  6. 用 EXPLAIN 说话：任何索引优化都要用 type/key/rows/Extra 验证前后差异
  7. 警惕隐式转换与函数：WHERE id = '123' 对 varchar 主键同样触发转换

八、和本仓库其他文档的关系 ​

文档内容与本文的关系
存储设备性能随机/顺序 IO 量化B+ 树设计动机的底层依据
Direct IO vs 页缓存页缓存决策树索引查询走页缓存时的 IO 行为
I/O 完整链路read 的内核路径一次索引页读取的完整内核开销
缓存组织与访问局部性原理相邻键同页设计的理论来源
数据库域索引本域规划本文为数据库域第一篇

九、一句话总结 ​

InnoDB 选 B+ 树，是因为它是"磁盘友好"的最优解：高扇出把树高压到 3~4 层（千万级数据也就 2~3 次 IO），叶子链表把范围查询变成顺序扫描——两条都直接对着磁盘 IO 的成本结构优化；聚簇索引让"数据即索引"，二级索引用主键回表，复合索引按最左前缀生效，这些规则全部可以从 B+ 树的结构推导出来。

本文对你有帮助吗？