下列关于非空 B 树的叙述中，正确的是（ ）

I. 插入操作可能增加树的高度

II. 删除操作一定会导致叶结点的变化

III. 查找某关键字一定是要查找到叶结点

IV. 插入的新关键字最终位于叶结点中

B树

A. 仅 I B. 仅 I、II C. 仅 III、IV D. 仅 I、II、IV

[tag_link]

正确答案：B

在 B 树 中，插入 操作可能导致节点分裂。如果根节点已满，插入新键会触发根节点分裂，生成一个新的根节点，从而增加树的高度。因此，插入操作确实可能（但不一定）增加树的高度。选项 I 正确。删除 操作可能涉及以下情况：

• 删除的键在叶子结点：直接从叶子结点移除该键，导致叶子结点内容变化。
• 删除的键在非叶子结点：B 树会用前驱或后继键（通常位于叶子结点）替换该键，然后删除前驱或后继键。这仍然会导致叶子结点的变化。
• 删除后触发合并或借键：如果删除键后某个节点键数低于最小要求（通常 ⌈m / 2⌉ − 1），可能需要从兄弟节点借键或与兄弟节点合并。这些操作可能涉及叶子结点（例如，合并两个叶子结点或调整叶子结点的键）。在所有删除场景中，无论是直接删除键还是通过替换、合并、借键，操作最终都会影响叶子结点（键的移除或调整发生在叶子结点）。选项 II 正确。查找关键字并不一定需要查找到叶子结点。例如，如果目标键位于根节点或中间节点，查找会在这些非叶子结点停止。选项 III 错误。新关键字在 B 树中开始总是被插入到叶子结点中，但是可能随着分裂上溢到非叶子结点，选项 IV 错误。