BツリーはAVLやRedBlack-Treeよりも高速ですか？ [閉まっている]

https://stackoverflow.com/questions/647537

22-07-2019
|

質問

パフォーマンスは決して白黒ではなく、多くの場合、1つの実装はXの場合はより速く、Yの場合はより遅いなどです。 AVLツリー（およびRedBlackツリーも）を実装するのはかなり複雑ですが、より高速です（複雑さは報われますか？）

編集：高速の場合は、同等のAVL / RedBlackツリー（ノード/コンテンツの観点から）-なぜが高速であるかを追加したい

解決

Seanの投稿（現在受け入れられている投稿）には、いくつかの誤った主張が含まれています。申し訳ありませんが、ショーン、失礼なつもりはありません。私の声明が事実に基づいていることを納得していただければ幸いです。

これらはユースケースがまったく異なるため、比較することはできません。

これらは両方とも、完全に順序付けられたアイテムのセットを、高速なルックアップ、挿入、削除で維持するために使用されます。それらは同じインターフェースと同じ意図を持っています。

RBツリーは通常、データへの高速アクセス（理想的にはO（logN））を提供するために使用されるメモリ内構造です。 [...]

常に O（log n）

Bツリーは通常、ディスクベースの構造であるため、インメモリデータよりも本質的に低速です。

ナンセンス。検索ツリーをディスクに保存する場合、通常はBツリーを使用します。それは本当です。ディスクにデータを保存すると、メモリ内のデータよりもアクセスが遅くなります。ただし、ディスクに保存されている赤黒ツリーは、メモリに保存されている赤黒ツリーよりも低速です。

ここでリンゴとオレンジを比較しています。本当に興味深いのは、メモリ内のBツリーとメモリ内の赤黒ツリーの比較です。

[余談ですが、赤黒木とは対照的に、BツリーはI / Oモデルで理論的に効率的です。ソート用のI / Oモデルを実験的にテスト（および検証）しました。 Bツリーでも機能すると期待しています。]

Bツリーはめったに二分木ではありません。ノードが持つことのできる子の数は通常、多数です。

明確にするために、Bツリーノードのサイズ範囲はツリーのパラメーターです（C ++では、テンプレートパラメーターとして整数値を使用できます）。

Bツリー構造の管理は、データが変更されると非常に複雑になる場合があります。

赤黒の木よりも理解（および実装）がはるかに簡単であることを覚えています。

Bツリーは、ディスクアクセスの数を最小限に抑えて、データの取得が合理的に決定されるようにします。

それは事実です。

非常にデータベース内のビットのデータを検索するために必要な4つのBツリーアクセスのようなものを見るのは珍しいことではありません。

データを取得しましたか

ほとんどの場合、インメモリRBツリーの方が高速だと思います。

データを取得しましたか

ルックアップはバイナリであるため、何かを見つけるのは非常に簡単です。 Bツリーはノードごとに複数の子を持つことができるため、各ノードで適切な子を探すためにノードをスキャンする必要があります。これはO（N）操作です。

各ノードのサイズは固定パラメーターであるため、線形スキャンを実行してもO（1）になります。各ノードのサイズを大きくした場合、通常は配列をソートしたままにして、O（log n）になるようにします。

RBツリーでは、比較を1回行ってから分岐するため、O（logN）になります。

あなたはリンゴとオレンジを比較しています。 O（log n）は、Bツリーの場合と同様に、ツリーの高さが最大でO（log n）であるためです。

また、赤黒の木で厄介な割り当てのトリックをプレイしない限り、Bツリーの方がキャッシュ動作が優れていると推測するのが妥当と思われます（場所に散らばっているポインタではなく、配列にアクセスし、割り当てが少ないメモリの局所性をさらに高めるオーバーヘッド）、これは速度の競争に役立つ可能性があります。

Bツリー（特にサイズパラメータ32および64）は、小さなサイズの赤黒ツリーと非常に競争力があり、適度に大きいnの値に対しても優れているという実験的証拠を示すことができます。 http://idlebox.net/をご覧ください。 2007 / stx-btree / stx-btree-0.8.3 / doxygen-html / speedtest.html

