Is it possible to write a truly generic disk-baked B+Tree implementation?

Question

I wrote a generic in-memory B+Tree implementation in C++ few times ago, and I'm thinking about making it persistent on disk (which is why B+Tree have been designed for initially). My first thought was to use mmap (I'm under Linux) to be able to manipulate the file as normal memory and just rewrite the new operator of my nodes classes so that it returns pointers in the mapped portion and create a smart pointer which can convert RAM adresses to file offset to link my nodes with others. But I want my implementation to be generic, so the user can store an int, an std::string, or whatever custom class he wants in the B+tree. That's where the problem occurs: for primitive types or aggregated types that do not contain pointers that's all good, but as soon as the object contains a pointer/reference to an heap allocated object, this approach no longer works.

So my question is: is there some known way to overcome this difficulty? My personnal searches on the topic end up unsuccessful, but maybe I missed something.

Answer 1

As far as I know, there are three (somewhat) easy ways to solve this.

Approach 1: write a std::streambuf that points to some pre-allocated memory.

This approach allows you to use operator<< and use whatever existing code already exists to get a string representation of what you want.

• Pro: re-use loads of existing code.
• Con: no control over how operator<< spits out content.
• Con: text-based representations only.

Approach 2: write your own (many times overloaded) output function.

• Pro: can come up with binary representation.
• Pro: exact control over every single output format.
• Con: re-write so many output functions... writing overloads for new types by clients is a pain because they shouldn't write functions that fall in your library's namespace... unless you resort to Koenig (argument dependant) lookup!

Approach 3: write a btree_traits<> template.

• Pro: can come up with binary representation.
• Pro: exact control over every single output format.
• Pro: more control on output and format that a function, may contain meta data and all.
• Con: still requires you / your library's users to write lots of custom overloads.
• Pro: have the btree_traits<> detault to use operator<< unless someone overrides the traits?

Answer 2

You cannot write a truly generic and transparent version since if the pointer in a non-trivial item was allocated with malloc (or new and new[]), then it's already in the heap.

A non-transparent sollution may be serializing the class is an option, and this can be done relatively easy. Before you store the class you'd have to call the serialization function and before pulling it you'd call the deserialize. Boost has good serialization features that you could make work with your B+Tree.

Answer 3

Handling pointers and references in a generic way means you will need to inspect the type of the structure you're trying to store, and its fields. C++ is a language not known for its reflectiveness.

But even in a language with powerful reflection, a generic solution to this problem is difficult. You might be able to get it to work for a subset of types in higher level languages like Python, Ruby, etc. A related and more powerful paradigm is the persistent programming language.

The function you want is usually implemented by delegating responsibility for writing the data block to the target type itself. It's called serialization. It simply means writing an interface with a method to dump data, and a method to load data. Any class that wants to be persisted in your B-tree then simply implements this interface.