InnoDB为什么使用B+树实现索引？

一、先看问题本质：索引像书的目录

想象一本书有 1000 页：

• 没有目录：找某个关键词需逐页翻（全表扫描）→ 慢！
• 有目录：先查目录定位章节页数 → 直接翻到目标页 → 快！

数据库索引的核心目标：快速定位数据位置，减少磁盘读取次数（磁盘 I/O 是数据库最慢的操作）。

二、为什么不用其他数据结构？对比图一目了然

1. 哈希表（Hash）：只能查单个值

         哈希桶
        ┌──────┐
键: 101 ─→│ 数据A │
        ├──────┤
键: 202 ─→│ 数据B │
        └──────┘

❌ 缺点：

• 无法范围查询（如 WHERE id > 100）
• 哈希冲突影响性能

2. 二叉树（BST）：树太高导致 I/O 多

         [100]
        /     \
     [50]     [150]
    /   \     /   \
 [20]  [70] [120] [180]

❌ 缺点：

• 100 万数据 → 树高约 20 层 → 查一次需 20 次磁盘 I/O（磁盘慢！）
• 不平衡时退化成链表（更慢）

3. B 树：节点存数据 → 占用空间大

          [50 | 100]     ← 节点同时存数据+指针
        /     |     \
      [20]  [70]   [120|150]

❌ 缺点：

• 每个节点既存索引又存数据 → 单节点能存的索引更少
• 树更高 → I/O 次数增加

三、B+ 树完美解决方案：多叉树 + 叶子链表

✅ B+ 树结构图解

                           ┌──────────────┐
                           │  非叶子节点   │
                           │ [20, 50, 70] │ ← 只存索引（不存数据！）
                           └──────┬───────┘
                 ┌────────────────┼────────────────┐
          ┌──────▼──────┐   ┌─────▼──────┐   ┌─────▼──────┐
          │ 非叶子节点   │   │ 非叶子节点  │   │ 非叶子节点  │
          │ [10, 20]    │   │ [30, 50]   │   │ [60, 70]   │
          └──────┬──────┘   └─────┬──────┘   └─────┬──────┘
       ┌─────────┴──┐       ┌─────┴─────┐     ┌────┴─────┐
  ┌────▼───┐   ┌────▼───┐  ┌▼───┐  ┌───▼┐   ┌▼───┐  ┌───▼┐
  │ 叶子节点│   │ 叶子节点│  │叶节│  │叶节│   │叶节│  │叶节│
  │[10,数据]│   │[20,数据]│  │[30]│  │[50]│   │[60]│  │[70]│
  ├────────┤   ├────────┤  ├───┤  ├───┤   ├───┤  ├───┤
  │ 指针   ├──→│ 指针   ├─→│指 ├→│指 ├─→│指 ├→│指 │
  └────────┘   └────────┘  └───┘  └───┘   └───┘  └───┘

📌 核心特点：

1. 非叶子节点只存索引（不存数据）→ 单节点能存更多索引 → 树更矮胖
2. 叶子节点存数据 + 双向指针 → 范围查询极快（顺序遍历链表）

四、B+ 树的 4 大核心优势

✅ 优势 1：树高极低 → 减少磁盘 I/O

• B+ 树一个节点存 16KB（InnoDB 页大小）
• 假设索引 8B + 指针 6B → 单节点存约 1200 个索引（16KB/(8+6)）
• 3 层 B+ 树能存：1200 × 1200 × 1200 ≈ 17 亿条数据 → 仅需 3 次 I/O 找到数据！

✅ 优势 2：范围查询极快

• 找到范围起点后 → 沿叶子节点链表顺序遍历（无需回溯上层）
• 例：查 WHERE id > 20 AND id < 60：
  1. 找到 20 所在叶子节点
  2. → 链表向右遍历到 30、50
  3. → 直到 60 结束

✅ 优势 3：查询更稳定

• 所有查询都要走到叶子节点 → 任何数据查询次数 = 树高
• 而 B 树可能在非叶子节点就找到数据（次数不稳定）

✅ 优势 4：全表扫描更快

• 只需遍历叶子节点链表 → 相当于顺序读磁盘
• 而 B 树需要遍历所有节点（随机读取）

五、B+ 树 vs 其他结构性能对比

总结：InnoDB 用 B+ 树的核心原因

💡 一句话总结：
B+ 树用“非叶子节点只存索引”换取更矮的树（减少 I/O），用“叶子节点链表”支持高效范围查询，完美适配磁盘特性和数据库查询需求。