B ツリーに格納されているキーの数と、B ツリーの順序 (つまり、非ルート ノードの子ポインターの最大数) がわかっている場合、単純な対数方程式で、木の高さは？
2267 次
1 に答える
2
ウィキペディアをチェックしてください：
ノードあたりの子の数を m とすると、すべてのノードが完全に満たされた高さ h の B ツリーには、n=mh−1 個のエントリがあります。
B ツリーの最適な高さは次のとおりです。
ceil( log_m(n+1) )
内部 (非ルート) ノードが持つことができる子の最小数を d とします。通常の B ツリーの場合、d=⌈m/2⌉ です。
B ツリーの最悪の場合の高さは次のとおりです。
floor( log_d( (n+1)/2 ) + 1 )
于 2013-10-09T23:31:17.393 に答える