implementing large trees

[Michael Schmitt]

Hello.

I'm trying to implement a large tree data structure, which does not fit 
into memory. Based on an in-memory implementation, which has two 
dictionarys, one for all nodes and one for all edges, the first idea was to 
use shelve to have disc-based dictionaries.

But for usual tree operations (depth-first traversal, breadth-first 
traversal) the shelve based tree was much slower, than the tree using two 
dictionaries and relying on swapping.

What is the "best" way to implement such a tree? Is it possible to improve 
performance without knowing how the tree is traversed? What about having a 
breadth-first and a depth-first cache, that prefetch nodes and edges after 
each access?

Thanks for any hints.

Michael