増え続けるリストを含む動的オブジェクトをディスクに保存する

Question

さて、私はこれまでメインメモリで多くの異なるオブジェクトを持ち、各オブジェクトがシステム内の他のオブジェクトのリストを格納するシステムを開発してきました。これを永続ストレージに移動したいと思います。システム用のカスタムデータベースを作成していることが重要なので、DBMSを使用するという明白な答えを探していません。

これで、オブジェクトごとにIDを割り当てます。 IDをテーブルで検索して、そのオブジェクトのデータの場所のブロックとオフセットを見つけることができます。これで、各オブジェクトには、システム内の他のオブジェクトを指すリスト/セットがあります。したがって、明らかにストレージ内には、他のオブジェクトを見つけるために使用できる8バイト（IDにlongを使用）IDのリストがあります。ここでの私の質問は、リストは時間の経過とともに成長するため、成長する余地が必要であることを知っているということです。リストを保存して、オブジェクトが大きくなったときにオブジェクトを移動する必要がないようにするためのこれまでの私の最善の考えは、各リストにオブジェクトと同じIDを割り当てて、オブジェクトと同じようにテーブルで検索できるようにすることです。それらはディスク上にあります。

これで、各リスト部分に10個のオブジェクトを格納するためのスペースが割り当てられ、さらにオブジェクトが含まれている場合は、最後に次のリスト部分のIDになります。これは、それを実行し、絶えず成長するオブジェクトを処理するための適切な方法のように思えますが、より良いアプローチがあるかどうか疑問に思っています。インデックスをメモリに保存するので（スペースが許す限り）、オブジェクトIDが与えられると、ルックアップはメモリ内にあり、ディスクからデータとリストIDを取得するのに1 I / Oかかります。次に、トラバースするリストごとに、ブロックがキャッシュされている場合、リスト内の10個以下のオブジェクトごとに別のルックアップとI / Oが必要になります。

I / Oの数はひどいものではなく、リスト部分の局所性を維持して不要なI / Oを排除しようとしますが、これを行うためのより良い方法はありますか？リストをオブジェクトとは別に保存しようとするのは正しいですか、それともオブジェクトのデータと一緒にリストを保存する方法を検討する必要がありますか。それを行うことについての私の心配は、あるリストが大きくなるにつれて、それは別のリストにぶつかり、次に断片化する必要があり、これはより複雑になる可能性があるということです。ご提案をいただければ幸いです。

Answer 1

これらの拡張可能なリストを持つというあなたの考えは良いです。私はあなたの説明がいくつかの詳細が欠けていると思います（すなわち、注文されたリストまたはそうではない、オブジェクトからのリストを別々に分けることで、これらのリストの図が役に立ちます）。

私は高速アクセスのためにソートされたインデックスをメモリに保持します。インデックスにはリストID、およびディスク上の場所にあります。範囲クエリに興味がある場合は、Bツリーアプローチで行く場合、そうでなければあなたはこれらのインデックスを保存するためにHashMapを使うことができます。

それ以上の改善は、リストを検索している場合は、それらをソートしておくことです。または少なくともセミソートされ、同じチャンク内の類似リストをグループ化できるようにします。これにより、メモリへのキャッシュが各チャンクの境界（値B / W 1-9,10-25などのノードなど）を参照している場合、リスト内での検索をスピードアップします。マージソートはおそらくリストに最適なソートです。リスト内のノードを正しい場所に挿入すると、リストが常にソートされている場合はさらに優れています。その後、バイナリ検索で検索します。データが正しく索引付けされていない場合は、クエリに対して複数回ディスクになり、この場合、使用した検索はディスクの時間のためにリニアタイムを与えます。

最も検索されたノード/リストのデータノードをキャッシュすることもできます。

これらのリストのサイズ（およびそれらのためにいくつかのチャンク）に応じて、いくつかのRAIDを使用することができるので、並列読み書き/書き込みを取得できます。