分析b-tree的高度
提问于 2014-10-03 08:29:11
我在下面的位置读到有关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，对吗？
回答 1
Stack Overflow用户
发布于 2014-11-06 18:24:10
听着，当根节点在级别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)。
如果你仍然不理解，只需阅读基础知识。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/26175689
复制相关文章
腾讯云开发者
