为什么数据库索引用 B+ 树，而不用红黑树、哈希表或 B 树？

简化版

因为数据库索引在磁盘上，瓶颈是磁盘 IO 次数（≈ 树高）。红黑树/二叉树扇出只有 2，树太高、IO 太多；哈希表等值查询快但不支持范围查询、排序、最左前缀；B 树内部节点存数据、扇出比 B+ 树小、且范围查询要回溯。B+ 树内部节点只存索引→扇出巨大→树矮→IO 少，叶子链表→范围查询和排序极快，综合最优。

详细版

逐个对比为什么其它结构不合适：

结构	为什么不选它做磁盘索引
二叉搜索树 / 红黑树	扇出只有 2，树高 O(log₂n)，几千万数据要几十层 → 几十次磁盘 IO，太慢
哈希表	等值查询 O(1) 很快，但不支持范围查询、排序、`ORDER BY`、最左前缀匹配；还有哈希冲突、扩容 rehash 问题
B 树	内部节点存数据 → 一页装的关键字少 → 扇出比 B+ 树小、树略高；范围查询要在树里回溯，不如叶子链表顺扫
B+ 树 ✅	内部只存索引 → 扇出大 → 树矮（3~4 层存千万级）→ IO 少；叶子有序链表 → 范围/排序极快；查询延迟稳定

完整版教学

一、核心前提：磁盘索引的瓶颈是 IO 次数

数据库的数据和索引放在磁盘上，磁盘一次 IO 比内存访问慢几万倍。查一条数据要下降几层树，每下降一层就是一次磁盘 IO。所以索引结构的首要目标是：把树压矮，让 IO 次数尽可能少。理解了「IO 次数 ≈ 树高」，就能理解为什么选 B+ 树——它是所有候选里最矮的。

二、为什么不用红黑树 / 二叉树

红黑树是优秀的内存数据结构，但拿到磁盘上就不行了：它每个节点只有 2 个孩子（扇出 2），树高 O(log₂n)。3000 万数据，红黑树高约 25 层——查一条数据最坏要 25 次磁盘 IO，慢得无法接受。扇出太小是二叉树类结构做磁盘索引的死穴。B+ 树扇出上千，同样数据只要 3~4 层。

三、为什么不用哈希表

哈希表等值查询平均 O(1)，比 B+ 树还快，为什么不用？因为数据库查询远不止「等值查询」：

不支持范围查询：WHERE age > 20 这种，哈希把 key 打散到各处，没法按范围找。
不支持排序 / ORDER BY：哈希无序。
不支持最左前缀匹配：联合索引 (a,b,c) 用哈希就没法只按 a 查。
等值查询也可能慢：哈希冲突严重时退化，扩容还要 rehash。

B+ 树天然有序，范围、排序、前缀匹配全支持。所以哈希索引只在「只做等值查询」的特定场景（如 Memory 引擎、Redis）才用，通用索引还得 B+ 树。

四、为什么不用 B 树（而是 B+ 树）

B 树已经是多路、很矮了，但 B+ 树在两点上更强：

扇出更大、树更矮：B 树内部节点存数据，一页装的关键字少；B+ 树内部节点只存关键字，同样一页能装多得多的关键字，扇出更大，树更矮，IO 更少。
范围查询更快：B 树范围查询要在树里中序遍历、上下回溯；B+ 树叶子是有序链表，范围查询只需定位起点后顺着链表扫，还是顺序 IO，快得多。

数据库大量操作是范围扫描、排序、分页，B+ 树的叶子链表在这些场景碾压 B 树。

五、B+ 树到底矮到什么程度

用 InnoDB 的典型参数估算（页 16KB）：内部节点一个索引项约 14 字节（主键 8 字节 + 页指针 6 字节），一页约存 16384/14 ≈ 1170 个。假设叶子一页存 16 行数据：

2 层：1170 × 16 ≈ 1.8 万行
3 层：1170 × 1170 × 16 ≈ 2000 万行
4 层：可达数百亿行

也就是说，3~4 层的 B+ 树就能覆盖绝大多数表，一次查询最多 3~4 次磁盘 IO（且根节点常驻内存，实际更少）。这就是 B+ 树做磁盘索引的终极理由。

六、常见误区与追问

考点	正确口径
红黑树	高度相对磁盘页太高，IO 多
哈希表	等值快但不支持范围和排序
B 树	数据分散，范围扫描不如 B+ 树
B+ 树	扇出高、叶子链表、范围友好

database index cares about:
  fewer page reads
  ordered range scan
  stable lookup path
B+ tree matches all three

数据库索引选 B+ 树，是因为磁盘 IO 和范围查询，而不是单纯比较内存里的算法复杂度。

误区：红黑树也是 O(log n)，所以适合数据库索引。 红黑树分叉少、树高大，磁盘页访问次数远多于高扇出的 B+ 树。
误区：哈希表平均 O(1)，一定比 B+ 树更适合。 哈希索引不天然支持范围查询、排序、前缀匹配和顺序扫描。
误区：B 树和 B+ 树做数据库索引没有区别。 B+ 树数据集中在叶子并有叶子链表，范围扫描和查询稳定性更好。
追问：B+ 树为什么 IO 少？ 内部节点扇出大，树高通常只有几层，根和上层还常被缓存。
追问：为什么叶子链表重要？ 范围查询定位起点后可以沿链表顺序读叶子页，避免反复从根查找。
追问：什么时候哈希索引仍有价值？ 只有等值查询、无需排序范围时哈希索引可能有优势，但通用数据库索引更偏 B+ 树。

七、加强记忆

数据库索引在磁盘上，瓶颈是 IO 次数 ≈ 树高，所以要树矮。红黑树/二叉树扇出仅 2、树太高，IO 多；哈希等值快但不支持范围/排序/最左前缀；B 树内部存数据、扇出较小、范围要回溯；B+ 树内部只存索引→扇出大→树矮（3 层存约 2000 万行）、叶子有序链表→范围排序顺扫、延迟稳定，综合最优。

简化版

详细版