ディスク上にn個のオブジェクトを含む大規模なコレクションがあり、それぞれに可変サイズの文字列があるとします。プレーンな文字列比較を使用してこれらのオブジェクトのインデックスを作成する効率的な方法の一般的な方法は何ですか。サイズとI/Oのために、文字列全体をインデックスに格納することは長期的には禁止されますが、ディスクは待ち時間が長いため、参照のみを格納することもお勧めできません。
私は試行錯誤でBツリーのような設計を使用することを考えていましたが、このアプローチを使用したデータベース実装を見つけることができません。実際、主要なデータベースが文字列のインデックスをどのように実装しているかを見つけるのは困難です（SQLレベルの情報の膨大な結果で失われる可能性があります）。
TIA！
編集：タイトルを「大きな文字列を持つ保存されたオブジェクトの効率的な外部ソーティングと検索」から「文字列の外部インデックスの効率的な保存」に変更しました。
ここでは、「プレフィックス B ツリー」または「単純なプレフィックス B ツリー」がおそらく役立つでしょう。
「単純なプレフィックス B ツリー」は少し単純で、2 つの項目を区切る最短のプレフィックスを格納するだけで、それらのプレフィックス内の冗長性を排除しようとはしません (たとえば、「天文学」と「方位角」の場合、「as」と「方位角」のみを格納します)。 'az' を使用しますが、'a' が重複しないように注意してください)。
「プレフィックス B ツリー」は、あなたが説明したものに近いものです。トライのようなものですが、主にディスクに格納されたときに優れた特性を与える B ツリー構造になっています。それにもかかわらず、インデックスを形成するプレフィックス内の冗長性 (ほとんど) を削除することを目的としています。
もう 1 つの質問があります。本当にレコードを順番にトラバースする必要があるのでしょうか。それとも、指定されたレコードをすばやく検索するだけでよいのでしょうか。後者で十分な場合は、代わりに拡張可能なハッシュを使用できる場合があります。拡張可能ハッシュは (さまざまな形で) 数十年前から存在しており、今でも十分に機能しています。一般的な考え方は非常に単純です。文字列をハッシュして固定長のキーを作成し、それらの固定長の疑似キーのある種のツリーを作成します。（ほぼ）すべてのハッシュと同様に、衝突に対処する準備ができている必要があります。他のハッシュ テーブルと同様に、ハッシュと衝突の解決の詳細はさまざまです (ただし、拡張可能なハッシュでは、インメモリ ハッシュほどではない可能性があります)。
実際の使用に関しては、主要な DBMS および DBMS に似たシステムが上記のすべてを使用しています。B ツリー バリアントは、おそらく汎用 DBMS 市場 (Oracle や MS SQL Server など) で最も一般的です。拡張可能なハッシングは、より専門的な製品 (Lotus Domino Server など) のかなりの数で使用されています。
やりたいことを明確にすることから始めましょう。それらを並べ替えますか、それとも索引付けしますか? 並べ替えには、ディスク上のアイテムの少なくとも一部を移動する必要がある可能性がありますが、インデックスを作成すると、アイテムがそのままの場所に残る可能性があります。
それらを本当にソートしたい場合は、Knuth の「The Art of Computer Programming」第 3 巻で、ソートと検索について、必要に応じて詳細に説明しています。
オブジェクトで何をしていますか？
多数の同時要求を処理するために低レイテンシーを必要とする大規模なシステムを実行している場合は、オブジェクトをデータベースに格納し、ソートとインデックス作成を処理するようにします。これは、B ツリーをゼロから実装し、バグがある可能性があるよりもはるかに簡単です。
DBMS には、作業を容易にするキャッシングやその他のさまざまな機能もあります。