algorithm - B-Tree - 为什么没有偶数个键的节点？

Question

我正在尝试根据“算法简介”中的“B-Trees”一章来实现 B-Tree。

我不太明白的是“最低学位”。在书中指出，度数是一个数字，表示节点可以持有的键数的下限/上限。它进一步说：

1. 每个非根节点至少存储t - 1key 并且有tchildren。
2. 每个节点最多存储2*t - 1key 并且有2*tchildren。

所以你得到 t = 2：

1. t - 1= 1 个键和 t = 2 个孩子
2. 2*t - 1= 3 把钥匙和 4 个孩子

对于 t = 3

1. t - 1= 2 个键和 t = 3 个孩子
2. 2*t - 1= 5 把钥匙和 6 个孩子

现在问题来了：似乎 B-Tree 中的节点在它们已满时只能存储奇数个键。

为什么不能有一个节点，比如说最多 4 个键和 5 个子节点？它与拆分节点有关吗？

Answer 1

似乎 B-Tree 中的节点只能存储奇数个键？

当然不。您写的数字分别是键的最小和最大数量，因此对于t = 2，允许具有 1、2、3 个键的节点。对于t = 3，允许具有 2、3、4、5 个键的节点。

此外，树的根只允许有 1 个键。

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

Answer 2

这不是不可能的，而是次优的。如何拆分具有奇数个子节点的节点？