I need to save big data structure (Tree with specific nodes) into file efficiently. Data is always changing, so I need to rewrite whole data structure very often, so simple serialization is not good option.
Which algorithms can be used to efficient saving of big data structures?
I used simple serialization, but i want to try algorihms which save only delta of my structure and then union those changes. In which direction should I move?
2
I tend to agree with Doc Brown’s answer: you’ll better use a database. That might be sqlite or a real database server: mongodb or postgresql, etc…. You could perhaps use an indexed file like GDBM (instead of a database) in some limited circumstances. If the data is small (which apparently it is not) you might consider persisting all of it in some textual formats like JSON (which you could also use inside database tables).
You should also define if your data structure is a real tree (without shared sub-nodes) or if it is a graph. You may have to manage the set of already dumped items, and handle shared data. Shared pointers and smart pointers may matter a lot.
You could store, in every significant object in memory, some database identifier (or id number), and perhaps other meta-information related to saving the data (saving timestamp, change time, etc…)
BTW, copying Garbage Collection algorithms may be relevant (since persisting to some database is quite similar to a copying GC). Read also the GC handbook.
You might be interested by persistence and application checkpointing.
You should design the persistence machinery quite early if possible.
Short answer: consider to use a database.
Databases allow you easily to save only the changed part of a whole bunch of data very quickly, whilst you don’t have to care for the unchanged parts.
And here is a former SO post dealing with the topic of storing tree structures in databases.
0