B树中的节点数

Question

在具有最小度数为t的B树中，除root之外的每个非叶节点至少有t个孩子和至多2 * t个孩子。假设将键{1,2,3 ...，n}插入到序列1,2,3 .....，n中具有最小次数2的空B树中。最终的B树有多少个节点？

从我所了解的情况来看，我觉得它会是n/t，因为每个节点可以拥有的最小密钥数是k，而密钥的总数是n。我对么？？如果不能告诉我我要去哪里，我该怎么做？

Answer 1

答案是(n-2)*log(n-2)与t=2

Answer 2

我们知道，除了根每个节点必须至少有T-1 = 1键，最多2T-1 = 3个键。当n≥2时，最终的树最多可以有n-1个节点。除非n = 1，否则不能有n个节点，因为我们只将密钥插入非空节点，所以总是会有至少一个带有2个密钥的节点。接下来观察一下，我们将永远不会有一个以上的密钥在一个不是我们B-树的正确脊柱的节点中。这是因为我们插入的每个密钥都大于存储在树中的所有密钥，因此它会插入到树的右侧脊柱中。当右侧脊柱中除最深节点之外的每个节点具有2个键并且右侧样条中最深的节点具有3个键时，可能的节点数量最少。因此，在高度为1,1节点，在高度为2,3的节点，...，在h级，2h-1节点。在这种情况下，n =Σ（i = 1）^ h^2^i + 1 = 2h + 1-1其中，h是B树的高度，并且B树中的节点数是＃节点=Σ（i = 1）^ h'〖（2^i-1）〗= 2h + 1-2-h = n-lg（n + 1）。因此，对于任何n，最终的B树必须有n-⌊lg（n + 1）⌋≤＃nodes≤n-1（如果n≥2）。