B-Tree - 为什么不能有一个偶数个键的节点？

Question

我试图根据“算法简介”中的“B-Trees”一章来实现B树。

我不明白的是“最低程度”。在书中指出，度是一个数字，它表示节点可以容纳的密钥数量的下限/上限。它进一步说：至少

1. 每个非根节点店在t - 1键和具有t孩子。
2. 每个节点最多存储2*t - 1密钥并且有2*t子女。

所以，你得到的T = 2：

1. t - 1 = 1个键和t = 2名儿童
2. 2*t - 1 = 3个键和4个孩子

当t = 3

1. t - 1 = 2个键和t = 3个ch ildren
2. 2*t - 1 = 5键和6个孩子

现在，这里的问题：它似乎在B树的节点只能存储一个奇数字键的时候都充分。

为什么不能有一个节点，让我们说至多4个键和5个孩子？它与分裂节点有关吗？

Answer 1

看来B树中的节点只能存储奇数个键？

绝对不是。您所写的数字分别是最小和最大键数，因此对于t = 2，允许使用带有1，2，3键的节点。对于t = 3，允许具有2,3,4,5个密钥的节点。

而且，树的根允许只有1个键。

可以定义（并实现）具有例如树的树。 1个或2个键在一个节点（所谓的2-3树）。 B树被定义为容纳多一个的原因是，这导致更快的性能。特别是，这允许分期付款O(1)（计数拆分和连接操作）删除和插入操作。

Answer 2

这不是不可能的，但不是最理想的。如何将一个节点与奇数个孩子分开？