コア外に格納された疎なデータ構造の値を参照する何百万ものキーを含む静的辞書があります。キーの数は、値の数のごく一部、たとえば 10% です。鍵のサイズは通常 64 ビットです。キーは線形に並べられており、クエリは多くの場合、この順序で互いに近いキーで構成されます。データ圧縮は要因の 1 つですが、データ サイズに最も大きく影響すると予想されるのは、キーではなく値です。キー圧縮は役に立ちますが、重要ではありません。ユーザーがデータを操作しているため、クエリ時間は可能な限り一定で、高速である必要があります。
これらの条件を考えると、辞書にクエリを実行して特定のキーが含まれているかどうかを判断する効果的な方法を知りたいと思います。クエリの速度は最優先事項であり、構築時間はそれほど重要ではありません。
現在、キャッシュに依存しない b+ ツリーと、外部ストレージに関連付けられた順序を保持する最小限の完全なハッシュを検討しています。
現時点では、CHD またはその他の形式のハッシュが候補のようです。キーはほぼ線形の順序でクエリされるため、順序を保持するハッシュはキャッシュ ミスを回避するように見えますが、CHD がキーの順序を保持できるかどうかを判断できるほどの知識はありません。一定時間のクエリも望ましいです。検索は O(1) ですが、キー空間に対するクエリ回数の上限も不明です。
木はあまり魅力的ではないようです。キャッシュに依存しないアプローチやキャッシュ固有のアプローチもいくつかありますが、その努力の多くは、一定時間のメンバーシップ クエリではなく、動的辞書での範囲クエリを対象としていると思います。一般に、プロセッサとメモリは分岐を好みません。
これらの線に沿って多くの質問がありましたが、このケースは (うまくいけば) 他の人に役立つかもしれない方法で問題を制限します.
フィードバックをいただければ幸いです。