CLRS B-Tree 属性 节点的键数的下限和上限可以包含
CLRS B-Tree property lower and upper bound on number of keys of a node can contain
在 CLRS 算法简介：B-Tree definition 中给出 属性 指出：
5.There are lower and upper bounds on the number of keys a node can contain. These bounds can be expressed in terms of a fixed integer t >=
2 called the minimum degree of the B-tree:
a. Every node other than the root must have at least t - 1 keys.
Every internal node other than the root thus has at least t children.
If the tree is nonempty, the root must have at least one key.
b. Every node can contain at most 2t - 1 keys. Therefore, an internal
node can have at most 2t children. We say that a node is full if it
contains exactly 2t - 1 keys.
它说
t
是最低学历。
我的问题是它在计算什么，子节点指针或键数。以及 属性 5.b 如何保持 .
我已经通过维基百科定义了 B-Tree 、2-Tree 和 2-3-4 Tree 并且只发现没有给出 Order of tree 的特定定义（根据 Knuth order is equal to max number of节点的子指针）。
我在Introduction to algorigthms, 3rd edition(CLRS)中查到了定义，t可以是>=2的任意整数，看你的需要。我们不计算它，我们只是设置 t，并确保属性 5 成立。也许你应该尝试通读所有的文字，希望post对你有所帮助~
您似乎对 Knuth 阶数和 CLRS 度数之间的区别感到困惑，所以请允许我解释一下。 Knuth 阶数 和 CLRS 度数 测量：min <= children <= max，最小值和最大值children，（min，max），树中的每个内部节点都允许有。两个定义都同意 min 不能小于 max/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
主要相似点/不同点：
- Knuth 阶数 k 是计算 children 的 最大 数量的索引。 k 的 Knuth 阶意味着每个节点必须有一个 max = k，和一个 min = ceil(k/2)。例如，(3,6) 是 Knuth 6 阶的 B-tree。
- CLRS度数t是统计children的最小个数的指标。 t 的 CLRS 度意味着每个节点必须有一个 min = t 和 max = 2t。例如，(3,6) 是 CLRS 度数 3
的 B-tree
- 在这两个定义中，都是 min = ceil(max / 2) 和 max = 2 * min.
在这两种定义中，键的数量等于children减去一个的情况。所以 Knuth order 和 CLRS degree 在技术上也在计算最小和最大 keys – 以及同时计算最小和最大 children.
Knuth 的定义允许树 (min,max)，其中 max an 是 奇数 ，但 CLRS 的定义忽略了它们。根据 CLRS 的定义，(t, 2t-1) 形式的任何树都是无效的。例如，具有 (min,max) = (5,9) 的树根据 Knuth 的定义是有效的，但根据 CLRS 的定义是无效的。
有趣的旁白：
- 两个定义都包含2-3-4 trees, which are trees with (min, max) = (2,4). It is a B-tree with Knuth order k = 4 and it's a CLRS B-tree with degree t = 2. These trees are closely related to Red-Black Trees.
- 只有 Knuth 的定义包括 2-3 trees, where (min, max) = (2,3). A 2-3 tree is a Knuth B-tree with Knuth order k = 3. It is not a valid CLRS B-tree. It's a shame that CLRS don't include this tree because they are closely related to AA trees.
在 CLRS 算法简介：B-Tree definition 中给出 属性 指出：
5.There are lower and upper bounds on the number of keys a node can contain. These bounds can be expressed in terms of a fixed integer t >= 2 called the minimum degree of the B-tree:
a. Every node other than the root must have at least t - 1 keys. Every internal node other than the root thus has at least t children. If the tree is nonempty, the root must have at least one key.
b. Every node can contain at most 2t - 1 keys. Therefore, an internal node can have at most 2t children. We say that a node is full if it contains exactly 2t - 1 keys.
它说
t
是最低学历。
我的问题是它在计算什么，子节点指针或键数。以及 属性 5.b 如何保持 .
我已经通过维基百科定义了 B-Tree 、2-Tree 和 2-3-4 Tree 并且只发现没有给出 Order of tree 的特定定义（根据 Knuth order is equal to max number of节点的子指针）。
我在Introduction to algorigthms, 3rd edition(CLRS)中查到了定义，t可以是>=2的任意整数，看你的需要。我们不计算它，我们只是设置 t，并确保属性 5 成立。也许你应该尝试通读所有的文字，希望post对你有所帮助~
您似乎对 Knuth 阶数和 CLRS 度数之间的区别感到困惑，所以请允许我解释一下。 Knuth 阶数 和 CLRS 度数 测量：min <= children <= max，最小值和最大值children，（min，max），树中的每个内部节点都允许有。两个定义都同意 min 不能小于 max/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
主要相似点/不同点：
- Knuth 阶数 k 是计算 children 的 最大 数量的索引。 k 的 Knuth 阶意味着每个节点必须有一个 max = k，和一个 min = ceil(k/2)。例如，(3,6) 是 Knuth 6 阶的 B-tree。
- CLRS度数t是统计children的最小个数的指标。 t 的 CLRS 度意味着每个节点必须有一个 min = t 和 max = 2t。例如，(3,6) 是 CLRS 度数 3 的 B-tree
- 在这两个定义中，都是 min = ceil(max / 2) 和 max = 2 * min.
在这两种定义中，键的数量等于children减去一个的情况。所以 Knuth order 和 CLRS degree 在技术上也在计算最小和最大 keys – 以及同时计算最小和最大 children.
Knuth 的定义允许树 (min,max)，其中 max an 是 奇数 ，但 CLRS 的定义忽略了它们。根据 CLRS 的定义，(t, 2t-1) 形式的任何树都是无效的。例如，具有 (min,max) = (5,9) 的树根据 Knuth 的定义是有效的，但根据 CLRS 的定义是无效的。
有趣的旁白：
- 两个定义都包含2-3-4 trees, which are trees with (min, max) = (2,4). It is a B-tree with Knuth order k = 4 and it's a CLRS B-tree with degree t = 2. These trees are closely related to Red-Black Trees.
- 只有 Knuth 的定义包括 2-3 trees, where (min, max) = (2,3). A 2-3 tree is a Knuth B-tree with Knuth order k = 3. It is not a valid CLRS B-tree. It's a shame that CLRS don't include this tree because they are closely related to AA trees.