Bツリーは高速です。どうして？私は考えますメモリの局所性、キャッシュ動作の改善、ポインターの追跡の減少（同じものではないにしても、ある程度重複している）が原因であると考えてください。

他のヒント

実際、Wikipediaには、すべてのRBツリーがBツリーとして簡単に表現できることを示す素晴らしい記事があります。サンプルとして次のツリーを使用します。

これをBツリーに変換するだけです（これをより明確にするために、ノードはまだR / Bに色付けされていますが、Bツリーには通常ありません）：

Bツリーと同じツリー

（何らかの奇妙な理由でここに画像を追加することはできません）

他のRBツリーについても同様です。この記事から引用しています：

http://en.wikipedia.org/wiki/Red-black_tree

この記事から引用するには：

赤黒木はのBツリーと構造的に同等注文4、最小充填率クラスターごとの値の33％ 3つの値の最大容量。

どちらか一方が他方よりもはるかに優れているというデータは見つかりませんでした。もしそうだったら、どちらか一方はすでに死んでいたと思います。メモリに保存する必要のあるデータの量と、ツリーからノードを追加/削除するのがどれほど複雑かという点で異なります。

更新：

個人的なテストでは、データ検索の際にBツリーの方が優れていることが示唆されています。これは、Bツリーがデータの局所性に優れているため、CPUキャッシュが比較的高速に比較できるためです。 Bツリーの次数が高い（順序はノートが持つことができる子の数です）ほど、ルックアップは速くなります。一方、新しいエントリを追加および削除する場合、順序が高いほどパフォーマンスが低下します。これは、ノード内に値を追加すると線形の複雑さが生じるためです。各ノードはソートされた配列であるため、要素を中央に追加する場合、その配列内で多くの要素を移動する必要があります。新しい要素の左側にあるすべての要素を1つ左に移動するか、すべての要素を新しい要素を1つ右に移動する必要があります。挿入中に値が1つのノードを上に移動する場合（Bツリーで頻繁に発生します）、すべての要素を左から1つ右に移動するか、すべての要素を左に1つ右の位置。これらの操作（通常Cでmemmoveによって実行される）は、実際にはO（n）です。したがって、Bツリーの次数が高いほど、ルックアップは速くなりますが、変更は遅くなります。一方、低すぎる順序（3など）を選択した場合、Bツリーは実際には他のツリー構造と比べて利点または欠点がほとんどありません（そのような場合、他のものを使用することもできます）。したがって、常に高次のBツリーを作成します（少なくとも4、8以上は問題ありません）。

多くの場合Bツリーに基づいているファイルシステムは、はるかに高い次数（200以上、さらにはそれ以上）を使用します-これは、通常、ノート（許可された要素の最大数を含む場合））は、ハードドライブ上のセクターまたはファイルシステムのクラスターのサイズに等しくなります。これにより、最適なパフォーマンス（HDは一度に完全なセクターのみを書き込むことができるため、1バイトだけを変更しても、完全なセクターは書き換えられます）と最適なスペース使用率（ドライブ上の各データエントリが少なくともデータが実際にどれほど大きいかに関係なく、1つのクラスターまたはクラスターサイズの倍数です）。ハードウェアはデータをセクターと見なし、ファイルシステムはセクターをクラスターにグループ化するため、Bツリーは他のツリー構造よりもはるかに優れたパフォーマンスとファイルシステムのスペース使用率を実現できます。そのため、ファイルシステムで非常に人気があります。

アプリが常にツリーを更新し、値を追加または削除する場合それから、RB-TreeまたはAVL-Treeは、高次のB-Treeと比較して、平均してより良いパフォーマンスを示す場合があります。ルックアップではやや悪化し、より多くのメモリが必要になる場合がありますが、通常、変更は高速です。実際、RB-TreeはAVL-Treeよりも修正がさらに高速です。そのため、AVL-Treeは通常、深さが浅いため、ルックアップでは少し高速です。

