B-树的阶数

Question

我正在为一次考试而复习，结果考上了B树。维基百科将B-树描述为一棵树，其中节点至少有d个，最多有2d个关键字，因此最多有2d+1个叶子。例如，如果为d=1，则它最多有2个键和3个子对象，这使其成为2-3个树。然而，除非我弄错了，否则这是不允许2-3-4树的。

然而，我们的材料将b-树描述为树，其中每个节点至少有t>=2、t-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的树中，键的最大数量是多少？

Answer 1

如果您仔细阅读wiki文章，您会发现B-trees有两种主要变体(不包括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 children t=1)

2-3-4是第二种类型(t+1 -> 2t+2 children t=1)

这两个变体的有效性都源于这样一个事实:拆分和合并(对ADT执行的delete和insert操作)都是有效的：

t -> 2t

分开。当我们添加一个新元素，并且一个节点的键数超过了最大数目2t时，我们就有了2t+1键，我们将节点拆分为两个节点，并将一个元素推送到父节点，将2t键留在两个子节点中，将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

当然，在运行时间上没有区别，只是实现上的细微差别，理论上意义不大(你可以用第一个变种略微优化一些算法，但不会改变运行时的复杂性)。

Answer 2

在谷歌学者中搜索b tree comer => Ubiquitous -Tree，Comer，1979

这是你在数据结构论文中被引用最多的论文。本文详细描述了b树(它是如何工作的，复杂性和它的变体...)。这样你就能找到答案了。

我希望这能帮到你

附注：如果你使用的公式与所教授的公式不同，请在考试中引用该试卷:P