跳到主要内容

索引与 B+ 树

为什么用 B+ 树​

对比三种候选结构，答题要落在磁盘 IO 次数上：

结构为什么不选
哈希表只能等值查询，不支持范围查询和排序；哈希冲突退化
二叉搜索树 / 红黑树树高太大。100 万数据红黑树高约 20，意味着最多 20 次磁盘 IO
B 树非叶子节点也存数据，导致单页能放的键变少、树更高；且叶子节点无链表，范围查询要回溯中序遍历

B+ 树的两个关键设计：

  1. 非叶子节点只存键和指针，不存数据 —— 单个 16KB 页能放更多键，树高更矮。按主键 bigint（8 字节）+ 指针（6 字节）算，一页约放 1170 个键；叶子页按一行 1KB 算放 16 行。那么三层 B+ 树能存 1170 × 1170 × 16 ≈ 2190 万行。三层树高意味着查任意一行最多 3 次 IO，且根节点常驻内存，实际只有 1～2 次。这是面试最想听到的量化回答。
  2. 叶子节点用双向链表串联 —— 范围查询（BETWEEN、>、ORDER BY）定位到起点后顺序扫链表即可，不需要回到上层。

聚簇索引与回表​

InnoDB 的数据就存在主键索引的叶子节点里，这棵树叫聚簇索引（clustered index）。没有显式主键时，InnoDB 选第一个非空唯一索引；都没有就生成 6 字节隐藏列 row_id。

二级索引（辅助索引）的叶子节点存的是索引列 + 主键值，不是整行。所以 SELECT * FROM t WHERE name = 'x'：

  1. 走 name 索引树找到主键值
  2. 拿主键值回聚簇索引再查一次完整行 —— 这一步叫回表

覆盖索引就是消除回表：如果查询的列全部包含在索引里，二级索引树上就能拿到结果。SELECT id, name FROM t WHERE name = 'x' 走 name 索引时不回表，EXPLAIN 的 Extra 显示 Using index。

提示

把 SELECT * 改成只查需要的列，常常能直接把回表消掉。这是成本最低的优化手段之一。

最左前缀原则​

联合索引 (a, b, c) 的 B+ 树是先按 a 排、a 相同再按 b 排、b 相同再按 c 排。所以：

查询能用到
WHERE a = 1a
WHERE a = 1 AND b = 2a, b
WHERE a = 1 AND c = 3只有 a（b 断了，c 用不上索引查找，但 5.6+ 可做索引下推）
WHERE b = 2用不上（除非能覆盖索引做全索引扫描）
WHERE a > 1 AND b = 2a 走范围，b 用不上 —— 范围查询之后的列失效

推论：建联合索引时，等值查询的列放前面，范围查询的列放最后。

索引失效的常见情形​

  • 对索引列做运算或用函数：WHERE YEAR(created_at) = 2026 失效，改写成 WHERE created_at >= '2026-01-01' AND created_at < '2027-01-01'
  • 隐式类型转换：phone 是 varchar 却写 WHERE phone = 13800138000，MySQL 会把列转成数字再比较，等于对列用了函数 → 失效。反过来 int 列传字符串不失效（转的是常量）
  • 前导模糊匹配：LIKE '%abc' 失效，LIKE 'abc%' 可用
  • OR 连接的条件有一侧无索引：整条失效，改用 UNION
  • !=、NOT IN、IS NOT NULL：不一定失效，取决于优化器估算的选择性
  • 优化器主动放弃：当估算要回表的行数占比过高（经验阈值约 20～30%）时，全表扫描比「走索引 + 大量随机回表」更快，优化器会选全表扫。这不是「失效」而是正确决策，用 EXPLAIN 看 rows 和 filtered 验证

索引下推（ICP）​

MySQL 5.6 引入 Index Condition Pushdown。联合索引 (name, age) 执行 WHERE name LIKE '张%' AND age = 20：

  • 无 ICP：用 name 过滤出所有「张」开头的主键，逐个回表，回表后再判断 age
  • 有 ICP：在索引层就把 age = 20 判断掉，只对真正匹配的行回表

效果是减少回表次数，EXPLAIN 的 Extra 显示 Using index condition。

最后于 更新