したがって、いつものように、アプリの動作に大きく依存します。私の推奨事項：

多くの検索、わずかな変更：Bツリー（高次）
多くの検索、多くの変更：AVL-Tree
少しの検索、多くの変更：RB-Tree

これらすべてのツリーに代わるものは、 AAツリーです。この PDFペーパーが示唆するように、AA-Trees（ RBツリーのサブグループ）は、通常のRBツリーとパフォーマンスがほぼ同じですが、RBツリー、AVLツリー、またはBツリーよりも実装がはるかに簡単です。これは完全な実装です。どのくらい小さいかを見てください（メイン関数は実装の一部ではなく、実装行の半分は実際にはコメントです）。

PDFペーパーが示すように、 Treap も、従来のツリー実装の興味深い代替手段です。 Treapもバイナリツリーですが、バランスを強制しようとはしません。不均衡なバイナリツリーで発生する可能性のある最悪のシナリオ（ルックアップがO（log n）ではなくO（n）になる）を回避するために、Treapはツリーにランダム性を追加します。ランダム性は、ツリーのバランスが取れていることを保証することはできませんが、ツリーのバランスが極端に崩れている可能性は非常に低くなります。

メモリ内でのみ動作するBツリー実装を妨げるものはありません。実際、キー比較が安価な場合、1つのノードに複数のキーをパックすると検索中にキャッシュミスが少なくなるため、メモリ内のBツリーは高速になります。パフォーマンスの比較については、こちらのリンクをご覧ください。引用：<！> quot;速度テストの結果は興味深いものであり、16,000を超えるアイテムを含むツリーではB +ツリーが非常に高速であることを示しています。<！> quot; （B + TreeはBツリーの単なるバリエーションです。）

質問は古いですが、まだ関連があると思います。 Jonas K <！>＃246; lkerとMeckiは非常に良い答えを出しましたが、答えがすべてを網羅しているとは思いません。私は議論全体がポイントを欠いているとさえ主張します:-)。

エントリが比較的小さい場合（整数、小さな文字列/単語、フロートなど）、Bツリーについて言われたことは真実です。エントリが大きい（100Bを超える）場合、差異は小さく/わずかになります。

Bツリーに関する主なポイントをまとめましょう：

これらは、メモリの局所性により、バイナリ検索ツリー（BST）よりも高速です（キャッシュとTLBミスが少なくなります）。
Bツリーは、エントリが比較的多い場合、通常はスペース効率が高くなります小さいか、エントリのサイズが可変の場合。空き領域管理はより簡単（より大きなメモリチャンクを割り当てる）および追加のメタデータエントリごとのオーバーヘッドは低くなります。 Bツリーはノードとしてスペースを浪費します常にいっぱいではありませんが、それでもなおコンパクトになりますそのバイナリ検索ツリー。
Oの大きなパフォーマンス（O（logN））は、両方で同じです。さらに、各Bツリーノード内でバイナリ検索を実行すると、BSTと同じ数の比較になります（これを検証するのは素晴らしい数学の練習です）。 Bツリーノードのサイズが適切な場合（1〜4倍のキャッシュラインサイズ）、各ノード内の線形検索は、ハードウェアのプリフェッチ。また、SIMD命令を使用して基本的なデータ型（整数など）を比較します。
Bツリーは圧縮に適しています。ノードごとに圧縮するデータが多くなります。場合によっては、これは大きなメリットになります。インデックスの構築に使用されるリレーショナルデータベーステーブルの自動インクリメントキーを考えてください。 Bツリーのリードノードには、非常によく圧縮される連続した整数が含まれています。
Bツリーは、セカンダリストレージ（ブロックIOを実行する必要がある場所）に格納されている場合、明らかにはるかに高速です。

論文では、Bツリーには多くの利点があり、ほとんど欠点はありません。最高のパフォーマンスを得るには、Bツリーを使用する必要がありますか？

