B 树中键的最大和最小数量

Question

阶数为 128、高度为 3 的 B 树中可以存储的键的最大和最小数量是多少？

为了最大化，这就是我所做的： 您有一个根节点。根节点可以拥有的最大子节点为 m（阶），即 128。这 128 个子节点中的每一个都有 128 个子节点，因此总共有 1+128+16384=16512 个节点。根据 Wikipedia，n 个节点的 B 树可以存储 n-1 个键，因此最多可以有 16511 个键。

对于分钟： 您有一个根节点，它可以拥有的最小子节点数为 2，这 2 个子节点可以拥有的最小子节点数为 m/2，其中 m 是阶数，因此每个子节点有 64 个。这样我们总共有 1+2+64+64=131 个子节点和 131-1=130 个键。

我在这里所做的正确吗？

Answer 1

根据维基百科，如果一个节点有 n 个子节点，则它最多可以有 n-1 个键。
所以 ，

                           root [127keys]
                 128 childnodes [each having 127 keys]
             128*128 childnodes [each having 127 keys]

127+128*127+128*128*127 = total no of maximum allowed keys

Answer 2

节点可以包含的键数量有下限和上限。这些界限用固定整数 t >= 2 表示，称为 B 树的最小度数。

• 除根之外的每个节点都必须至少有 t - 1 个键。
  除根之外的每个内部节点至少有 t 个子节点。
  如果树非空，则根必须至少有一个键。

• 每个节点最多可以包含 2t - 1 个键。
  因此，一个内部节点最多可以有 2t 个子节点。
  如果一个节点正好包含 2t - 1 个键，我们就说它是满的。

高度 3 的最大键数 = (2t-1) + (2t-1) * 2t + (2t-1) * 2t * 2t
高度 3 的最小键数 = (t-1) + (t-1)*t + (t-1) * t * t

Answer 3

这实际上取决于您如何定义顺序。根据 Knuth 的说法，b 树的阶数是子节点的最大数量，这意味着最大答案是 129。如果阶数的定义是非根节点的最小键数，则答案为最大值未知。

使用 this 定义，您的最小值计算是正确的，但最大值是不是，因为每个节点（包括叶子节点）都包含 m-1 个键。这也与Cormen中B-Tree的定义一致。如果n是16512，并且每个n存储127个密钥，那么答案肯定不是16511。

Answer 4

下面的 C# 代码用于计算给定级别数和节点可以拥有的最大子节点数的任何 B 树的最大键数。

        /// <summary>
        /// Given number of levels in the tree, computes the maximum number of keys the tree can hold. 
        /// </summary>
        /// <param name="levelCount">Is the number of levels in the tree. </param>
        /// <param name="MaxBranchingDegree ">Is the maximum number of children a node in the tree can have. </param>
        /// <returns>Maximum number of keys a tree with <paramref name="levelCount"> levels can hold. </returns>
        public int ComputeMaxKeyCount(int levelCount, int MaxBranchingDegree )
        {
           int maxKeys = 0;
           for (int l = 0; l < levelCount; l++)
           {
              maxKeys += (MaxBranchingDegree - 1) * (int)Math.Pow(MaxBranchingDegree, l);
           }
           return maxKeys;
        }