3阶B-树每个结点最多包括3-1
=
2个关键字，自然子树个数最多为3棵
这个后面的计算假设这个叶子不是B-树的外结点
第一层最多
1个结点
第2层最多3个结点
第3层最多3^2个结点
第4层最多3^3个结点
结点总数为1
+
3
+
9
+
27
=
40，因此关键字最多为40*2=80个
按照定义，b-树的根结点最少可以只有一个关键字，普通结点最少2个关键字
所有结点最多有4个关键字
因此，最少时有最大高度，下面是关键字数：
第1层：1个
第2层：（1+1）*2=4
第3层：2
*（2+1）*2=12
第4层：2*（2+1）*（2+1)*2=
36
1+
4+12+36=
53，因此最大高度为4
最多时的关键字数：
第1层：4个
第2层：(4+1)
*
4
=
20个
第3层：(4+1)
*(4
+
1)
*4
=
100
20
+
4
=
24
<
53,
24
+
100
=
124
>
53
，因此最小高度为3
3阶B-树除根结点外每个非叶子结点最多包括3-1
=
2个关键字，每个结点的度最多为3
第1层最多
1个结点（根结点只有一个关键字）
第2层最多3个结点
第3层最多3^2个结点
第4层最多3^3个结点
关键字总数为1+（3+9+27）*2=79
内容全部来源于网络收集，如有侵权，请联系网站删除！
QQ：24596024