⭐ 题目日期：

美团 - 2025/4/4

📝 题解：

MySQL选择B+树作为索引结构，是出于对磁盘存储特性、查询效率、范围查询支持等多方面权衡的结果。以下是具体原因：

---

1. 适合磁盘存储结构，减少I/O次数

• 节点存储密度高：
  B+树的非叶子节点不存储实际数据（仅存储键值），因此一个节点可以容纳更多键值，从而显著降低树的高度。
  树高越低，磁盘I/O次数越少（例如，3层的B+树可存储千万级数据）。

• 利用磁盘预读特性：
  磁盘按页（通常4KB）读取数据，B+树的节点大小通常设置为页大小的整数倍，单次I/O能加载更多键值，减少寻道开销。

---

2. 高效支持范围查询

• 叶子节点构成有序链表：
  B+树的所有叶子节点通过指针相连，范围查询（如WHERE id BETWEEN 10 AND 100）只需遍历链表即可，无需回溯上层节点。

• 对比B树：
  B树的数据分散在各层节点，范围查询需要多次中序遍历，导致更多随机I/O。

---

3. 查询性能稳定

• 所有查询均需到叶子节点：
  无论查询命中与否，B+树的路径长度一致（树高固定），时间复杂度稳定为O(logN)，适合OLAP和OLTP场景。

• 对比B树：
  B树可能在非叶子节点直接命中数据，导致查询时间波动。

---

4. 更优的扫表性能

• 全表扫描更高效：
  由于叶子节点包含全部数据，遍历链表即可完成全表扫描，无需访问非叶子节点。

• 对比B树：
  B树需要按层级遍历所有节点，效率较低。

---

5. 与B树的对比

特性	B+树	B树
非叶子节点存储数据	❌ 仅存储键值，无数据	✅ 存储键值和数据
叶子节点结构	✅ 链表连接，支持高效范围查询	❌ 无链表，范围查询需多次中序遍历
树高与I/O次数	更低（相同数据量）	更高
适用场景	范围查询、全表扫描	随机点查询为主

---

6. 为什么不选其他数据结构？

• 哈希表：
  仅支持等值查询，无法处理范围查询（如>、<、BETWEEN）。

• 平衡二叉树（AVL/红黑树）：
  树高过高（存储百万数据需要约20层），导致磁盘I/O次数剧增。

• 跳表：
  虽然支持范围查询，但内存开销大，且磁盘I/O不友好。

---

总结

B+树通过高扇出、低树高的设计，最小化磁盘I/O次数；通过叶子节点链表优化范围查询；同时保持查询稳定性。这些特性使其成为磁盘存储场景下数据库索引的理想选择。