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

Question

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

我不太明白的是“最小程度”。书中指出，度数是一个数字，表示节点可以容纳的键数的下限/上限。它进一步说:

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

所以当 t = 2 时:

1. t - 1 = 1 个键和 t = 2 个 child
2. 2*t - 1 = 3 个 key 和 4 个 child

对于 t = 3

1. t - 1 = 2 个键和 t = 3 个 child
2. 2*t - 1 = 5 把 key 和 6 个 child

现在问题来了:似乎 B 树中的节点在满时只能存储奇数 个键。

为什么不能有一个节点，比如说最多 4 个键和 5 个子节点？跟 split 节点有关系吗？

Answer 1

It seems that the nodes in a B-Tree can only store an odd number of keys?

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

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

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