47

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

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

  2. データはシステムのメモリに比べて比較的少ないため、速度のためにメモリ自体に保存および操作できます。

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

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

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

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

ケース 3 については、これには疑問があります。ページ ファイルはディスク上にあり、ネイティブ OS I/O を使用してファイルを操作します。したがって、B ツリーの方が適切なオプションでしょうか、それともレッド ブラック ツリーでしょうか?

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

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

更新 1:: stackoverflow でこの投稿を読んでいました。本当に良い洞察を得たので、私がケースで行ったタイプの比較は間違っているかもしれないと感じています. 最も投票数の多い回答にリンクが投稿されましたhttp://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

4

3 に答える 3

25

赤/黒ツリーは、B ツリーの一種である 2-3-4 ツリーとほぼ同等です。B ツリー ノード値の二分探索を行う場合、最悪の場合のパフォーマンスは同じです。

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

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

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

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

于 2011-06-19T15:40:11.257 に答える
-3

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

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

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

于 2016-03-09T18:28:20.967 に答える