个人学习站

深色模式

01 · 索引与 B+ 树 ​

数据库最核心的一篇。懂了这篇，80% 的 SQL 优化题都能推出来。

一句话本质 ​

索引是为了减少磁盘 IO 次数而额外维护的一份有序结构——用"多占空间 + 写变慢"，换"读变快"。

生活类比：图书馆的索引柜 ​

没有索引：你要找"作者是余华的书"，只能从第一个书架翻到最后一个。100 万本书，翻到天黑。

有索引：索引柜里有一叠卡片，按作者名排好序，每张卡片写着"余华 → 3 排 2 号架"。

  • 找"余华"：直接在卡片里二分，几秒定位 → 快
  • 但每次进新书，都要多做一张卡片 → 写变慢
  • 卡片柜本身占地方 → 多占空间

这就是索引的全部本质。所有细节都是这句话的展开。

核心机制 ​

一、为什么是 B+ 树（把三个候选都比一遍） ​

核心约束：磁盘 IO 次数 = 树高。一次 IO 约 10ms（机械盘），必须把树高压到最低。

候选 1：哈希表
  ✅ 等值查询 O(1)
  ❌ 不支持范围查询（age > 20 得全扫）
  ❌ 不支持排序
  ❌ 不支持最左前缀
  > 淘汰（只能做辅助索引）

候选 2：红黑树（二叉）
  1000 万行 > 树高 ≈ log₂(1000万) ≈ 24 层
  > 24 次磁盘 IO × 10ms = 240ms
  > 淘汰

候选 3：B 树（多叉）
  一个节点存几百个键 > 树高 3~4 层
  ✅ 树高低
  ❌ 数据存在所有节点上（包括非叶子），一个节点能存的键变少
  ❌ 范围查询要在树上反复上下跳

候选 4：B+ 树
  ✅ 数据只在叶子节点，非叶子只存索引 > 一个节点能存更多键 > 树高更低
  ✅ 叶子节点用双向链表串起来 > 范围查询直接顺序扫，不用回到根
  ✅ 每次查询都要走到叶子 > IO 次数稳定（B 树可能提前命中，也可能不）
  > 胜出

二、B+ 树的结构（InnoDB，页大小 16KB） ​

← 左右滑动看完整图 →[ 10 | 30 ][ 1 | 5 ][ 10 | 20 ][ 30 | 50 ]key=1 整行key=10 整行key=30 整行根：键 + 子指针分支：键 + 子指针叶子：整行数据< 1010 ~ 29≥ 30叶子之间是双向链表 → 范围查询顺着链表扫，不用回到根
非叶子节点只存「键 + 子指针」，一页能塞下上千个键，所以 2000 万行的表树高也只有 3 层；数据全在叶子，叶子之间用双向链表串起来——范围查询顺着链表扫，不用回到根。

一个节点就是一页（16KB）。根和分支只存「键 + 子节点指针」，一页能放约 1170 个键，所以树很矮；真正存整行数据的只有叶子，叶子之间用双向链表相连，范围查询顺着链表扫就行，不用回到根。

树高能压到多低（算一下，面试常问）：

假设：
  页大小 16KB
  主键 bigint（8 字节）+ 页指针（6 字节）= 14 字节
  一个非叶子节点能存：16KB / 14B ≈ 1170 个键
  一行数据约 1KB > 一个叶子节点能存约 16 行

三层 B+ 树能存多少行？
  第 1 层（根）：1 个节点
  第 2 层：1170 个节点
  第 3 层（叶子）：1170 × 1170 ≈ 137 万个节点
  总行数：137 万 × 16 ≈ 2200 万行

结论：2000 万行的表，树高只有 3 层 > 3 次 IO

这就是 B+ 树的核心价值：把 24 次 IO 压到 3 次。

三、聚簇索引 vs 二级索引（必考） ​

聚簇索引（主键索引）：

叶子节点直接存"整行数据"
  [主键=1 | 整行数据] > [主键=2 | 整行数据] > ...

一张表只有一个聚簇索引（因为数据只能按一种方式物理组织）

二级索引（辅助索引）：

叶子节点存"索引列 + 主键值"
  [name='张三' | 主键=5] > [name='李四' | 主键=8] > ...

可以有多个

回表：用二级索引查到主键值后，还要再去聚簇索引查一次完整数据。

SELECT * FROM user WHERE name = '张三';

① 走 name 索引，找到 name='张三' 的记录，拿到主键 id=5
② 拿 id=5 去聚簇索引查，拿到整行
> 两次 B+ 树查找 = 两次（可能更多）IO

这就是"回表"，也是"为什么 SELECT * 比 SELECT 具体列慢"的原因之一

