索引结构对比：Hash、B 树、B+ 树的恩怨情仇

面试官问：「为什么 MySQL 用 B+ 树而不是 B 树？」

你张口就来：「B+ 树查询快啊。」

面试官笑了笑：「B 树查询也快，你能说说 B+ 树具体好在哪吗？」

你沉默了。

别急，这篇文章帮你把 B 树、B+ 树、Hash 的恩怨情仇捋清楚。

---

先说 Hash：最直接的查找方式

Hash 索引的结构很简单：一个数组 + 链表（处理冲突）。

// Hash 索引的核心思想
public class HashIndex {
    private Entry<String, Long>[] table;  // 数组
    private int capacity;                   // 容量

    public Long get(String key) {
        // 1. 计算 Hash 值
        int hash = hash(key);

        // 2. 定位到数组下标
        int index = hash % capacity;

        // 3. 遍历链表查找
        for (Entry<String, Long> e = table[index]; e != null; e = e.next) {
            if (e.key.equals(key)) {
                return e.value;  // 找到了，返回主键值
            }
        }
        return null;
    }
}

Hash 索引的优点：

• 等值查询极快，O(1) 时间复杂度
• 简单高效，不需要复杂的树结构

Hash 索引的致命缺陷：

1. 不支持范围查询：WHERE id > 100 AND id < 200，Hash 无法高效处理
2. 不支持排序：Hash 值无序，无法 ORDER BY
3. 不支持最左前缀匹配：联合索引在 Hash 面前毫无意义
4. Hash 冲突：极端情况下可能退化为 O(n)

所以 Hash 索引只适合等值查询极多的场景，比如 Session 表、配置表。

---

B 树：进步了，但还不够

B 树（Balance Tree）是一种自平衡的多路查找树。

「多路」是关键——每个节点可以有多个子节点，不像二叉树只有两个。

B 树结构（每个节点最多 3 个索引，2 个指针）：

                    [30 | 50 | 70]
                   /    |    \
           [10,20]  [35,40]  [60,80,90]
              |        |         |
            数据      数据       数据

B 树的核心特点

1. 所有节点都存储数据：索引和真实数据都存在节点里
2. 多路平衡：每个节点可以有多个子节点
3. 自平衡：插入/删除自动调整结构

B 树的优点：

• 查询稳定，O(log n)
• 树高比二叉树低很多
• 单次 I/O 能读取更多数据

B 树的缺点：

• 所有节点都存数据，导致每个节点存的索引变少，树高增加
• 范围查询效率不高

---

B+ 树：B 树的全面升级版

B+ 树在 B 树的基础上做了两个关键改进：

改进一：非叶子节点只存索引

B 树（非叶子节点也存数据）：
                    [30数据 | 50数据 | 70数据]
                   /       |        \
              数据        数据        数据

B+ 树（只有叶子节点存数据）：
                    [30 | 50 | 70]  ← 只有索引
                   /    |    \
                页1    页2    页3     ← 指向数据页的指针
               / | \   / | \   / | \
            数据 数据 数据 数据 数据 数据

这意味着：同样大小的节点，B+ 树能存更多索引，树高更低。

改进二：叶子节点用链表连接

B+ 树叶子节点链表：

[10] ↔ [15] ↔ [23] ↔ [30] ↔ [45] ↔ [67] ↔ [89]
  ↓      ↓      ↓      ↓      ↓      ↓      ↓
数据    数据    数据    数据    数据    数据    数据

范围查询 WHERE id > 20 AND id < 50 只需：

1. 找到 20 所在位置
2. 沿着链表向后遍历，直到超过 50

不需要回溯到父节点！

---

三大数据结构横向对比

特性	Hash	B 树	B+ 树
等值查询	O(1)，最快	O(log n)	O(log n)
范围查询	不支持	需要回溯，效率低	链表遍历，高效
排序	不支持	中序遍历，效率一般	链表天然有序，高效
插入/删除	可能有 rehash	需要分裂合并，较复杂	需要分裂合并，较复杂
空间利用率	取决于负载因子	较高	较高
磁盘 I/O	单点查询友好	中等	专为磁盘设计，最优
最左前缀	不适用	不适用	支持（联合索引）

---

为什么 MySQL 选择 B+ 树？

综合来看，B+ 树是 MySQL（尤其是 InnoDB）的最优选择：

1. 磁盘 I/O 友好

MySQL 的数据最终存储在磁盘上，每次读取磁盘以页（通常 16KB）为单位。

B+ 树的非叶子节点只存索引不存数据，相同大小的页能存更多索引，树高更低，I/O 次数更少。

2. 范围查询高效

叶子节点的链表设计，让范围查询只需沿着链表遍历，无需回溯。

这对 SQL 中的 BETWEEN、IN、>、< 等操作非常友好。

3. 查询稳定性

无论查询哪条数据，B+ 树都需要从根节点走到叶子节点，路径长度固定，不存在最坏情况退化。

4. 适合数据库索引

数据库索引的核心需求就是：快速定位 + 高效范围查询 + 排序支持，B+ 树完美满足。

---

一句话总结

数据结构	一句话评价
Hash	等值查询王者，范围查询青铜
B 树	什么都行，但什么都不精
B+ 树	为数据库而生的六边形战士

---

面试追问方向

• B+ 树的叶子节点链表是单向还是双向？为什么？
• B+ 树的度（degree）是怎么确定的？和什么因素有关？
• 如果一张表数据量是 1 亿条，B+ 树大概有多高？

B+ 树的高度通常只有 3-4 层，这是 MySQL 能支撑海量数据的关键。