ツリーがメモリに収まる場合、答えは通常NOです。パフォーマンスが重要な場合、スレッドセーフなツリーのようなデータ構造が必要です（簡単に言えば、複数のスレッドが単一のスレッドよりも多くの作業を行うことができます）。 Bツリーを作成して並行アクセスをサポートすることは、BSTを作成するよりも問題が多くなります。ツリーが同時アクセスをサポートするようにする最も簡単な方法は、ノードをトラバース/変更しているときにロックすることです。 Bツリーでは、ノードごとにより多くのエントリをロックするため、より多くのシリアル化ポイントと競合ロックが発生します。

すべてのツリーバージョン（AVL、赤/黒、Bツリー、その他）には、並行処理のサポート方法が異なる無数のバリアントがあります。大学のコースで学んだり、入門書から読んだりするバニラアルゴリズムは、実際にはほとんど使用されません。そのため、各ツリーの背後にある正確なアルゴリズムに関する公式の合意がないため、どのツリーが最適に機能するかを言うのは困難です。言及されたツリーは、正確なデータ構造ではなく、特定のツリーのような不変式に従うデータ構造クラスのように考えることをお勧めします。

たとえばBツリーを取得します。バニラBツリーは実際に使用されることはほとんどありません。うまく拡張することはできません。使用される最も一般的なBツリーバリアントは、B +ツリー（ファイルシステム、データベースで広く使用されています）です。 B + -TreeとB-Treeの主な違い：1）エントリをツリーの内部ノードに格納しない（したがって、内部ノードに格納されたエントリを変更するときにツリーの高い書き込みロックを必要としない） ; 2）同じレベルのノード間にリンクがあります（したがって、範囲検索を行うときにノードの親をロックする必要はありません）。

これが役立つことを願っています。

Googleの男たちは最近、Bツリーに基づいたSTLコンテナの実装をリリースしました。彼らは、バージョンが高速で、赤黒木を介して実装された標準のSTLコンテナと比較してメモリの消費が少ないと主張しています。詳細はこちら

一部のアプリケーションでは、BツリーはBSTよりもかなり高速です。ここにある木：

http://freshmeat.net/projects/bps

非常に高速です。また、ノードごとに2つまたは3つのポインターのBSTインフラストラクチャと、バランシング情報を保持するためのいくつかの追加フィールドを必要としないため、通常のBST実装よりも少ないメモリを使用します。

これらはさまざまな状況で使用されます。通常、ストレージはディスクページであるため、ツリーノードをストレージに保持する必要がある場合にBツリーが使用されます。この制約がない場合、RBツリーが使用されます。したがって、リレーショナルデータベースインデックスを（たとえば）実装したい場合、Bツリーはおそらく高速になりますが、メモリ内検索では（たとえば）RBツリーはおそらく高速になります。

これらはすべて同じ漸近動作を持っているため、パフォーマンスは使用しているツリーのタイプよりも実装に大きく依存します。ツリー構造のいくつかの組み合わせは、実際には最速のアプローチであり、Bツリーの各ノードがキャッシュラインに正確に適合し、各ノード内の検索に何らかのバイナリツリーが使用されます。ノードのメモリを自分で管理することで、キャッシュの局所性をさらに高めることもできますが、非常に高価です。

個人的には、使用している言語の標準ライブラリにあるものを何でも使用します。これは、非常に小さなパフォーマンスゲイン（もしあれば）のための多くの作業です。

理論上の注意... RBツリーは、実際にはBツリーと非常によく似ています。これは、RBツリーが2-3-4ツリーの動作をシミュレートするためです。 AAツリーも同様の構造で、2〜3本のツリーをシミュレートします。

さらに...赤黒木の高さはO（log [2] N）であるのに対し、B-treeの高さはO（log [q] N）で、ceiling [N] <！> lt; = q <！> lt; = Nしたがって、Bツリーの各キー配列（上記のように固定されている）での比較を考慮すると、Bツリーの時間の複雑さ<！> lt; =赤黒ツリーの時間の複雑さ。（ブロックサイズとサイズが等しい単一レコードの場合は等しい）

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow