非常に大量のレコード (400K レコード以上) のソフトウェア表現を探しています
各レコードには 2 つのキーがあります。1 つは下限用、もう 1 つは上限用です。これらの数値は範囲を表します。また、各レコードにはいくつかの情報があり、それを I と呼びましょう。言い換えれば、各レコードは共通のアイテム インデックスを集約し、それらに関するいくつかの共通の説明を持っています。
私のソフトウェアにはアイテム番号が与えられており、その情報を取得する必要があります。
AVL、B-Tress、またはフィボナッチについて考えました。しかし、その膨大な量のレコードには、どちらが最適であると確信しています。私は間違いなくAVL /バランスのとれたAVLを小さなデータベースに使用します.
どのデータベースでも、必要なことをうまく実行できます。
インデックスを検索している場合、2から4レコードに移行するときのルックアップ速度の向上は、200万から400万レコードに移行するときと同じです...ツリーのもう1つのレベル...それは指数関数的な関係です。
データ構造の観点から、インターバル ツリーを検索します。
ウィキペディアの記事はかなり良いです。できることは、AVL や Red-Black-Trees のような (バランスの取れた) 二分探索木を拡張することです。二分探索木に基づく区間木には、Cormen らによる古典的な DS の本に独自のセクションがあります。.
優れたデータ構造は、大量のデータにうまく対応します。主要なディレクトリ操作の複雑さは O(k + log n) です。ここで、n はツリー内の間隔の数、k は範囲内の重複する間隔の数です。これは通常かなり良いです。多くまたはほとんどの間隔が他のすべての間隔と重なっている場合を除いて、間隔アイテムの数に応じてゆっくりと増加します。
データをメイン メモリに保持できない場合は、B ツリーが適しています。