03. B+ 树索引原理

1. 为什么需要 B+ 树

1.1 磁盘 I/O 问题

数据库的数据存储在磁盘上，磁盘 I/O 是性能瓶颈。B+ 树的设计目标是减少磁盘 I/O 次数。

磁盘读取特点：
- 顺序读：快（磁盘预读）
- 随机读：慢（磁头寻道时间 ~ 10ms）
- 最小读取单位：页（Page，通常 4KB/8KB/16KB）

B+ 树通过让树尽可能"矮胖"，减少随机 I/O：
  树高 3 → 最多 2 次随机 I/O（根→叶子）
  树高 4 → 最多 3 次随机 I/O
  
对于 2000 万行数据（InnoDB，16KB 页）：
  每页存储约 1170 个 key（假设 key 为 8B + 指针 6B）
  树高 3 可存储：1170 × 1170 × 16 ≈ 2190 万行

1.2 B-Tree vs B+Tree

B-Tree：
       [10, 20]
      /   |    \
    [5,8] [15,18] [25,30]
    数据存储在所有节点（内部节点也存数据）
    问题：内部节点大，树变高

B+Tree（数据库标准）：
       [10, 20]              ← 内部节点：只存 key 用于导航
      /   |    \
    [5,8] [15,18] [25,30]  → 叶子节点：存 key + 数据，且叶子间有链表
    叶子节点通过链表连接，范围查询高效

2. InnoDB 索引结构

2.1 聚簇索引（Clustered Index）

聚簇索引就是表本身。数据行按主键顺序存储在 B+ 树的叶子节点中。

聚簇索引（主键索引）：

       [PK 节点]
          │
    ┌─────┼─────┐
    ↓     ↓     ↓
 [叶子] [叶子] [叶子]  ← 叶子节点存储完整的行数据
    │     │     │
  行数据  行数据  行数据
  
MySQL InnoDB 表必须有主键：
  1. 用户定义主键 → 使用该主键
  2. 无显式主键 → 选第一个非空唯一索引
  3. 无唯一索引 → 隐式生成 6B 行 ID

2.2 非聚簇索引（Secondary Index）

叶子节点不存数据，只存主键值。查询时需要"回表"到聚簇索引查找完整行。

二级索引（name 列上的索引）：

       [Alice]
          │
    ┌─────┼─────┐
    ↓     ↓     ↓
 [Alice] [Bob] [Cathy]  ← 叶子存储：name + PK
    │       │      │
    1       2      3     ← 存储的是主键值（回表指针）
    
SELECT * FROM users WHERE name = 'Alice';
  → 查二级索引找到 name='Alice' → 得到 PK=1
  → 回表查聚簇索引 → 找到 PK=1 的完整行
  → 两次索引查找（二级 → 聚簇）

2.3 覆盖索引（Covering Index）

-- 索引：INDEX idx_name_age(name, age)

-- ✅ 覆盖索引（无需回表）
SELECT name, age FROM users WHERE name = 'Alice';
  → 索引中已有 name 和 age 两列 → 直接返回

-- ❌ 需回表（索引不含 phone）
SELECT name, age, phone FROM users WHERE name = 'Alice';
  → 索引中找到 name → 得到 PK → 回表查 phone

覆盖索引是数据库性能优化的"银弹"之一——通过让查询所需列都在索引中，避免回表。

3. 复合索引与最左前缀

3.1 最左前缀法则

CREATE INDEX idx_abc ON users(a, b, c);

-- ✅ 可用索引：
WHERE a = 1
WHERE a = 1 AND b = 2
WHERE a = 1 AND b = 2 AND c = 3
WHERE a = 1 ORDER BY b           -- a 过滤，b 排序
WHERE a = 1 AND b > 2 AND c = 3  -- a、b 用索引，c 不走索引（b 是范围）

-- ❌ 不可用索引：
WHERE b = 2                -- 缺少最左列 a
WHERE a = 1 AND c = 3      -- b 缺失（中间断裂），c 无法使用
WHERE a > 1 AND b = 2      -- a 是范围后 b 不用索引（部分引擎优化除外）

3.2 索引列顺序设计

复合索引列顺序原则：
1. 等值查询列放前面（=）
2. 排序列次之（ORDER BY）
3. 范围查询列放最后（>, <, BETWEEN）

示例：
  查询：WHERE type = 'A' AND status = 1 AND created_at > '2024-01-01' ORDER BY id
  索引：(type, status, created_at) 或 (type, status, id)
  
  如果 created_at 过滤性极强：
    (type, created_at) 可能更优

4. 索引失效场景

5. 索引设计原则

1. 为 WHERE、JOIN、ORDER BY 列建索引
2. 区分度高的列更适合做索引（唯一值 / 总行数 ≈ 1）
3. 控制索引数量（写性能随索引数下降）
4. 优先覆盖索引（减少回表）
5. 避免冗余索引（(a,b) 和 (a) 冗余）
6. 索引字段尽量小（INT 优于 VARCHAR(255)）
7. 利用 EXPLAIN 验证索引使用

延伸阅读

• 查询优化与执行计划
• MySQL InnoDB 存储引擎