Btreeをディスクファイルに保存して読み取る

Question

ディスクファイルにBtree（バイナリファイルではないこと）を保存します。 を読み込み、それをメモリに読み込みます。 バイナリBツリーに対しては、レベルオーバトラバーサルが適しています。 ですが、バイナリ形式ではない場合 私はリーフノードからメモリ内のルートノードにBtreeを構築します。 私は、ディスクファイルにいくつかの構造を定義し、ツリーノードを出力する必要があると考えています。 ファイル内のノードを識別するために余分なタグを使用していますか？ ここでのトラバース方法は重要な問題です。 ノードとポインタを保存する良い方法を見つけられませんでした。 し、それを読んでください。ツリーをメモリに構築する。 良いアイデアは？ ありがとうございました。

Answer 1

あなたが本当に似た何かをしたい場合は、あなただけの各ノードでIDを割り当て、その形式でノードを保存することができます：

[ノード-id値左ノードID右ノードID]

を検索し、幅優先検索でツリーにアクセスしてください。

ツリーを再構築したい、マップID->ノードを作成し、後方ファイルを読む：あなたがレコードを読み取るときに、ノードを作成してマップに登録し、左を割り当て、右ノードはマップからノードをフェッチする。

Answer 2

ノードごとに、ノードにある同じ情報を保持し、その構造に追加フィールドを追加するデータ構造を定義します。このフィールドは、次の子のファイル内のオフセットをマークします。あなたが現在どのような種類のツリーを見ているのかわからないので、その構造のトップフィールドを実際のサイズにします。今すぐファイルを飛び越えて、あなたのツリーを再構築することができます。 私の解決策は最終的なものではないと確信していますが、それがあなたのために良い星座になることを願っています。

Answer 3

Protocol Buffersをチェックしてください。コンパクトで、バイナリで、拡張性があり、読み書きが容易で、C++、Java、Python（他言語のサードパーティの実装もあります）で利用できます。

子ノードのファイルオフセットを使用して、BTreeノードのプロトコルバッファメッセージを定義し、明示的にディスクにシリアライズすることができます。

Answer 4

通常、Bツリーのテクニックは、ノードのサイズがディスクのブロックサイズと等しいことを確認し、ディスクファイルをmmapします。どのようなプログラミング言語を使用しているのかは指定していないので、C言語のキャストと同じくらい簡単かもしれませんし、java.nio.IntBufferをラップするためのフライウェイトオブジェクトの作成などもっと複雑なものもあります。いずれにしても、Bツリーの利点の多くは、一度にすべてをロードする必要はなく、かなり効率的にジャンプできます。