🏷️ 知识点：B+树

下列关于 B-树和 B+树的叙述中，不正确的是（　）。

A. B-树和 B+树都能有效地支持顺序查找 B. B-树和 B+树都是平衡的多叉树 C. B-树和 B+树都能有效地支持随机查找 D. B-树和 B+树都可以用于文件索引结构

B+树

[tag_link]

正确答案：A

在B-树和B+树的比较中，B+树由于所有数据存储在叶子节点且叶子节点通过指针链接成有序链表，可以高效地进行顺序查找（即范围查询或全表扫描）。 而B-树的数据分布在整个树的节点中，叶子节点之间没有直接链接，进行顺序查找时需要从根节点开始反复进行树搜索，效率较低。 因此，B-树不能像B+树那样有效地支持顺序查找，选项A的叙述不正确。

选项B正确，因为B-树和B+树都是平衡的多路搜索树，所有叶子节点处于同一层，保持了树的平衡性。 选项C正确，两者都支持基于键值的随机查找，查找时间复杂度与树高相关，效率较高。 选项D正确，B-树和B+树在数据库和文件系统中被广泛用作索引结构，以优化数据存取性能。

下列应用中，适合使用 B+ 树的是（）

B+树

A. 编译器中的词法分析 B. 关系数据库系统中的索引 C. 网络中的路由表快速查找 D. 操作系统的磁盘空闲块管理

[tag_link]

正确答案：B

B+ 树 是应文件系统所需而产生的 B 树 的变形，前者比后者更加适用于实际应用中的操作系统的文件索引和数据库索引，因为前者磁盘读写代价更低，查询效率更加稳定。编译器中的词法分析使用有穷自动机和语法树。网络中的路由表快速查找主要靠高速缓存、路由表压缩技术和快速查找算法。系统一 般使用空闲空间链表管理磁盘空闲块。所以 B 正确。

B+ 树不同于 B 树的特点之一是（）

B树 B+树

A. 能支持顺序查找 B. 结点中含有关键字 C. 根结点至少有两个分支 D. 所有叶结点都在同一层上

[tag_link]

正确答案：A

由于 B+ 树 的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序 链接，可以进行顺序查找，而 B 树不支持顺序查找（只支持多路查找）。