Boost logo

Boost :

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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at