Re: [boost] Boost Btree ?

From: Beman Dawes (bdawes_at_[hidden])
Date: 2006-10-25 21:25:49

Bernhard Reiter wrote:
> Am Dienstag, den 24.10.2006, 20:40 -0500 schrieb Rene Rivera:
>> Jose wrote:
>>> The SOC project is for a memory container not a disk one
>> Not strictly true. The SoC project is for consistent algorithms and 
>> concepts for any kind of tree. The idea is the same as for the current 
>> STL algorithms, of working with any form of container.
> 
> Admittedly, there isn't much B-tree related code in the repository yet;
> to the not-so involved, the current strategy is having a b_tree adaptor
> wrap around a multiway_tree adaptor wrapping around an nary_tree, and
> all that's there as of yet are some experiments implementing the latter
> two. The idea is, however, providing common bases to different
> applications (a B-tree, like a B*-tree, both being multiway trees) such
> that this framework maps relations between different trees somewhat
> consistently.
> 
> That said, any contributions re the "disk" part would be very welcome,
> as I don't have any experience with all the locking/invalidating
> necessary. I was hoping this was/could be made a pure allocator issue,
> but I'd be glad if anybody enlightened me if there're obstructions to
> that approach.

Managing the b-tree page cache is one of the prime difficulties with 
trying to reuse code developed for in-memory uses. Iterators have to be 
constant iterators and a separate update() member provided to change the 
contents of the tree. Otherwise there is no way to know when the page 
cache is dirty. And if the implementation doesn't know when the cache is 
dirty, all touched pages have to be rewritten to disk; that is a 
showstopper performance wise.

An implementation using memory-mapped files could avoid that problem, 
but would be useless for a significant number of real-world apps on 
32-bit platforms, because the file size would be limited. Multiple 
window memory-mapping might work, but that is a lot to bite off.

--Beman