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