6

複雑なデータ構造 (ツリーなど) をディスクに保存したいとします。データ構造のノードを接続する内部ポインターはポインターですが、これらのポインターをディスクに書き込むことはできません。データ構造を読み戻すと、メモリの場所が変更されるためです。

では、ポインターをディスクに保存する正しい方法は何でしょうか? 答えは（ファイル、オフセット）と同じくらい簡単ですか、それとも何か不足していますか？ポインターがどのように (ファイル、オフセット) ペアに変換され、また元に戻されるかは直感的にわかりますが、注意すべき微妙な点はありますか?

編集：私は、データベースが内部でこれを行う方法に特に興味があることを言及する必要があります。XMLベースの回答には感謝していますが、私はおそらく質問を必要以上に一般的にしました.

4

5 に答える 5

7

(ファイル、オフセット) ペアに関するあなたの直感は正しいです。

ディスクにデータを保存する際に注意すべき重要な点は、ディスクが遅いということです。そのため、「検索可能な」データをディスクに格納するように設計された特別なデータ構造があります。(ファイル、オフセット) ポインターを使用してディスクに格納された二分探索木のノードにアクセスすると、メモリ内のノードにアクセスするよりも桁違いに遅くなります。

アクセス速度が重要な場合は、一緒にアクセスされることが予想されるものを、ディスク上でより近くに格納する必要があります。これに使用される 2 つのデータ構造はB-treeとB+ treeです。これらを調べて、それらの使用方法を見つけてください。データベースなどのいくつかのアプリケーションでは、メモリにキャッシュするために複雑なキャッシュ アルゴリズムが使用されているため、アプリは何度もディスクに移動してデータを取得する必要がありません。

アクセス速度が重要でない場合は、Aiden と Darren が提案する XML 形式でディスク上のデータを単純に「シリアル化」するだけで十分です。

編集：データベースがディスクにデータを保存する方法についてさらに詳細が必要な場合は、データベース理論についてさらに学ぶ必要があります。データベースに関する優れた本を読んで、ディスク フォーマットを駆動する要件を理解することをお勧めします。ここでは主にリレーショナル データベースについて言及していますが、他にもさまざまな 種類のデータベースがあり、要件がまったく異なるため、ディスク フォーマットも異なります。ただし、リレーショナル データベースは最も一般的に使用されているため、リレーショナル データベースから始めることをお勧めします。

要するに、リレーショナル データベースのディスク フォーマットに影響を与えるいくつかの事柄は次のとおりです。

  1. ディスクの読み取り/書き込みパフォーマンス
  2. データベースの復旧(破損の場合)
  3. エンティティ間の関係
  4. ガベージ コレクション
  5. トランザクション サポート
  6. プライマリ インデックス

クエリの最適化は、クエリを満たすためにディスク アクセスを最適化するためのデータベース理論の重要な分野です。うまくいけば、これで正しい方向に進むことができます。

于 2010-01-10T18:13:07.383 に答える
1

バイナリまたはテキストは最初の質問です

歴史的に、アプリケーションは構造化データに複雑なバイナリ形式を使用していましたが、現在の傾向はテキストベースの表現を定義することです。これにより、開発者とユーザーにとってより使いやすいファイルが生成されます。

XML は、構造化されたデータを保持および交換するための移植可能な方法として作成されました。

私だったら、XML に似ているが扱いにくい YAML を使用します。

ファイルが非常に大きくなる可能性がある場合は、OpenOffice と同じようにして、それらをテキストベースのマークアップとして保持し、圧縮 (OO の zip だと思います) アーカイブに直接書き込むことができます。

ほとんどの言語には、既にシリアライゼーション ライブラリがあります。C用のBoostライブラリがいくつかあると確信しています。通常、異なる表現を使用する複数のシリアル化インターフェースがあります。

ライブラリ、XML、または YAML を使用する場合、リンクはツリー構造の表現で暗黙的になります。データがより一般的なグラフを持っている場合、テキストを使用するかバイナリを使用するかにかかわらず、リンクを正規化する必要がある場合があります。これはあなたが言及したポインタの問題です。これを解決する 1 つの方法は、ファイルの読み取りまたは書き込み時に使用される一時マップを保持することです。つまり、すべてのリンク ターゲットに、たとえば A1、A2、A3 などの名前を付けて、リンク先ではタグとして、ソースではリンク名 (href= と考えてください) として使用します。

私はファイル オフセットをポインターとして使用しません。あまりにも壊れやすいように思われるため、XML や YAML など、既に存在するものを使用することは理にかなっています。

于 2010-01-10T18:12:45.333 に答える
1

とにかく好き。各ノードのファイルシステムの最上位にある他のファイルへの参照として保存するか、ブロック参照を使用するファイルシステムドライバーを作成できます。

提供:

  1. ノードには、持続する場所への参照が含まれています
  2. ノードを書き込むときに、書き込む場所を知ることができます

好きなようにできます。ファイルシステムは、ディスクベースの i ノード システムを使用するツリーです。

常にヘッダー付きの単一のファイルを使用し、unsigned int または int にマップされる値として格納されたバイト オフセットを使用できます。いくつかのノードの開始を示すためにファイル内に...次に、各ノードの最後に記録の終わりがあります。

他の場所または単一のファイルとXPath/XPointersへの参照を含む XML ファイルを使用することもできます。

<Node id="someNode">
    <value>...</value>
    <children>
        <child xpath="/node[id=1]" />
        <child xpath="/node[id=29]" />

ただし、これは、値が単なるバイナリ BLOB の場合、値を文字にシリアル化することを意味します (eww)。値は、次のようなファイルに書き込まれたばかりのバイナリ チャンクのパスである可能性があります。

<value>/path/to/mappable.bin</value>

XML カプセル化から C で記述されたファイルシステムまで、ツリー実装の全範囲について調べてください。

この XML ソリューションは肥大化する可能性がありますが、速度が必要ない場合は十分に単純です。高レベルのアプローチのほんの一例です。ツリー ストレージは古くからの問題であり、あらゆるレベルで解決策があります。

木は木です。

于 2010-01-10T18:00:49.897 に答える
1

まさに、ポインタの値を保存しても意味がありません。

ツリー構造でデータを保持するテキスト形式またはバイナリ形式を作成する必要があります。ツリー データ構造をリレーショナル データベースに格納するもう 1 つの例であるNested Set Model
について読むことをお勧めします。

たとえば、データは次のように保存されます。

[meta-data][data]



[meta-data] = [ length ][ list-of-Nested-Set-Model-Locations ]
    [ list-of-data-records ] = [ lft-#1 ][ rgt-#1 ][ lft-#2 ][ rgt-#2 ] ...
[data] = [length][ payload / data-itself ]

これは単なる例であり、JSON (推奨) または XML を使用する方が適切で簡単な場合があります。

于 2010-01-10T18:20:11.677 に答える
0

インメモリ ツリーをシリアル化することは可能でしょうか? これは、ネットワーク経由でオブジェクトを送信する際の一般的な Java の問題のように思えます。オブジェクトには他のものへの参照がありますが、それらのポインターアドレスは、プログラムのアドレス空間から出ると変更されます。ツリーを XML または JSON 形式にシリアライズできますか?

于 2010-01-10T18:06:50.953 に答える