ディスク上のリストを増やしながら動的オブジェクトを保存する

Question

これまで、メインメモリにはさまざまなオブジェクトがあり、各オブジェクトはシステム内の他のオブジェクトのリストを格納するシステムを開発していました。今私は永続的なストレージに移動したいと思います。私はDBMSを使用する明らかな答えを探しているわけではありません。なぜなら、私のシステム用のカスタムデータベースを作成しているからです。

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

各リスト部分には、10個のオブジェクトを格納するために割り当てられたスペースが設定され、さらに多くのオブジェクトが含まれている場合は、次のリスト部分のIDになります。これはそれを行うためのまともな方法のようであり、絶えず成長するオブジェクトに対処するためには、私はそれ以上のアプローチがあるのだろうかと思っています。私は、オブジェクトIDが与えられているので、メモリに索引を格納します（その領域が許可されている）ので、参照はメモリー内にあり、ディスクからデータとリストIDを取得するには1 I/Oがかかります。そのリストをトラバースしたい各リストに対して、リスト内の10個のオブジェクトごとに別のルックアップとI/Oを実行します。

I/Oの数はひどいわけではありません。不要なI/Oを排除するためにリスト部分の局所性を維持しようとしますが、これを行うにはより良い方法がありますか？私はオブジェクトとは別のリストを試して保存する権利がありますか、オブジェクトのデータでリストを保存する方法を検討する必要があります。私の心配は、1つのリストが成長するにつれて別のリストに入り、断片化する必要があり、これはもっと複雑になる可能性があるということです。どんな提案も感謝しており、事前に感謝しています。

Answer 1

これらの拡張可能なリストを持つというあなたの考えは良いです。あなたの説明にはいくつかの詳細が欠落していると思います。（順序付きリストかどうか、オブジェクトからリストを分離しようとするとどういう意味ですか？これらのリストの図が役に立ちます。

高速アクセスのためにソートされたインデックスをメモリに保持します。索引にはリストIDとディスク上のロケーションがあります。範囲問合せに興味があるならば、Bツリー・アプローチを使用してください。そうでなければ、ハッシュマップを使用してこれらの索引を格納できます。

リストを検索している場合は、並べ替えを維持するか、少なくとも同じセクションで類似リストをグループ化できるようにセミソートしておくとさらに改善されます。これは、あなたが頻繁にキャッシュにキャッシュするたびに、各チャンクの境界（b/w値1-9,10-25などのノード）の境界を言うならば、リストの検索を高速化します。マージソートはおそらくリストのための最良のソートです。または、リスト内のノードを挿入すると、リストが常にソートされるように、正しい位置に挿入するとさらに優れています。次に、バイナリ検索で検索します。データが適切に索引付けされておらず、ソートされていない場合は、問合せのためにディスクに複数回アクセスします。この場合、使用する検索によってディスク時間のために線形時間が得られます。

また、10％のルックアップされたノード/リストのデータノードをキャッシュすることもできます。

これらのリストのサイズ（どれくらい多くのチャンクを持っているか）によっては、いくつかのRAIDを使用できるため、いくつかの並列読み取り/書き込みが可能です。