覆盖索引：如果查询的列全都在索引里，就不用回表。

索引 (name, age)
SELECT name, age FROM user WHERE name = '张三';
> name 和 age 都在索引里，直接返回，不回表 ✅

SELECT name, age, email FROM user WHERE name = '张三';
> email 不在索引里，必须回表 ❌

这是最重要的优化手段之一：把常用查询的列做成联合索引，实现"索引覆盖"。

四、最左前缀原则 ​

联合索引 (a, b, c) 的排序方式是：先按 a 排，a 相同再按 b 排，b 相同再按 c 排。

索引里的顺序：
(1,1,1) (1,1,2) (1,2,1) (1,2,2) (2,1,1) (2,1,2) ...
 ^a    ^b    ^c

所以能用的查询：

查询条件能用索引吗用到几列
a=1✅a
a=1 AND b=2✅a, b
a=1 AND b=2 AND c=3✅a, b, c
b=2❌完全用不了（不知道 a 就没法定位）
a=1 AND c=3⚠️只用 a，c 用不上（b 断了）
a>1 AND b=2⚠️只用 a（范围查询后面的列失效）

**"范围查询后面的列失效"**是高频考点：因为 a > 1 之后，a 有多个值，b 在每个 a 内部有序但整体无序，无法再用 b 做定位。

例外：MySQL 5.6+ 的"索引下推"（ICP）可以在索引上过滤 b，减少回表次数，但仍不能用于定位。

五、索引失效的常见原因 ​

① 对索引列做函数/运算
   WHERE YEAR(create_time) = 2026     ❌
   WHERE create_time >= '2026-01-01'  ✅

② 隐式类型转换
   索引是 varchar，却写 WHERE phone = 13800138000（数字）  ❌
   > 数据库会把每行的 phone 转成数字比较，等于对列做函数

③ 前导模糊匹配
   WHERE name LIKE '%三'   ❌（无法二分，因为不知道从哪开始）
   WHERE name LIKE '张%'   ✅

④ OR 连接的列没有都建索引
   WHERE a=1 OR b=2  > 如果 b 没索引，全表扫

⑤ 区分度太低
   性别字段只有 2 个值 > 索引扫描的行数接近全表，优化器会放弃索引

⑥ 使用了 != 、NOT IN、IS NOT NULL（部分情况）
   > 因为要扫描的行太多，优化器判断不如全表扫

六、什么时候不该建索引 ​

① 表很小（几百行）> 全表扫更快
② 写多读少 > 每次写都要维护索引
③ 区分度极低 > 索引用不上
④ 频繁更新的列 > 索引维护成本高
⑤ 已经有更合适的联合索引（避免冗余索引）

为什么这么设计 ​

反事实 1：如果页大小是 4KB 而不是 16KB ​

一个节点能存的键少了 4 倍，树高增加。按上面的计算，2000 万行可能要 4 层而不是 3 层——多一次 IO，性能下降 30%+。

16KB 是权衡：太小树高增加，太大一次 IO 读的数据用不完（浪费带宽）、且 Buffer Pool 管理粒度变粗。

反事实 2：如果数据也存在非叶子节点（B 树） ​

一个非叶子节点原本能存 1170 个键，现在要存"键 + 数据"，假设数据 1KB，那一个节点只能存 16 个键——树高会暴增。

B+ 树把数据全部下沉到叶子，正是为了让非叶子节点"尽可能多地存键"，从而压低树高。

反事实 3：如果没有索引 ​

1000 万行的表，WHERE id = 123 要全表扫描：读 1000 万行 × 1KB = 10GB 数据。即使顺序读，也要几秒到几十秒。

有了索引：3 次 IO，约 30ms。差了 1000 倍。

面试怎么问 ​

Q：为什么用 B+ 树而不是 B 树？

三点：① 数据只在叶子 > 非叶子能存更多键 > 树高更低；② 叶子有链表 > 范围查询直接顺序扫；③ 每次查询都到叶子 > IO 次数稳定可预测。

Q：为什么不用红黑树/哈希？

红黑树树高太高（24 层 = 24 次 IO）；哈希不支持范围查询、排序、最左前缀。

Q：什么是回表？怎么避免？

二级索引叶子只存主键，查其他列要再回聚簇索引查一次。避免方式：覆盖索引（把要查的列都放进索引）。

Q：什么是聚簇索引？

叶子节点存整行数据的索引。一张表只有一个（通常是主键）。InnoDB 必须有聚簇索引——没主键就用唯一非空索引，再没有就生成隐藏的 row_id。

Q：联合索引的最左前缀原则？

