1

私はデータベース設計の専門家ではないので、CS用語で翻訳する前に、必要なことをわかりやすく説明します。大きなサブセット（たとえば、約100Moのdouble）をすばやく反復する正しい方法を見つけようとしています。 ）データの、潜在的に非常に大きなデータセット（たとえばいくつかのGo）。基本的に4つの整数（キー）と値、単純な構造体（1ダブル1ショート）で構成されるオブジェクトがあります。私のキーは少数の値（数百）しか取ることができないので、データをツリーとして保存するのが理にかなっていると思いました（キーごとに1つの深さ、値は葉であり、少なくとも私の素朴なビューではXMLのXPathに似ています） 。

キー値/それらのキー値の関数に基づいて、リーフのサブセットを反復処理できるようにしたいと思います。フィルタリングするキーの組み合わせは異なります。これは横断検索と呼ばれていると思いますか？
したがって、同じキーをn回比較しないようにするには、理想的には、キーの順列ごとにデータ構造にインデックスを付ける必要があります（12の可能性：！4 /！2）。これboost::multi_index が目的のようですが、smthを見落とさない限り、これを行う方法は、実際にこれらの12のツリー構造を構築し、値ノードへのポインターをリーフとして格納することです。キーに比べて値のサイズが小さいことを考えると、これはスペース効率が非常に悪いと思います。

私が使用すべき設計/データ構造に関する提案、またはこれらのトピックに関する簡潔な教材へのポインタをいただければ幸いです。

4

3 に答える 3

4

Boost.MultiIndex を使用すると、4 つのキーの特定のサブセットを構成するすべてのクエリをカバーするために、12 個ものインデックスを必要としません (ところで、4 つの要素の順列の数は 12 ではなく 4!=24 です)。複合キーの、そして少し工夫すれば、6 つのインデックスで十分です。

偶然にも、私は数年前に自分のブログで、特定のシナリオにほぼ正確に一致する方法でこれを行う方法を示す例を提供しました。

Boost.MultiIndex を使用した複数属性のクエリ

必要に応じて少し変更するだけで使用できるソース コードが提供されています。この構成の理論的正当性は、同じブログの一連の記事でも提供されています。

この背後にある計算は簡単ではないため、無視しても問題ありません。ただし、理解するのに支援が必要な場合は、遠慮なくブログ記事にコメントしてください。

このコンテナーはどのくらいのメモリを使用しますか? 典型的な 32 ビット コンピューターでは、オブジェクトのサイズは 4*sizeof(int)+sizeof(double)+sizeof(short)+padding で、通常は 32 バイトになります (Win32 の Visual Studio で確認)。この Boost.MultiIndex には、インデックスごとに 3 ワード (12 バイト) のオーバーヘッドが追加されるため、コンテナーの各要素に対して、

32+6*12 = 104 バイト + パディング。

繰り返しますが、Win32 の Visual Studio で確認したところ、取得されたサイズは要素あたり 128 バイトでした。10 億 (10^9) の要素がある場合、32 ビットでは十分ではありません。64 ビット OS に移行するとオブジェクトのサイズが 2 倍になる可能性が高いため、必要なメモリは 256 GB になり、これは非常に強力です。野獣（これほど巨大なものを使用しているかどうかはわかりません。）

于 2011-07-22T20:01:38.223 に答える
1

B ツリー インデックスとビットマップ インデックスは、使用される主要なインデックスの 2 つですが、それだけではありません。それらを探索する必要があります。始めるための何か。

B-Tree を使用する場合と Bitmap を使用する場合を評価する記事

于 2011-07-22T15:50:11.947 に答える
0

正直なところ、それにアクセスするアルゴリズムに依存します。この構造が常駐する必要があり、メモリを消費する余裕がある場合は、それを実行してください。multi_indexは問題ありませんが、ヘッダーにある場合はコンパイル時間が破壊されます。

1回のトラバーサルが必要な場合は、構造を構築するのは無駄になります。next_permutationのようなものから始めるのが良いかもしれません。

于 2011-07-22T15:56:20.470 に答える