数十億の整数を格納するデータ構造

Question

メモリ（RAM）に100万/数十億のレコード（名前と整数を含むレコードを想定）を格納するのに最適なデータ構造は何ですか？ 最小検索時間（第1優先）とメモリ効率（第2優先）の点でベスト？それはパトリシアの木ですか？これ以外の何か他の？

検索キーは整数です（たとえば、32ビットのランダムな整数）。また、すべてのレコードはRAMに格納されています（十分なRAMがあると仮定して）。 C、プラットフォームのLinuxでは

..

基本的に私のサーバープログラムは、ユーザーに32ビットのランダムなキーを割り当て、私は効率的な方法でレコードを削除/検索できるように対応するユーザレコードを保存したいです。データ構造には十分なデータが格納されていると見なすことができます。

Answer 1

に依存します。

名前または整数で検索しますか？

名前はすべて同じサイズですか？

すべての整数は32ビットですか、それとも大きな数字ですか？

すべてがメモリに収まっていますか？そうでなければ、おそらくディスクI/Oとメモリ（またはディスク使用量）によって制限されていることになります。

インデックス（名前または整数）に共通のプレフィックスが付いているのか、それとも一様に分散していますか？共通接頭辞を持つ場合にのみ、patriciaツリーが便利です。

インデックスを順番に検索していますか（ギャングルックアップ）、ランダムに表示されますか？すべてが均一で、ランダムで、共通のプレフィックスがない場合、ハッシュはすでに得られているほど良好です（これは悪いです）。

インデックスがギャングルックアップを使用する整数の場合は、基数ツリーを調べることができます。

Answer 2

私の推測ではあるB-Tree（私は...間違っている可能性）：

B-木は実質的な利点を持っている ノードアクセス時間がはるかにノード内のアクセスに 回を超えて代替の実装を超えます。ほとんどのノードがハードドライブなどの二次ストレージ にある場合、これは通常 です。 各内部ノード内の子 ノードの数を最大にすると、 のツリーの高さが減少し、 の分散が少なくなり、 効率が向上します。通常、この の値は、各ノードがフルディスクブロックの上に を取り込むか、または二次記憶装置内の類似の サイズになるように設定されます。 2-Bツリーはメインの メモリで有用であり、確かに の方が簡単ですが、ノードサイズがディスクブロックのサイズに合わせて調整されている場合、 の結果は257-513 B-ツリー （サイズはより大きい の累乗に関連しています）。

Answer 3

ハッシュではなく、少なくとも基数を使って開始することができます。

特定の問題については、btree、ハッシュテーブル、またはpatricia trieよりもはるかに優れています。問題を少し詳しく説明し、何が有効かを提案することができます。

Answer 4

整数キーで検索する場合は、単純なハッシュテーブルが最速です。整数が連続している（またはほとんど連続していて）固有である場合、（レコードへのポインタの）単純な配列はさらに高速です。

ハッシュテーブルを使用している場合は、予想される最終サイズにハッシュテーブルをあらかじめ割り当てて、再ハッシュしないようにします。