赤い黒ツリー対Bツリー

Question

私は、メガバイトからテラバイトの範囲のデータに対して高速検索、挿入、および削除操作を実現するプロジェクトを持っています。私は後半のデータ構造を勉強して分析していました。

1. をデータがメモリが1回で（10〜15件のテラバイトのサンプル範囲）を扱うことができるものよりもはるかにである：具体的なので、私は3例を紹介し、その上で質問をお願いしたいと思います。この場合、データ構造をディスクに格納します。

2. データはシステムのメモリに比べて相対的に少なく、メモリ自体に格納され、速度のために動作することができます。

3. データは空きメモリを超えており、ページングファイル内の可能な連続するデータチャンクのサイズよりも小さいとみなされます。私はディスク上のファイルにデータ構造を格納し、ファイルのメモリマッピングを行います。私が描かれている

結論は次のとおりケース1について

それはケース2のディスク回転

によって生産遅れを節約するように、私は、より速いアクセスのためにBツリーを使用する必要があり、Iデータがメモリ上にあるので高速のアクセスのためにRed Black Treeを使用する必要があります。私がBツリーを使用する場合、私がしなければならないものよりも悪い場合にスキャンする必要がある要素の数は少なくなるでしょう。

ケース3の場合、私はこのファイルがディスク上のネイティブOS I/Oファイルを操作するために、Bツリーはより良いオプションかレッドブラックツリーであるべきですか？

上記の3つの結論が正しいかどうか、どこが間違っているのか、そして3つの別々のケースでパフォーマンスをどのように改善できるかを知りたいと思います。

私は最初から設計した赤い黒のツリーとBのツリーを持つC++言語を使用しています。私はファイルマッピングのためのBoostライブラリを使用しています。

更新1 :: thisの記事を読んでいました。本当の良い洞察力を得ました。これは、私がケースで行った比較のタイプが間違っているかもしれないと感じさせるものです。 http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

Answer 1

赤色/黒色のツリーは、単なるB型ツリーの1つである2-3-4ツリーと多かれ少なかれ同等です。最悪の場合のパフォーマンスは、Bツリーのノード値をバイナリ検索すると同じです。

Bツリーの明らかな欠点は無駄なスペースですが、使用されている言語/メモリアロケータによっては、2-3-4ツリーは赤黒のツリーよりも少ないスペースしか使用しないことがあります。たとえば、32ビットのJavaでは、オブジェクトあたり約8バイトのオーバーヘッドがあります。 （また、アロケータに大きく依存し、IIRCのphkmallocは、2の累乗のサイズに小型の配分を切り上げ。）

をあなたの例に答えるために、

1. ディスクの待ち時間はおおよそ均等に分割されたシーク時間ディスクが回転するのを待つ。
2. Bツリーは、正しく実行している場合は赤黒のツリーよりも優れているはずです（特に、ノードがキャッシュラインに収まる場合はBツリーが速くなるはずです）。）
3. ページファイル内で連続している必要はありません。プロセスの仮想アドレス空間では連続している必要があります。正常なOSでは、データがほとんどメモリに収まるほど小さく、memcpyのオーバーヘッドが重要でない限り、ケース1とほとんど同じです。

簡潔にするために、私はBツリーに行き、さまざまなノードサイズでいくつかのベンチマークを実行します。色の付いた各ノードと

1）A「赤黒木は」「自己均衡」「バイナリ検索ツリー」で、 （：これらの違いを理解することが

Answer 2

、2ポイント下回っ読みます「赤黒」ツリーはすべて「バイナリ検索ツリー」ですが、すべての「バイナリ検索ツリー」は「赤」または「黒」のいずれでもありません） Red-Black Tree "