B树的性能分析
答案:1 悬赏:40 手机版
解决时间 2021-02-12 18:58
- 提问者网友：了了无期
- 2021-02-12 04:28
B树的性能分析
最佳答案
- 五星知识达人网友：老鼠爱大米
- 2021-02-12 04:48
设B-树包含N个关键字，因此有N+1个叶子结点，叶子都在第I层。因为根至少有两个孩子，因此第二层至少有两个结点。除根和叶子外，其它结点至少有┌m/2┐个孩子，因此在第三层至少有2*┌m/2┐个结点，在第四层至少有2*(┌m/2┐^2)个结点，．．．，在第I层至少有2*(┌m/2┐^(l-2) )个结点，于是有：
N+1 ≥ 2*┌m/2┐I-2
考虑第L层的结点个数为N+1，那么2*(┌m/2┐^(l-2)）≤N+1，也就是L层的最少结点数刚好达到N+1个
即： I≤ log┌m/2┐((N+1)/2 )+2
所以，当B-树包含N个关键关键字时，B-树的最大高度为l-1（因为计算B-树高度时，叶结点所在层不计算在内）
即：log┌m/2┐((N+1)/2 )+1。
这个公式保证了B-树的查找效率是相当高的。
N+1 ≥ 2*┌m/2┐I-2
考虑第L层的结点个数为N+1，那么2*(┌m/2┐^(l-2)）≤N+1，也就是L层的最少结点数刚好达到N+1个
即： I≤ log┌m/2┐((N+1)/2 )+2
所以，当B-树包含N个关键关键字时，B-树的最大高度为l-1（因为计算B-树高度时，叶结点所在层不计算在内）
即：log┌m/2┐((N+1)/2 )+1。
这个公式保证了B-树的查找效率是相当高的。
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