saving Btrees to a disk file and read it
I want to save a Btree(not sure a binary one) in a disk file. and then read it to the memory. some Level-order traversal may be a good way for a binary Btree. but if it is not a binary one. I build up the Btree from the leafnode to the rootnode in memory. I believe that I have to define some structures in the disk file and output the tree nodes. using some extra tag to identify a node in the file? how to traversal may be the key problem here. I coudn't figure out a good way to save the nodes and the pointers. and then read it. rconstruct the tree in memory. any good ideas?. thanks a lot.
Answer
If you really want to do something similar, you can just assign at each node an id and save the nodes in that format:
[node-id value left-node-id right-node-id]
and then visit the tree with a breadth-first search.
When you want to reconstruct the tree, create a map id->node and then read backward the file: so, when you read a record, create the node, register it to the map and assign the left and right node fetching the nodes from the map.