7

2nですか？チェックしてるだけ。

4

4 に答える 4

13

用語
B ツリー の順序は、文献では一貫して定義されていません。
(たとえば、ウィキペディアの B-Tree に関する記事の用語セクションを参照してください)非リーフ ノードが保持できるキーの最小数で
あると考える著者もいれば、非リーフ ノードの子ノードの最大数であると考える著者もいます。ノードが保持できる可能性があります (これは、そのようなノードが保持できるキーの最大数よりも 1 つ多い数です)。
それでも、他の多くの人は、固定長のキー (および固定サイズのノード) を想定することであいまいさを回避します。これにより、最小値と最大値が同じになります。したがって、順序の 2 つの定義は、1 だけ異なる値を生成します (キーの数は常に子の数より 1 少ない数です。)

深さをリーフ レコードへの検索パスで見つかったノードの数として定義し、ルート ノードとリーフ ノードを含みます。その意味で、リーフ ノードを直接指しているルート ノードのみを持つ非常に浅いツリーの深さは 2 です。そのツリーが成長し、中間レベルの非リーフ ノードが必要になる場合、その深さは 3 になります。

次数 n の B-Tree にはいくつの要素を保持できますか?
固定長のキーを想定し、「順序」nが子ノードの最大数として定義されていると仮定すると、答えは次のようになります。

   (Average Number of elements that fit in one Leaf-node) * n ^ (depth - 1)

どのように計算しますか?...:
データ (「要素」) はリーフ ノードにのみ保持されます。したがって、保持される要素の数は、1 つのノードに収まる要素の平均数にリーフ ノードの数を掛けたものになります。
リーフ ノードの数自体は、非リーフ ノードに収まる子の数 (順序) によって決まります。たとえば、リーフ ノードのすぐ上の非リーフ ノードは、n 個 (順序) のリーフ ノードを指します。次に、この非葉ノードの上の非葉ノードは、n個の同様のノードなどを指します。したがって、「（深さ-1）の累乗」になります。

上記の式は、固定キー長と固定レコード長を想定するのではなく、(非リーフ ノードに保持されているキーとリーフ ノードに保持されている要素の) 平均を使用して一般的に成り立つことに注意してください。ツリーは通常、次のノード サイズを持ちます。キーとレコードのサイズに比例するため、葉に保持されるキーまたはレコードの有効な数が平均と比較して比較的わずかに変化するのに十分な数のキーまたはレコードを保持します。

例:深さ 4 (ルート ノード、2 レベルの非葉ノード、1 レベルの [明らかに] 葉ノード)
のツリーと順序 12 (非葉ノードは最大 11 個のキーを保持できるため、12 個のノードを指す) - ルートノードがその下の 12個   のノードを指している - その下の各ノードがその下の 12 個のノードを指している (したがって、レイヤーには 12 * 12 個のノードが存在することになる) "3" (ルートがレイヤー 1 などであると仮定すると、この番号付けもあいまいに定義されます...) - "レイヤー 3" の各ノードは 12 個のリーフノードを指します (したがって、12 * 12 * 12 個のリーフが存在します) - 各リーフノード   には 5 つの要素があります (この例の場合)


したがって..そのような木は保持されます...

  Nb Of Elements in said tree = 5 * 12 * 12 * 12
                              = 5 * (12 ^ 3)
                              = 5 * (12 ^ depth -1)
                              = 8640

3 行目の式を認識します。

B ツリーで一般的に注目に値することは、比較的浅いツリー (ルートと求められるレコードとの間の "ホップ" の数が限られているツリー) が比較的高い数のレコードを保持できることです。この数は、各レベルの次数で乗算されます。

于 2010-04-03T18:25:17.037 に答える
3

私の本によると、B ツリーの順序は、ノードに格納できるポインターの最大数です。(p. 348) 「キー」の数は、順序より 1 つ少なくなります。したがって、次数 n の B ツリーは n-1 個の要素を保持できます。

この本は、Michael J. Folk による「File Structures」第 2 版です。

于 2010-04-03T18:56:57.377 に答える
0

要素数の式に指数がどこかに含まれていない場合は、間違っています。

次数5の二分木は2^0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 + 2 ^ 4要素を保持できるため、31 ..（2 ^ order-1）です。

編集：順序と深さ/長さが混同されているようです。二分木の順序は一体何ですか？Bツリーについては、その定義の性質上、要素ごとに最大2つの子要素を保持していないかのように説明しているように見えます。

于 2010-04-04T00:01:10.563 に答える
0

B ツリーの順序を 'm' とは、b ツリーの同じレベルに挿入できるノードの最大数 = m-1 を意味します。その後、ノードは分割されます。例: 次数が 3 の場合、3 番目の要素の到着時に最大 2 つのノードのみを挿入できます。ノードは、二分探索木または自己平衡木のプロパティに従って分割されます。

于 2016-11-25T15:03:09.123 に答える