首页 > 试题广场 >

极端情况下,B-树中根以外所有节点只有ém2ù个分支,空间

[问答题]

极端情况下,B-树中根以外所有节点只有ém/2ù个分支,空间使用率大致仅有50%。而若按照教材8.2节介绍的方法,简单地将上溢节点一分为二,则有较大的概率会出现或接近这种极端情况。

为提高空间利用率,可将内部节点的分支数下限从m/2提高至2m/3。二是,一旦节点v发生上溢且无法通过旋转完成修复,即可将v与其(已经饱和的某一)兄弟合并,再将合并节点等分为三个节点。采用这一策略之后,即得到了B-树的一个发种,称作B*-树(B*-tree)[39][40]

当然,实际上不必真地先合二为一,再一分为三。可通过更为快捷的方式,达到同样的效枅:从来自原先两个节点及其父节点的共计m + (m - 1) + 1 = 2m个关键码中,取出两个上交给父节点,其余2m - 2个则尽可能均衡地分摊给三个新节点。
 a)按照上述思路,实现B*-树的关键码插入算法;
b) 与 B-树相比,B*-树的关键码删除算法又有何不同?
c) 按照你的极想,实现 B*-树的关键码删除算法。

这道题你会答吗?花几分钟告诉大家答案吧!