1

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

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

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

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

4

1 に答える 1

1

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

高速アクセスのために、ソートされたインデックスをメモリに保持します。インデックスには、リストIDとディスク上の場所が含まれます。範囲クエリに関心がある場合は、Bツリーアプローチを使用します。それ以外の場合は、ハッシュマップを使用してこれらのインデックスを格納できます。

リストを検索している場合のさらなる改善は、それらをソートしたままにすることです...または少なくとも半ソートして、同じチャンクに類似したリストをグループ化できるようにします。これにより、各チャンクの境界(値がb / w 1-9、10-25などのノード)をメモリにキャッシュすることがよくある場合、リストの検索が高速化されます。マージソートは、おそらくリストに最適なソートです。またはさらに良いことに、リストにノードを挿入するときは、リストが常にソートされるように正しい場所に挿入します。次に、二分探索で調べます。データが適切にインデックス化されておらず、並べ替えられていない場合、クエリのために複数回ディスクにアクセスします。この場合、使用する検索では、ディスク時間が原因で線形時間が得られます。

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

これらのリストのサイズ(およびそれらにあるcチャンクの数)に応じて、いくつかのRAIDを使用して、いくつかの並列読み取り/書き込みを取得できます。

于 2011-12-14T15:15:35.663 に答える