有效B+tree的最小数目是多少？

Question

我正试图对前几天考试中的一个关于B+tree的问题提出上诉。

问题是：

考虑以l为因子的B+tree (假设l为正且偶数)，h>=0为高度(考虑根为0)，n>=1为记录数。

有5个答案。其中3人我马上就被淘汰了，不得不在这两种情况中做出选择：

1. h>1 ==> n >= 0.5*l*(l+1)。第二个方向不能保证:这取决于钥匙的到达顺序。
2. 以上都不是。

我选择了(2)，讲师说它的选择(1)。我有一个我认为与之相矛盾的例子：

7 / \ 3 9 / \ / \ 1 2 3 4 5 7 8 9 10

使用l=4和h=2

• 这个b+tree是否代表一个有效的B+tree？
• 我的讲师真的错了吗？

我真的很想在这里提供一些帮助。这个例子是我上诉的好例子吗？

通常，在具有高度( n )和因子( l )的B+tree中，记录的最小数量是多少？

Answer 1

显然我是对的..。我展示的这棵树是合法的，并在对比讲师的答案。

通过按该顺序插入以下键：1, 2, 3, 4, 5, 6, 7, 8, 9, 10，然后将6从树中取出，将创建一个有效的height > 1和n<10 B+tree。

这与答案中的h>1 ==> n >= 0.5*l*(l+1)规则相矛盾.

经过多次尝试和大量官僚主义之后，讲师接受了我的回答，我得到了以下几点:)

谢谢你的尝试乔纳森·莱弗勒..。