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 验证索引使用

6. B+ 树的动态维护

6.1 页分裂（Page Split）

当叶子节点存满（InnoDB 默认 16KB）且需要插入新 key 时，触发页分裂：

分裂前：
    [10, 20, 30, 40, 50]  ← 叶子已满（假设容量5）

插入 25：
    1. 申请新页
    2. 将后半部分（30,40,50）移至新页
    3. 原页保留 [10, 20, 25]
    4. 更新父节点指针

分裂后：
    原页: [10, 20, 25] ──→ 新页: [30, 40, 50]
                              ↑
                         父节点新增指针

分裂的成本：

• 申请新页（磁盘 I/O）
• 移动数据
• 更新父节点索引
• 极端情况：根节点分裂 → 树高 +1

6.2 页合并（Page Merge）

删除操作导致页填充率过低（InnoDB 默认 < 50%）时，与相邻兄弟页合并：

原页: [10, 20]  兄弟页: [30, 40, 50]
合并后: [10, 20, 30, 40, 50]
释放兄弟页空间

Why 50% 阈值？ 合并后立即再次分裂的概率过高，造成「抖动」。InnoDB 采用惰性合并策略，等待填充率进一步降低。

6.3 索引维护的写放大

每次 INSERT/DELETE/UPDATE 不仅修改数据页，还需维护索引页：

二级索引越多，写放大越严重。高写入场景应精简索引数量。

7. 索引选择性与基数

7.1 选择性计算

选择性 = 不同值数量 / 总行数

示例：
  users 表 100 万行
  gender 列：2 个不同值 → 选择性 = 2/1,000,000 = 0.000002 ❌
  email 列：100 万个不同值 → 选择性 = 1,000,000/1,000,000 = 1 ✅

选择性阈值：

• ≥ 0.1（10%）：适合建索引
• 0.01 - 0.1：中等，需结合实际查询模式
• < 0.01：通常不适合单独建索引（可考虑复合索引前缀）

-- 查看列的选择性
SELECT 
  COUNT(DISTINCT gender) / COUNT(*) AS gender_selectivity,
  COUNT(DISTINCT email) / COUNT(*) AS email_selectivity
FROM users;

7.2 基数（Cardinality）估算

InnoDB 通过采样估算索引基数，可能存在偏差：

-- 强制更新统计信息
ANALYZE TABLE users;

-- 查看索引基数
SHOW INDEX FROM users;

基数估算不准会导致优化器选错索引。高写入表建议定期 ANALYZE TABLE。

8. InnoDB Buffer Pool 与索引页

8.1 Buffer Pool 对索引的影响

查询命中 Buffer Pool → 纯内存操作，ns 级延迟
查询未命中 → 从磁盘加载页，~10ms 延迟

B+ 树高度 3 的查询：
  Buffer Pool 命中：3 次内存寻址 ≈ 300ns
  Buffer Pool 未命中：3 次磁盘 I/O ≈ 30ms
  相差 100,000 倍

8.2 预读与索引优化

InnoDB 的线性预读会在顺序扫描索引时提前加载后续页。覆盖索引的场景下，全表扫描退化为仅遍历叶子节点链表，配合预读可达到接近顺序读的性能：

-- 覆盖索引，无需回表
SELECT user_id, created_at 
FROM orders 
WHERE created_at > '2024-01-01';
-- 索引: INDEX idx_created_user(created_at, user_id) ✅

9. 实战索引设计案例

案例：电商订单查询优化

CREATE TABLE orders (
    id BIGINT PRIMARY KEY,
    user_id BIGINT NOT NULL,
    status VARCHAR(20),
    created_at TIMESTAMP,
    total_amount DECIMAL(10,2),
    INDEX idx_user_created (user_id, created_at)  -- 用户查看订单历史
);

-- 查询场景分析：
-- Q1: SELECT * FROM orders WHERE user_id = ? ORDER BY created_at DESC LIMIT 10
--     ✅ idx_user_created 完全覆盖

-- Q2: SELECT * FROM orders WHERE status = 'paid' AND created_at > ?
--     ❌ 索引不含 status，需全表扫描
--     修复: INDEX idx_status_created (status, created_at)

-- Q3: SELECT user_id, COUNT(*) FROM orders WHERE created_at > ? GROUP BY user_id
--     ❌ idx_user_created 中 created_at 不是最左前缀
--     修复: INDEX idx_created_user (created_at, user_id) —— 或保留两个索引

不存在「一个索引走天下」的方案。根据实际查询分布，选择覆盖 80% 高频查询的索引组合。

延伸阅读

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