C++: Which Data Type in STXXL is suitable to create External Memory Binary Search Tree?

Question

I want to create an External Memory Binary Search Tree Data Structure whose data sits in the external memory using stxxl as a library.

For this purpose, which Data Type in STXXL is suitable to use as nodes in the Tree. If we use stxxl:Vector as the Nodes of the tree, how do we hold the pointers to them.

I have read in STXXL:Vector documentation that its obviously not possible to use Pointers which is very logical to understand.

Warning : Do not store references to the elements of an external vector. Such references might be invalidated during any following access to elements of the vector .

Then the Question is what is an alternative to hold a Binary Search Tree Data Structure using 'stxxl' data types ?

Answer 1

Store iterators pointing to elements instead of pointers/refs to elements. Pointers/refs will be invalidated because of paging to/from the disk, but the iterators will not be invalidated.

Ex:

// Safe to store this, not safe to store &nodes[node_index].
stxxl::vector<Node>::iterator node_it = nodes.begin() + node_index;

... and const_iterator for read-only purpose.

node_it will not be invalidated unless the element is removed. Unlike the STL, it doesn't even get invalidated if you do things like push_back. Dereferencing it will write/read pages to/from disk (only reading for const_iterator), and so you can treat it like a pointer that doesn't get invalidated.

Answer 2

You can keep directly the stxxl::vector in the node structure. However, while using and traversing nodes you need to return the reference of the vector not the vector itself. If you return the vector directly, you will deep-copy it which is not feasible. Returning references from an existing node is a safe way to use:

const stxxl::vector<int> &Node::getVectorFromNode() const
{
   return _VectorNodeMember;
}