webdevqa.jp.net

赤黒木vs B木

メガバイトからテラバイトの範囲のデータに対して高速な検索、挿入、削除操作を実行する必要があるプロジェクトがあります。私は最近、データ構造を研究して分析してきました。具体的には、3つのケースを紹介し、それについて質問します。

  1. データは、メモリが一度に処理できるもの(10〜15テラバイトのサンプル範囲)をはるかに超えています。この場合、データ構造をディスクに保存します。

  2. データはシステムのメモリと比較して比較的少ないため、速度を上げるためにメモリ自体に格納して操作できます。

  3. データは空きメモリよりも多く、ページングファイル内の連続するデータのチャンクのサイズよりも小さいと想定しています。したがって、データ構造をディスク上のファイルに格納し、ファイルのメモリマッピングを行います。

私が導き出した結論は次のとおりです。

ケース1の場合、ディスクの回転によって生じる遅延を節約できるため、アクセスを高速化するためにBツリーを使用する必要があります。

ケース2では、データがメモリ上にあり、メモリ上にないため、アクセスを高速化するためにRed Black Treeを使用する必要があります。最悪の場合にスキャンする必要がある要素の数は、Bツリーを使用する場合に実行する必要がある要素よりも少なくなります。

ケース3の場合、私はこれに疑問があります。ページファイルはディスク上にあり、ネイティブOS I/Oを使用してファイルを操作するので、Bツリーの方が良いオプションですか、それともRed Blackツリーですか?

上記の3つの結論が正しいところと間違っているところ、および3つの個別のケースでパフォーマンスを向上させる方法を知りたいです。

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

更新1 :: Stackoverflowで this の投稿を読んでいました。いくつかの実際の良い洞察を得たので、ケースで行った比較のタイプに欠陥があるかもしれないと感じます。リンクがmost-voted-for-answer http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html に投稿されました

39
swanar

赤/黒のツリーは、Bツリーの一種である2-3-4ツリーとほぼ同じです。 Bツリーノード値のバイナリ検索を実行すれば、最悪の場合のパフォーマンスは同じです。

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

あなたのケースに答えるために、

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

簡単にするために、Bツリーを使用して、さまざまなノードサイズでいくつかのベンチマークを実行します。

15
tc.

これらの違いを理解するには、以下の2つの点をお読みください。

1)「赤黒木」は「自己均衡」「二分探索木」であり、各ノードは色(赤または黒)でマークされ、「バランス」を維持するために追加の操作が定義されています

2)すべての「赤黒木」は「二分探索木」ですが、すべての「二分探索木」は「赤黒木」ではありません

0
Muhammad Noman