在128阶和3阶的B树中可以存储的最大和最小键数是多少?
最大限度,这就是我所做的:你有一个单根节点。根节点可以拥有的最大子节点是m(顺序),因此是128.并且这128个子节点中的每一个都有128个子节点,因此总共有1 + 128 + 16384 = 16512个节点。根据维基百科,n个节点的B树可以存储n-1个密钥,因此最多可以留下16511个密钥。
对于min:你有一个单根节点,这个孩子可以拥有的最小子女数是2,这两个孩子可以拥有的最小孩子数是m / 2,其中m是顺序,每个64个孩子。这给我们留下了1 + 2 + 64 + 64 = 131个孩子和131-1 = 130个键。
我在这里做的是正确的吗?
这实际上取决于您如何定义订单。根据Knuth的说法,b树的顺序是最大子节点数,这意味着最大答案是129.如果顺序的定义是非根节点的最小键数,那么答案为最大值未知。
使用this定义,您的最小值计算是正确的,但您的最大值不是,因为每个节点(包括叶子)都包含m-1个键。这也与Cormen中B-Tree的定义一致。如果n是16512,并且每个n存储127个密钥,则答案肯定不是16511。
根据维基百科,如果节点具有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
节点可以包含的键数有下限和上限。这些边界用固定整数t> = 2表示,称为B树的最小程度。
高度最大键3 =(2t-1)+(2t-1)* 2t +(2t-1)* 2t * 2t 高度密钥最小3 =(t-1)+(t-1)* t +(t-1)* t * t
下面是C#代码,用于计算任何B-Tree的最大键数,给定级别数和节点可以拥有的最大子节点数。
/// <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;
}