Re: [boost] B-tree for handling hugh datastructures (partly on disk)

From: Beman Dawes (bdawes_at_[hidden])
Date: 2003-12-15 09:55:29

At 02:56 AM 12/15/2003, Toon Knapen wrote:

 >A few months ago there was some initial discussion about implementing a
 >B-tree to handle hugh datastructures by storing parts of the B-tree on
 >disk.
 >
 >Could someone tell me if there is still something going in this area ?

Several years ago I implemented a B-tree for Boost, but was dissatisfied 
with it so never submitted it. Some of the problems included that for a 
B-tree to be efficient, it has to deviate from the Associative Container 
requirements in many ways, large and small. I was afraid that would be 
error-prone, and that users would be dissatisfied with the interface. The 
iterator-based design also ran about twice as slow as the older 
cursor-based design I had used in the past.

The availability of Boost type_traits and concept checking libraries now 
probably means that usage errors can be detected at compile time, rather 
than showing up as runtime crashes. The C++ committee has also resolved an 
iterator issue that was a concern. The Boost iterator adaptors would be a 
great help, too, and weak_ptr's might make the page cache management 
easier.

If the project were restarted, I'd rethink the interface so that the 
portions which look like Associative Container operations were in fact 
Associative Container compliant, and the operations which behaved 
differently from the Associative Containers had interfaces different from 
the usual interfaces.

That's the status at the moment.

--Beman