题目

下列应用中，适合使用 B+ 树的是( )。

错因

A

只记住"B+ 树是一种高效查找结构"，看到"词法分析"也涉及"查找关键字"就误选。但词法分析的关键字集很小且固定（一般几十个），且都在内存里，用 哈希表或自动机（如 trie / DFA）即可，用不上 B+ 树这种磁盘多路平衡树——B+ 树的优势在于"减少磁盘 I/O 次数"，对内存里的小数据集是过度设计。

C

路由表查找的核心是 最长前缀匹配（longest prefix match），主流方案是 trie / 压缩 trie / TCAM 硬件。B+ 树支持"等值查找"和"范围查找"，不支持最长前缀匹配语义，应用场景不对口。

D

磁盘空闲块管理需要"快速找到空闲块、合并相邻空闲块"，主流方案是位示图 / 空闲链表 / 成组链接——这些数据结构操作的粒度很细（按 bit 或按链节点），用 B+ 树会引入额外索引开销，得不偿失。

总解析

核心：B+ 树的设计目标是"减少磁盘 I/O"——节点容量大（一个节点对应一个磁盘块），高度低（几亿条记录通常 3-4 层），叶子节点用链表串联便于范围扫描。

四个候选场景的本质需求逐项对照：

场景	核心需求	主流数据结构	是否 B+ 树
词法分析	内存里小关键字集查找	哈希表 / DFA / Trie	✗
数据库索引	海量数据按键查找 + 范围扫描，主存储在磁盘	B+ 树	✓
路由表	最长前缀匹配	Trie / TCAM	✗
磁盘空闲块	快速分配 / 合并	位示图 / 成组链接	✗

为什么数据库索引偏爱 B+ 树（而非 BST、AVL 或 B 树）：

• 数据量大、不能全装内存 → 需要磁盘友好的存储结构
• 节点宽（fan-out 高）→ 树高低 → 一次查找只需 3-4 次磁盘 I/O
• 数据全部存放在叶子节点 + 叶子按键链接 → 范围查询（BETWEEN、ORDER BY）只需一次 I/O 定位起点，再顺链遍历，比 B 树更快
• 内部节点只存键不存数据 → 同等内存可缓存更多索引项，进一步降低 I/O

最终答案是 B。

数据结构与场景的匹配口诀：内存小数据集用哈希；最长前缀匹配用 trie；位级分配用位图；磁盘上的海量索引才用 B+ 树。