索引按 (a,b,c) 顺序排列，所以必须从 a 开始用。跳过 a 直接用 b 用不了；a 用了范围查询后，b、c 只能用于过滤（索引下推），不能用于定位。

Q：索引越多越好吗？

不是。每个索引都要占空间，且每次 INSERT/UPDATE/DELETE 都要维护所有索引。写多的表，索引会显著拖慢写入。

追问链：

索引为什么快？
  > 因为减少了磁盘 IO
    > 为什么 B+ 树 IO 少？（树高低，3 层）
      > 为什么树高低？（多叉 + 数据只在叶子）
        > 为什么不用 B 树？（数据占空间，节点存键少）
          > 为什么不用哈希？（不支持范围）
            > 二级索引查到主键后还要做什么？（回表）
              > 怎么避免回表？（覆盖索引）

和其他知识的连接 ​

自测 3 问 ​

Q1：2000 万行的表，为什么 B+ 树只有 3 层？

点开看答案

按 16KB 页算：

  • 非叶子节点：每个键 + 指针约 14 字节 > 一页能放 16384/14 ≈ 1170 个键。
  • 叶子节点：一行约 1KB > 一页能放约 16 行。

三层结构：

  • 第 1 层（根）：1 个节点，1170 个分支
  • 第 2 层：1170 个节点，共 1170 × 1170 ≈ 137 万 个分支
  • 第 3 层（叶子）：137 万个叶子节点 × 16 行 ≈ 2200 万行

所以 2000 万行确实只要 3 层，查任意一行最多 3 次 IO。

注意：这是"主键 bigint + 行 1KB"的估算。行越大、主键越长，能存的行数越少。

Q2：为什么 WHERE a > 1 AND b = 2 用不上联合索引 (a,b) 的 b？

点开看答案

因为索引的排序是"先按 a，再按 b"。

a > 1 会命中多个 a 值（比如 a=2,3,4...）。在每个 a 内部，b 是有序的；但跨 a 的时候，b 整体无序。

a=2: b=1,2,3
a=3: b=1,2,3

要找"b=2"，在 a=2 里有一个，a=3 里有一个，a=4 里还有一个……必须把每个 a 都扫一遍，无法像等值查询那样一次定位。

所以 b 只能用于"过滤"（索引下推，减少回表），不能用于"定位"（缩小扫描范围）。

对比：a = 1 AND b = 2 能精确定位到唯一位置，因为 a 是等值，b 在 a=1 内部有序。

Q3：为什么 WHERE phone = 13800138000 会让 varchar 索引失效？

点开看答案

因为隐式类型转换。

MySQL 在比较 varchar 和数字时，会把字符串转成数字（而不是把数字转成字符串）。这个转换作用在每一行上：

等价于：WHERE CAST(phone AS SIGNED) = 13800138000

一旦对索引列用了函数，B+ 树的有序性就被破坏了——数据库不知道 CAST(phone) 的结果在索引里是什么顺序，只能全表扫描。

正确写法：WHERE phone = '13800138000'（加引号）。

这个坑非常常见，因为很多 ORM 或前端传参时类型不对，表面看不出来。

类比失效处 / 易错点 ​

  • "卡片柜"类比会让人以为索引和数据是两份独立的拷贝。聚簇索引的叶子就是数据本身，只有二级索引才是"另存一份"。
  • "索引让查询变快"不绝对。区分度低（如性别）或要返回大量行时，优化器会主动放弃索引——全表扫可能更快。
  • B+ 树的"+"不是"加强版"的意思，是指"数据都在叶子层"这个结构差异。
  • 不是所有引擎都有聚簇索引。MyISAM 的索引和数据完全分离（叶子存的是数据地址），所以它没有聚簇索引。
  • 索引下推（ICP）不是"能用于定位"。它只是把过滤条件下推到索引层，减少回表次数，不改变"范围查询后列失效"这个事实。
  • LIKE '张%' 能用索引，LIKE '%张' 不能——因为前者知道从哪开始找，后者不知道。

✅ 验收清单 ​

  • 能算出"2000 万行的表 B+ 树只有 3 层"，并说清计算过程
  • 能说出 B+ 树相比 B 树的三个优势（数据下沉、叶子链表、IO 稳定）
  • 能说出为什么不用红黑树（树高）和哈希（范围查询）
  • 能解释聚簇索引和二级索引的区别，以及"回表"是什么
  • 能用"索引覆盖"举一个具体例子（写出索引和 SQL）
  • 能默写最左前缀原则的 5 种查询场景，并解释"范围查询后列失效"
  • 能说出至少 4 种索引失效的原因，并给出正确写法
  • 能说出"什么时候不该建索引"（至少 3 种）
  • 合上书，用自己的话讲 3 分钟，中途不卡壳