12

TツリーとB-/B+ツリーの定義を調べました。Web上の論文から、ディスクドライブやキャッシュメモリなどの階層メモリでBツリーのパフォーマンスが向上することがわかりました。

私が理解できないのは、フラットメモリでもTツリーが使用された理由です。

それらは、AVLツリーのスペース効率の良い代替手段として宣伝されています。

最悪の場合、Tツリーのすべてのリーフノードには1つの要素のみが含まれ、すべての内部ノードには許容される最小量が含まれます。これはほぼ満杯です。これは、割り当てられたスペースの平均で半分しか使用されないことを意味します。私が誤解しない限り、これは、Bツリーのノードが半分いっぱいになっている場合のBツリーの最悪の場合と同じ使用率です。

両方のツリーがキーをノードにローカルに格納し、ポインタを使用してレコードを参照すると仮定すると、唯一の違いは、Bツリーが各ブランチのポインタを格納する必要があることです。これにより、キーのサイズにもよりますが、通常、最大50％以下のオーバーヘッド（Tツリーに対して）が発生します。実際、これは、親ポインター、ノードに埋め込まれたレコード、レコードに埋め込まれたキーがないと仮定すると、AVLツリーで予想されるオーバーヘッドに近いものです。これは、代わりにBツリーを使用できないようにする期待される効率の向上ですか？

Tツリーは通常、AVLツリーの上に実装されます。AVLツリーはBツリーよりもバランスが取れています。これはTツリーのアプリケーションと関連付けることができますか？

4

2 に答える 2

3

答えの半分をカバーする個人的な話をすることができます。つまり、約 18 年前にB+ ツリーをプログラムするための Pascal コードを書いた理由です。

私のターゲット システムは 2 つのディスク ドライブを備えた PC でした。インデックスを不揮発性メモリに保存する必要があり、大学で学んだことをよりよく理解したいと考えていました。私は商用パッケージのパフォーマンスに非常に不満を持っていました.おそらくDBase III、またはいくつかのFox製品です.覚えていません.

とにかく：これらの操作が必要でした：

  • 調べる
  • 挿入
  • 消す
  • 次の項目

  • 前のアイテム

  • インデックスの最大サイズが不明でした

  • そのため、データはディスク上に存在する必要がありました
  • サポートへのアクセスごとにコストが高かった
  • ブロック全体の読み取りコストは、1 バイトの読み取りと同じです

B+ ツリーによって、その小さくて遅い PC が実際にデータを飛び回るようになりました。

リーフには 2 つの余分なポインターがあったため、順次検索用に二重にリンクされたリストが形成されました。

于 2011-02-11T22:49:37.887 に答える
2

実際には、違いは使用するシステムにあります。大学の私の家庭教師がコメントしたように、問題がメモリ不足にある場合、または hdd 不足にある場合は、どのツリーとどの実装で使用するかが決まります。ほとんどの場合、それは B+ ツリーになります。

数百の実装があるため、たとえば、思考要素をループする必要がある 2 方向キューと 1 方向キューを使用し、インデックスを格納して取得する方法が複数あるため、実装の実際の短所と短所が決まります。

于 2011-02-25T08:02:35.077 に答える