为什么 InnoDB 选择 B+ 树索引，而不是 B 树或者 Hash？

InnoDB 选择 B+ 树（B+Tree）索引 作为默认存储引擎索引结构，主要是因为它 兼顾查询效率、范围查询、磁盘存取优化，而 B 树 和 哈希索引（Hash） 各有局限性。

1. B+ 树 vs B 树

特性 B+ 树（B+Tree） B 树（B-Tree）
数据存储位置 仅叶子节点存储数据 所有节点（包括内部节点）都存储数据
范围查询（BETWEEN, >, <） ✅ 高效（叶子节点链表结构） ❌ 低效（必须遍历整个树）
磁盘读取效率 ✅ 更少的磁盘 I/O，更快的查询 ❌ 节点大小不均，I/O 开销大
索引扫描（ORDER BY） ✅ 高效支持 ❌ 不支持，查询需回溯树结构

🔹 为什么 B+ 树更适合数据库？

  1. 范围查询更高效：

    • B+ 树的 叶子节点 通过 链表连接，遍历时可以 直接顺序访问，适合 BETWEEN、ORDER BY、LIKE 'prefix%' 查询。
    • B 树的内部节点也存数据，导致范围查询需要回溯，效率低。

  2. 磁盘 I/O 友好：

    • B+ 树的内部节点只存索引，不存数据，一个节点可以存储更多索引，使树的高度更低，减少磁盘访问次数。
    • B 树的内部节点存数据，导致索引页大小不均匀，查询可能触发更多磁盘 I/O。

  3. 适用于数据库分页存储：

    • InnoDB 采用 页存储，B+ 树的叶子节点可与数据页对齐，优化存储和查询效率。

2. B+ 树 vs Hash 索引

特性 B+ 树索引 Hash 索引
等值查询（=） ✅ 高效 ✅ 更快
范围查询（BETWEEN, >, <） ✅ 支持 ❌ 不支持
有序查询（ORDER BY） ✅ 支持 ❌ 不支持
联合索引（复合索引） ✅ 支持 ❌ 不支持
索引存储方式 树结构，叶子节点存有序数据 哈希表，存储键值对

🔹 为什么 B+ 树比 Hash 更适合数据库？

  1. 支持范围查询（BETWEEN, >, <）：

    • B+ 树的索引是 有序的，支持范围查询。
    • Hash 索引是基于 哈希函数，数据是 无序的，无法进行范围查找。

  2. 支持 ORDER BY / GROUP BY / LIKE：

    • B+ 树索引支持 ORDER BY 和 GROUP BY 操作，因为数据是有序的。
    • Hash 索引无序，无法用于排序和分组。

  3. 支持部分匹配（联合索引）：

    • B+ 树支持 联合索引，可以利用前缀匹配索引。
    • Hash 索引只能完整匹配，无法利用部分匹配。

  4. 避免 Hash 冲突：

    • Hash 索引依赖 哈希函数，如果两个不同的键计算出相同的哈希值，会导致哈希冲突，影响性能。
    • B+ 树索引没有这个问题，查找速度稳定。

3. 为什么 InnoDB 选择 B+ 树，而 MyISAM 也使用 B+ 树？

✅ InnoDB 选择 B+ 树的原因

  • InnoDB 是事务型存储引擎，需要支持 事务（ACID） 和 高并发，B+ 树结构天然适用于 MVCC（多版本并发控制），提高数据库并发性能。
  • B+ 树索引天然支持：
    • 等值查询（=）
    • 范围查询（BETWEEN, >, <）
    • 排序（ORDER BY）
    • 分组（GROUP BY）
  • B+ 树适用于磁盘存储，减少磁盘 I/O，提高查询效率。

✅ MyISAM 也使用 B+ 树

  • MyISAM 不是事务型存储引擎，但也使用 B+ 树索引，因为它擅长快速读取和范围查询，适用于 全文索引。

4. 结论

索引类型 优点 缺点 适用场景
B+ 树索引 ✅ 适用于 等值查询（=）+ 范围查询（>、<、BETWEEN）+ 排序，磁盘 I/O 友好 插入时可能需要维护索引平衡，写入性能稍低 ✅ 适用于所有关系型数据库（MySQL/InnoDB 默认使用）
B 树索引 ✅ 适用于等值查询（=） ❌ 不适用于范围查询，内部节点存数据，查询复杂度高 ❌ 不适用于数据库索引（查询范围性能差）
Hash 索引 ✅ 等值查询（=）极快 ❌ 不支持范围查询、不支持排序、哈希冲突影响性能 ✅ NoSQL 数据库、缓存（如 Redis）

🔥 InnoDB 选择 B+ 树的 4 大核心原因

  1. 支持等值查询 & 范围查询（BETWEEN、>、<）。
  2. **有序存储，支持 ORDER BY / GROUP BY / LIKE ‘prefix%’**。
  3. 适用于磁盘存储，减少磁盘 I/O，提高查询效率。
  4. 支持事务和 MVCC，提高数据库并发性能。

💡 总结：

  • 数据库索引首选 B+ 树（InnoDB 默认使用）。
  • 如果是缓存（如 Redis），可以使用 Hash 索引，但只适合等值查询（=）。
  • B 树几乎不会用于数据库索引，因为范围查询性能差。