algorithm - 为什么 B 树的根可以有最小度数 2？

Question

最近我发现B树的一个性质，它的根可以有最小度数2为什么会这样，有什么办法可以证明这一点吗？

Answer 1

这个问题有两个部分:

1。是否保证最少 2 个？

是的。

假设 B 树被配置为具有最大度 n，这意味着非叶节点最多可以具有 n-1 值。

当您开始向空 B 树添加值时，根节点第一次获得子节点是在添加的值不再适合根节点时。然后根节点 split 成两个节点，并在它们之上创建一个新的根节点，即作为这两个节点的父节点。因此，这里保持规则:根节点有 2 个子节点。

当添加更多的值时，根可能会得到更多的 child ，并且可能会再次发生上述情况:根被完全占用，需要 split ......等。

从 B 树中删除值时，子节点有时可能需要合并，这可能会减少根节点的子节点数量。规则是，当根节点的子节点数变为 1(因此根节点不再具有no 值)时，应删除该根节点，并且该子节点应成为新的根节点。由于该子节点维护了至少有 n/2 个子节点(或成为叶节点)的规则，我们可以得出结论，根节点将始终至少有两个子节点，或者成为叶节点。

2。下限可以设置得更高吗？

没有。最小度数不能超过 2。

例如，考虑我们希望它为 3(而不是 2)的情况。如果现在我们从一棵空树开始并添加值，并且我们遇到根已满的情况，我们需要将该根分成三个。但是这 3 个新节点的每个值将少于 n/2，这违反了 B 树的另一条规则:非根节点应至少占据其 50%能力……

所以，...这就是根的度数规则保持原样的原因。