B树的顺序

Question

我正在备考考试，遇到了B树。维基百科将B树描述为一种树，其中节点具有至少d个键和最多2d个键，因此最多有2d+1个叶子节点。例如，如果d=1，则最多有2个键和3个孩子，这是一棵2-3树。但是，除非我搞错了，否则这样做将不允许2-3-4树存在。

然而，我们的资料将b-tree描述为一种树，其中每个节点至少有t>=2t-1个键，最多有2t-1个键。这意味着节点具有奇数个键和偶数个孩子。例如，t=2将具有1到3个键，并且最多有4个孩子，这是一棵2-3-4树。另一方面，使用这种符号不能得到2-3树。

此外，Knuth提出的符号中，d表示节点中的最大孩子数。该符号既允许偶数个孩子，也允许奇数个孩子，从而允许2-3树和2-3-4树均存在。

我知道2-3树和2-3-4树都存在。

真正的符号是什么？是否有真正的符号？额外的问题是：在高度为h的树中，键的最大数量是多少？

- Masse

Answer 1

如果你仔细阅读维基百科文章，你会发现B树有两个主要变种（不包括像B*和B+这样的结构变体），一个是 t -> 2t 个键，另一个是 t -> 2t+1 个键。

将这些变种转换为 #子项，我们有一个具有 t+1 -> 2t+1 个子节点的变种，以及一个具有 t+1 -> 2t+2 个子节点的变种。

因此，回答你的问题，2-3和2-3-4树都是有效的树，每个树符合不同的变种/定义：

2-3是第一种类型（t+1 -> 2t+1 个子节点，其中 t=1）

2-3-4是第二种类型（t+1 -> 2t+2 个子节点，其中 t=1）

两种变种的有效性源于分裂和合并（在ADT中删除和插入时执行的操作）都是有效的： t -> 2t：

分裂。当我们添加一个新元素并且一个节点具有超过最大键数 2t 时发生。所以我们有 2t+1 个键，我们将节点分成两个节点，并将一个元素推到父节点，使得两个子节点中各有 t 个键。这是可以接受的，因为节点中键的最小数量确实是 t。

合并。当我们删除一个键，一个节点包含少于最小数量 t，并且它的兄弟节点也处于最小状态时发生。所以我们在新合并的节点中有 t-1 + t 个键，结果节点必须是有效的：t-1 + t = 2t-1 <= 2t。很好。

同样适用于 t -> 2t+1：

分裂。2t+2 变成了 t 和 t+1，这是可以接受的。

合并。t-1 + t = 2t-1 <= 2t+1 当然，运行时间没有区别，这只是一些微小的实现差异，理论上没有太大的重要性（你可以稍微优化一些算法来使用第一种变种，但不会改变运行时间复杂度）。

- davin

Answer 2

在 Google 学者中搜索 b 树 comer => Ubiquitous B-Tree, Comer, 1979

这是数据结构论文中最常被引用的论文。该论文详细描述了 b 树（它的工作原理、复杂度及其变种...）。您应该能在那里找到答案。

希望这能帮到您。

p.s. 如果您使用了不同于所教公式，请在考试中引用该论文 :P

- mkn