分析b-tree的高度

Question

我在下面的位置读到有关B树的信息

http://www.brpreiss.com/books/opus4/

这里作者正在分析B-树的高度。

在高度为>= 0，阶为M的B-树中，最小键数为Nk =2* >= (M/2) ^h -1

：证明很明显，高度为零的B-树至少包含一个节点。考虑一个B树的顺序M和高度h>0。根据定义，每个内部节点(根节点除外)至少有天花板(M/2)子树。这意味着内部节点中包含的键的最小数量是(M/2)-1。0级的最小键数为1；1级时为2(celing(M/2)-1)；2级时为2(ceiling (m/2)(Ceiling(M/2)-1) )

我的问题是，作者是如何得出1级kesy的最小数目为2(celing(M/ 2 )-1)和2级的结论？

例如，如果M是2，那么level1的最小键数是0，对吗？

Answer 1

听着，当根节点在级别1有两个subtrees.So时，级别1的密钥数量将是最小的。考虑到级别2，我们有两个nodes.Therefore级别1的密钥的最小数量= 2(celing(M/2)-1).Now

1 )对于级别1的节点，有2(上限(m/2))个子树(最小)。

2)这里2级键的最小数目是2(ceiling (m/2))*(ceiling(m/2) -1)。

如果你仍然不理解，只需阅读基础知识。