パフォーマンスが白黒になることは決してないことを私は知っています。多くの場合、1つの実装はXの場合は速く、Yの場合は遅くなりますが、一般的には、BツリーはAVLやRedBlackツリーよりも高速ですか？それらは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 の値が適度に大きい場合でも、B ツリーよりも優れているという実験的証拠を指摘できます。http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.htmlを参照してください。
B ツリーは高速です。なんで？これは、メモリの局所性、キャッシュ動作の改善、ポインター追跡の減少 (同じではないにしても、ある程度重複している) が原因であると推測します。
実際、ウィキペディアには、すべての RB ツリーが B ツリーとして簡単に表現できることを示す素晴らしい記事があります。次のツリーをサンプルとして取り上げます。
これを B-Tree に変換するだけです (これをより明確にするために、ノードはまだ R/B に色付けされています。これは通常、B-Tree にはありません)。
（奇妙な理由でここに画像を追加できません）
他の RB-Tree についても同様です。それはこの記事から取られた：
http://en.wikipedia.org/wiki/Red-black_tree
この記事から引用するには：
赤黒ツリーは、次数 4 の B ツリーと構造的に同等であり、クラスターあたりの値の最小フィル ファクターは 33% で、最大容量は 3 つの値です。
どちらか一方が他方よりも大幅に優れているというデータは見つかりませんでした。だとしたらどちらかはすでに死んでいたと思います。それらは、メモリに保存する必要があるデータの量と、ツリーからノードを追加/削除するのがどれほど複雑かという点で異なります。
私の個人的なテストでは、B ツリーの方がデータの局所性が高く、CPU キャッシュの比較が多少高速であるため、データを検索する場合は B ツリーの方が優れていることが示唆されています。B-Tree の順序 (順序とは、メモが持つことができる子の数) が高いほど、ルックアップが速くなります。一方、順序が高いほど、新しいエントリの追加と削除のパフォーマンスが低下します。これは、ノード内での値の追加が線形の複雑さを持つという事実によって発生します。各ノードはソートされた配列であるため、要素を中央に追加するときは、その配列内で多くの要素を移動する必要があります。新しい要素の左側にあるすべての要素を 1 つ左に移動するか、すべての要素を右側に移動する必要があります。新しい要素を 1 つ右に移動する必要があります。挿入中に値が 1 ノード上に移動すると (B ツリーで頻繁に発生します)、すべての要素を左の 1 位置から右に移動するか、すべての要素を右の 1 つの位置を左に。これらの操作 (C では通常 memmove によって実行される) は、実際には O(n) です。したがって、B ツリーの次数が高いほど、ルックアップは高速になりますが、変更は遅くなります。一方、選択した順序が低すぎる場合 (たとえば 3)、実際には、B ツリーは他のツリー構造よりも利点も欠点もほとんど示しません (このような場合は、別のものを使用することもできます)。したがって、私は常に高次の B-Tree を作成します (少なくとも 4、8、およびそれ以上は問題ありません)。すべての要素を左から 1 桁右に移動するか、すべての要素を右に 1 桁左に移動することによって、穴を埋める必要があります。これらの操作 (C では通常 memmove によって実行される) は、実際には O(n) です。したがって、B ツリーの次数が高いほど、ルックアップは高速になりますが、変更は遅くなります。一方、選択した順序が低すぎる場合 (たとえば 3)、実際には、B ツリーは他のツリー構造よりも利点も欠点もほとんど示しません (このような場合は、別のものを使用することもできます)。したがって、私は常に高次の B-Tree を作成します (少なくとも 4、8、およびそれ以上は問題ありません)。すべての要素を左から 1 桁右に移動するか、すべての要素を右に 1 桁左に移動することによって、穴を埋める必要があります。これらの操作 (C では通常 memmove によって実行される) は、実際には O(n) です。したがって、B ツリーの次数が高いほど、ルックアップは高速になりますが、変更は遅くなります。一方、選択した順序が低すぎる場合 (たとえば 3)、実際には、B ツリーは他のツリー構造よりも利点も欠点もほとんど示しません (このような場合は、別のものを使用することもできます)。したがって、私は常に高次の B-Tree を作成します (少なくとも 4、8、およびそれ以上は問題ありません)。一方、選択した順序が低すぎる場合 (たとえば 3)、実際には、B ツリーは他のツリー構造よりも利点も欠点もほとんど示しません (このような場合は、別のものを使用することもできます)。したがって、私は常に高次の B-Tree を作成します (少なくとも 4、8、およびそれ以上は問題ありません)。一方、選択した順序が低すぎる場合 (たとえば 3)、実際には、B ツリーは他のツリー構造よりも利点も欠点もほとんど示しません (このような場合は、別のものを使用することもできます)。したがって、私は常に高次の B-Tree を作成します (少なくとも 4、8、およびそれ以上は問題ありません)。
多くの場合 B ツリーに基づいているファイル システムは、はるかに高い次数 (200 次、さらにはそれ以上) を使用します。ハードドライブ上のセクターまたはファイルシステムのクラスターのサイズ。これにより、最適なパフォーマンス (HD は一度にフル セクターしか書き込むことができないため、たとえ 1 バイトが変更された場合でも、フル セクターはいずれにせよ書き換えられるため) と最適なスペース使用率 (ドライブ上の各データ エントリが少なくとも実際のデータの大きさに関係なく、1 つのクラスターまたはクラスター サイズの倍数です)。ハードウェアがデータをセクターとして認識し、ファイル システムがセクターをクラスターにグループ化するという事実が原因で、B-Tree は、他のどのツリー構造よりも、ファイル システムのパフォーマンスとスペースの使用率を大幅に向上させることができます。そのため、ファイル システムで非常に人気があります。
アプリがツリーを絶えず更新し、値を追加または削除している場合、RB ツリーまたは AVL ツリーは、高次の B ツリーと比較して、平均してより良いパフォーマンスを示す場合があります。ルックアップではやや悪化し、より多くのメモリが必要になる場合もありますが、そのため変更は通常高速です。実際には、RB ツリーは AVL ツリーよりも変更が高速です。そのため、AVL ツリーは通常、深さが浅いため、ルックアップが少し高速です。
したがって、いつものように、アプリが何をしているかに大きく依存します。私の推奨事項は次のとおりです。
これらすべてのツリーに代わるものはAA-Treesです。このPDF ペーパーが示唆するように、AA ツリー (実際には RB ツリーのサブグループです) は、通常の RB ツリーとパフォーマンスがほぼ同等ですが、RB ツリー、AVL ツリーよりも実装がはるかに簡単です。またはBツリー。これが完全な実装です。これがどれほど小さいか見てください(main-function は実装の一部ではなく、実装行の半分は実際にはコメントです)。
PDF ペーパーが示すように、Treapは従来のツリー実装の興味深い代替手段でもあります。Treap も二分木ですが、バランスを強制しようとはしません。不均衡なバイナリ ツリーで発生する可能性がある最悪のシナリオ (ルックアップが O(log n) ではなく O(n) になる) を回避するために、Treap はツリーにランダム性を追加します。ランダム性は、ツリーのバランスが取れていることを保証することはできませんが、ツリーが極端にバランスが取れていない可能性も非常に低くなります。
メモリ内でのみ機能するBツリーの実装を妨げるものはありません。実際、キーの比較が安価な場合、メモリ内のBツリーは、1つのノードに複数のキーをパックすると、検索中のキャッシュミスが少なくなるため、より高速になります。パフォーマンスの比較については、このリンクを参照してください。引用：「速度テストの結果は興味深いものであり、16,000を超えるアイテムを含むツリーではB+ツリーが大幅に高速であることを示しています。」（B + TreeはB-Treeの単なるバリエーションです）。
質問は古いですが、まだ関連性があると思います。Jonas Kölker と Mecki は非常に良い回答をしてくれましたが、その回答がすべてを網羅しているとは思いません。私は、議論全体が要点を欠いているとさえ主張します:-)。
B ツリーについて述べたことは、エントリが比較的小さい場合 (整数、小さな文字列/単語、浮動小数など) に当てはまります。エントリが大きい (100B を超える) 場合、差は小さくなり、重要ではなくなります。
B-Tree についての主なポイントをまとめましょう。
メモリの局所性により、バイナリ検索ツリー (BST) よりも高速です (その結果、キャッシュと TLB のミスが少なくなります)。
エントリが比較的小さい場合、またはエントリのサイズが可変の場合、B ツリーは通常、スペース効率が高くなります。空き領域の管理が容易になり (より大きなメモリ チャンクを割り当てる)、エントリごとの余分なメタデータ オーバーヘッドが少なくなります。B ツリーは、ノードが常にいっぱいであるとは限らないため、いくらかのスペースを浪費しますが、最終的には二分探索ツリーよりもコンパクトになります。
Big O のパフォーマンス ( O(logN) ) はどちらも同じです。さらに、各 B ツリー ノード内でバイナリ検索を実行すると、BST と同じ数の比較が行われることになります (これを確認するには、数学の演習が必要です)。B ツリー ノードのサイズが妥当な場合 (1 ～ 4 倍のキャッシュ ライン サイズ)、ハードウェアのプリフェッチにより、各ノード内の線形検索はさらに高速になります。基本的なデータ型 (整数など) を比較するために SIMD 命令を使用することもできます。
B ツリーは圧縮に適しています。ノードごとに圧縮するデータが多くなります。場合によっては、これが大きなメリットになることがあります。インデックスの作成に使用されるリレーショナル データベース テーブルの自動インクリメント キーについて考えてみてください。B ツリーのリード ノードには、非常によく圧縮される連続した整数が含まれています。
B ツリーは、セカンダリ ストレージ (ブロック IO を実行する必要がある場所) に格納すると、明らかにはるかに高速になります。
紙の上では、B ツリーには多くの利点があり、欠点はほとんどありません。では、最高のパフォーマンスを得るには B-Tree を使用する必要がありますか?
ツリーがメモリに収まる場合、答えは通常 NO です。パフォーマンスが重要な場合は、スレッドセーフなツリーのようなデータ構造が必要です (簡単に言えば、複数のスレッドが 1 つのスレッドよりも多くの作業を実行できます)。B-Tree が同時アクセスをサポートするようにすることは、BST を作成することよりも問題があります。ツリーで同時アクセスをサポートする最も簡単な方法は、ノードをトラバース/変更するときにノードをロックすることです。B ツリーでは、ノードごとにより多くのエントリをロックするため、シリアライゼーション ポイントが増え、ロックの競合が増えます。
すべてのツリー バージョン (AVL、Red/Black、B-Tree、その他) には、同時実行のサポート方法が異なる無数のバリアントがあります。大学のコースで教えられたり、入門書で読んだりするバニラ アルゴリズムは、実際にはほとんど使用されません。そのため、各ツリーの背後にある正確なアルゴリズムについて公式の合意がないため、どのツリーが最もパフォーマンスが良いかを判断するのは困難です。言及されたツリーは、正確なデータ構造ではなく、特定のツリーのような不変条件に従うデータ構造クラスのように考えることをお勧めします。
たとえば、B ツリーを考えてみましょう。通常の B ツリーは実際にはほとんど使用されません。うまくスケーリングすることはできません。使用される最も一般的な B-Tree バリアントは、B+-Tree (ファイル システム、データベースで広く使用されています) です。B+ ツリーと B ツリーの主な違い: 1) ツリーの内部ノードにエントリを格納しない (したがって、内部ノードに格納されたエントリを変更するときに、ツリーの上位にロックを書き込む必要はありません)。 ; 2) 同じレベルのノード間にリンクがある (したがって、範囲検索を行うときにノードの親をロックする必要はありません)。
これが役立つことを願っています。
Google の関係者は最近、B ツリーに基づく STL コンテナーの実装をリリースしました。彼らは、赤黒木を介して実装された標準の STL コンテナーと比較して、バージョンが高速であり、メモリ消費量が少ないと主張しています。詳細はこちら
一部のアプリケーションでは、B ツリーは BST よりも大幅に高速です。あなたがここで見つけるかもしれない木：
http://freshmeat.net/projects/bps
は非常に高速です。また、ノードごとに 2 つまたは 3 つのポインターの BST インフラストラクチャと、バランス情報を保持するためのいくつかの追加フィールドを必要としないため、通常の BST 実装よりも使用するメモリが少なくなります。
これらはさまざまな状況で使用されます。Bツリーは、ツリーノードをストレージにまとめて保持する必要がある場合に使用されます。通常、ストレージはディスクページであるため、リバランスには非常にコストがかかる可能性があります。この制約がない場合は、RBツリーが使用されます。したがって、リレーショナルデータベースインデックスを実装する場合はBツリーの方が高速である可能性がありますが、メモリ内検索の場合はRBツリーの方が高速である可能性があります。
さらに、赤黒の木の高さは O(log[2] N) ですが、B-tree の高さは O(log[q] N) です。ここで、ceiling[N]<= q <= N です。したがって、B ツリー (上記のように固定されている) の各キー配列での比較を考慮すると、B ツリーの時間複雑度 <= 赤黒ツリーの時間複雑度となります。(ブロック サイズと同じサイズの単一レコードの場合は同じ)
それらはすべて同じ漸近的な動作をするため、パフォーマンスは、使用しているツリーの種類よりも実装に依存します。B ツリーの各ノードが正確にキャッシュ ラインに収まり、ある種のバイナリ ツリーを使用して各ノード内を検索する、ツリー構造のいくつかの組み合わせが実際には最速のアプローチである可能性があります。ノードのメモリを自分で管理すると、キャッシュの局所性をさらに高めることもできますが、非常に高くつきます。
個人的には、私が使用している言語の標準ライブラリにあるものは何でも使用するだけです。これは、非常に小さなパフォーマンスの向上 (もしあれば) に対して多くの作業が必要になるためです。
理論的には... RB ツリーは、2-3-4 ツリーの動作をシミュレートするため、実際には B ツリーに非常に似ています。AA ツリーは同様の構造で、代わりに 2 ～ 3 本のツリーをシミュレートします。
.svg){kind=link}