2

B ツリーの最大の深さをどのように把握しますか?

次数が 1625 の B ツリーがあるとします。つまり、各ノードには 1625 のポインターと 1624 の要素があります。

85,000,000 個のキーが含まれている場合、ツリーの最大の深さは?

4

6 に答える 6

5

次数 m の B ツリーの最悪の場合の高さは、log m/2 n です。

参照: http://en.wikipedia.org/wiki/B-tree#Best_case_and_wost_case_heights

于 2010-04-05T22:25:40.340 に答える
5

仮定

  • 質問で定義された順序の理解

    具体的には、ノードごとに 1625 個のポインターを持つことが期待できます (順序の意味によっては、キーまたはポインターの最大数として定義されるため、以下で計算されるツリー サイズが大きくなる可能性があります)。

  • リーフ ノードも 1625 レコード (またはこれらのレコードへのポインター) を格納するという事実

... このツリーの最小の深さは 3 です。つまり、ルート ノード、非葉ノードの 1 つの層、および葉ノードの層があります。... このツリーの最大深度も 3 になります。

最適なケースで深さを計算するには:

  • レコードの総数 85,000,000 を次数 1,625 で割る

    これにより、リーフ行の数が得られます: 52,308

  • このリーフ行数を次数で割ります

    これは 33 になります。この数は、分割を停止できる順序よりも小さく、これはルート ノード内のポインターの数です。この数が 1 つのノードが保持できる数を超えていた場合、余分なレベルがあり、分割を続けます。

ツリーの深さが 3 になるように 2 つの分割を行いました。

すべてのノードを分割する必要があり、平均して order/2 (丸めなし) ポインターを保持する必要がある場合は、最悪のケースが発生します。最悪の場合の計算も同様です。次数 / 2 、つまりこの場合は 812.5 で除算するだけで、104,616 個のリーフ ノード、リーフの上のレベルで 129 個の非リーフ ノード、そして最後にこれらを追跡するための 1 つのルートが生成されます。 129 個の非リーフ ノード。

于 2010-04-05T22:35:11.667 に答える
1

B ツリーはバランスが取れており、最悪の場合の検索はその高さによって制限されます。容量順の B ツリーの各ノードにはdがあります。最大深度 = 最悪の場合

日=1624/2=812

高さ <= log d+1 ((n+1)/2)+1

答えは log 812+1 ((85,000,000+1)/2)+1

于 2014-12-30T14:02:50.993 に答える
0

最大の深さは、ツリーを操作するために使用されるアルゴリズムと、それらの最悪の場合の動作が何であるかによって異なります (詳細はわかりません、申し訳ありません)。おおよその深さは log(N)/log(1625) であり、完全なバランスが取れていると仮定します。

B+ ツリーは葉だけがキーを保持するため、少し深いかもしれませんが、その違いはおそらく無視できる程度です。また、リーフ以外の各ノードがポインターを保持するだけでよいと考えると、より浅くなる可能性もあります。

于 2010-04-05T22:24:04.773 に答える
0

ab ツリーの最大深度の式は、Can Berk Güder によって既に与えられています。あなたの場合、m = 1625

ただし、ポインターの数が奇数でキーの数が偶数の場合、ノードがいっぱいになったときにノードを不均等に分割する必要があるため、お勧めできません。

むしろ、ノードを均一に分割するために、ノードごとに奇数のキーと偶数のポインターを保持する必要があります。

于 2012-04-26T07:08:28.743 に答える