0

私はDBMSでBツリーとB+ツリーを学びました。nが特定のツリーに対して修正されているのに、ツリー内の非リーフノードが[n/2]からn個の子を持つ理由がわかりません。

何故ですか？そしてその利点は？

ありがとう ！

4

2 に答える 2

1

これは、B+ ツリーと B ツリーのバランスを取る機能であり、そのおかげで、ツリー上の操作の複雑さを簡単に計算し、それを O(logn) [ここで、n はデータセット内の要素の数です] にバインドできます。 ]。

  • ノードが B 個以上の息子を持つことができる場合、深さ 2 のツリーを作成できます: ルートであり、他のすべてのノードはルートからの葉になります。要素の検索は、目的の O(logn) ではなく、O(n) になります。
  • ノードが B/2 未満の息子を持つことができる場合、高さ n のリンク リスト [n ノード、それぞれ 1 息子] であるツリーを作成できます。検索操作は、代わりに O(n) になります。 O(ログ)

小さな修正: すべての非リーフ ノード (ルートを除く) には、B/2 から B の子があります。ルートだけでは、B/2 未満の息子を持つことができます。

于 2011-12-20T09:03:54.380 に答える
0

この構造の基本的な前提は、ブロック サイズが固定されていることです。これが、各内部ブロックにnその子にインデックスを付けるためのスロットがある理由です。

満杯の (正確に子を持つ) ブロックに子を追加する必要がある場合n、ブロックは 2 つのブロックに分割され、親のインデックス内の元のブロックが置き換えられます。2 つのブロックのそれぞれの子の数は明らかにn div 2(偶数であると仮定n)。これが下限の由来です。

親がいっぱいの場合、操作はルート自体まで繰り返される可能性があります。

分割操作とn/2-filled ブロックの許可により、ほとんどの挿入/削除は、ツリーの巨大な部分を再調整するのではなく、局所的な変更のみを引き起こすことができます。

于 2011-12-20T12:14:09.217 に答える