背景：約10億のキーと値のペアを挿入します。（一意の64ビット整数）キーの（32ビット整数）値を同時に検索できるメモリ内インデックスが必要です。更新、削除、トラバースはありません。キーは一般的に時間とともに徐々に増加しています。
これを処理するのに最も適切なインデックス構造は何ですか？
私が考えることができる要件は次のとおりです。
この問題に対して、単純な並べ替えられたベクトルよりも効率的なデータ構造はおそらくありません。(実際には、アラインメントの問題があり、アクセスの特性によっては、キーと値を別々のベクトルに配置することをお勧めします。) しかし、実際には多くの問題があり、特にデータの大きさがわからない場合はそうです。これを知っている場合、またはあまりにも多くのスペースを事前に割り当てて、このスペースに収まりきらないほど多くのデータを取得した場合に死ぬ準備ができている場合は、それでも問題ありませんが、ベクトルをソートし続けることについて心配する必要があります.
おそらくより良いアプローチは、BST の葉がデータ (つまりベクトル) の「塊」を指すインデックス範囲のバイナリ検索ツリーを保持することです。(これは本質的にB+ ツリーです。) クランプはかなり大きくなる可能性があります。数分で受信すると予想されるデータの量、または数千のエントリのようなものだと思います。すべて同じサイズである必要はありません。(通常、B+ ツリーのファンアウトはそれよりも小さいですが、データは「ほとんどソートされている」ため、より大きなファンアウトを使用できるはずです。大きくしすぎないでください。唯一のポイントは、オーバーヘッドを減らし、場合によってはキャッシュすることです-スラッシング。)
データは「ほとんどソートされている」ため、通常の順序付けされたマップ (そのようなものがあると仮定)、または挿入ソートを使用してベクトルに保持して、しばらくの間データを蓄積できます。このバッファーが十分に大きくなったら、メインのデータ構造に単一のクランプとして追加し、最後のクランプを再分割してオーバーラップに対処できます。
順不同のキーをめったに取得しないことが合理的に確信している場合は、順不同のデータ要素の 2 番目の従来の BST を保持することになります。新しいクランプと前の最後のクランプを再分割しても対応できない要素は、この BST に追加できます。ルックアップを行うには、メイン構造とアウトオブオーダー構造の間で並行ルックアップを行います。
偏執的であるか、順序付けされていないデータの量について十分に確信が持てない場合は、標準の B+ ツリー挿入アルゴリズムを使用してください。スペースのオーバーヘッドを避けたい場合)、必要に応じてクランプを分割します。