Btree（バイナリのものはわかりません）をディスクファイルに保存したいと思います。そしてそれをメモリに読み込みます。いくつかのレベル順トラバーサルは、バイナリBtreeの良い方法かもしれません。しかし、それがバイナリのものでない場合。メモリ内のリーフノードからルートノードまでBtreeを構築します。ディスクファイルにいくつかの構造を定義し、ツリーノードを出力する必要があると思います。ファイル内のノードを識別するためにいくつかの追加のタグを使用していますか？ここでは、トラバーサルの方法が重要な問題になる可能性があります。ノードとポインタを保存する良い方法がわかりません。そしてそれを読んでください。メモリ内のツリーを再構築します。何か良いアイデアはありますか？どうもありがとう。
8817 次
4 に答える
6
B-Tree の通常の手法は、ノードのサイズがディスクのブロック サイズと同じであることを確認し、ディスク ファイルを mmap することです。作業しているプログラミング言語を指定しないため、C でのキャストのように単純な場合もあれば、flyweight オブジェクトを作成して java.nio.IntBuffer をラップするなどのより複雑な場合もあります。いずれにせよ、B ツリーの利点の多くは、一度にすべてをロードする必要がなく、かなり効率的にジャンプできることです。
于 2009-05-16T13:07:47.850 に答える
5
本当に似たようなことをしたい場合は、各ノードに id を割り当てて、ノードをその形式で保存できます。
[ノード ID 値 左ノード ID 右ノード ID]
次に、幅優先検索でツリーにアクセスします。
ツリーを再構築する場合は、マップ id->node を作成し、ファイルを逆方向に読み取ります。つまり、レコードを読み取るときにノードを作成し、それをマップに登録し、そこからノードをフェッチする左右のノードを割り当てます。地図。
于 2009-05-16T09:44:06.263 に答える
0
ノードごとに、ノードが持っているのと同じ情報を保持するデータ構造を定義し、その構造に次の息子のファイル内のオフセットをマークする追加フィールドを追加します。そして、その構造の一番上のフィールドを実際のサイズにします。なぜなら、あなたが今見ているツリーの種類がわからないからです。ファイルをジャンプすると、ツリーを再構築できます。私の解決策は最終的なものではないと確信していますが、それがあなたにとって良いスターポイントになることを願っています.
于 2009-05-16T10:01:21.653 に答える
-6
Protocol Buffersを確認してください。それらはコンパクトで、バイナリで、拡張可能で、読み書きが簡単で、C++、Java、Python (および他の言語でのサードパーティの実装) で利用できます。
子ノードのファイル オフセットを使用して、BTree ノードのプロトコル バッファ メッセージを定義し、それを単純にディスクにシリアル化できます。
于 2009-05-16T12:41:09.380 に答える