m 路 B 树可以有 m 个奇数吗？

Question

我在书 CLRS 上读到我们有 m 路 B 树，其中 m 是偶数。但是有没有m为奇数的B-Tree，如果有那我们怎么修改本书给出的代码呢

Answer 1

m-way B-tree 我假设你的意思是 B-tree 每个内部节点最多允许有 m children。根据 CLRS 对 B-tree 的定义：

Nodes have lower and upper bounds on the number of keys they can contain. We express these bounds in terms of a fixed integer t ≥ 2 called the minimum degree of the B-tree: ... an internal node may have at most 2t children.

所以 children 的最大数量将永远是 even – 根据这个定义，它不能是奇数。

然而，这并不是B-tree的唯一定义。有许多定义略有不同，最终对整体性能影响不大。这可能会造成混淆。有一些 B-tree 定义允许奇数上限，而那些则不允许。 CLRS 的定义不内部节点的 children 计数的奇数上限。

然而，B-tree 的另一个正式定义是由 Knuth [1998]（计算机编程艺术，第 3 卷（第二版），Addison-Wesley，ISBN 0 -201-89685-0）。 Knuth 的定义确实允许奇数上限。 CLRS 枚举所有 min-max 形式的树边界 (t, 2t) for t ≥ 2，Knuth 枚举形式 (ceil(k/2), k) for k ≥ 2 的所有树边界。

Knuth Order, k |  (min,max)  | CLRS Degree, t
---------------|-------------|---------------
     0         |      -      |        –
     1         |      –      |        –
     2         |      –      |        –
     3         |    (2,3)    |        –
     4         |    (2,4)    |      t = 2
     5         |    (3,5)    |        –
     6         |    (3,6)    |      t = 3
     7         |    (4,7)    |        –
     8         |    (4,8)    |      t = 4
     9         |    (5,9)    |        –
     10        |    (5,10)   |      t = 5

因此，例如，2-3 tree，(2,3) 是 Knuth 阶数为 3 的 B-tree。但它不是有效的 CLRS 树，因为它的上界为奇数。

更改代码并不容易，因为 B-trees 有很多代码取决于变量 t。最大的变化之一是在内部：B-TREE-SPLIT-CHILD(x,i)，您需要找到一种方法将 child 拆分为奇数个children（偶数个键）进入节点 y 和 z。这两个结果节点之一将比另一个多一个密钥。如果您正在寻找代码，我建议您在 Internet 上寻找使用类似于 Knuth 的定义的 B-tree 的实现（例如搜索 "Knuth Order B-tree"）。

m 路 B 树可以有 m 个奇数吗？

Can an m-way B-Tree have m odd?

algorithm

b-tree

clrs