B树中的最大和最小键数

Question

在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个键.

我在这里做的是正确的吗？

Answer 1

节点可以包含的键数有上限和下限。这些边界以固定整数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 2

根据维基百科,如果节点具有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 3

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

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