Re: [boost] Interest in B-tree library for Boost?

Subject: Re: [boost] Interest in B-tree library for Boost?
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-09-15 12:44:42

Beman Dawes wrote:
> A Boost B-tree library would provide disk-based associative containers
> that scale all the way from really, really, small to really, really,
> large. B-trees perform well on hardware ranging from ancient floppy
> disk drives all the way up to humongous disk arrays. They are the
> technology behind most high-performance disk file systems and
> databases.
...
> Initial timing tests have been very encouraging. The time test
> compares the btree_map implementation to std::map. As expected, a
> btree_map is many times slower than a std::map, given a cold operating
> system file cache and constraining the btree_map's caching to a
> minimum. But at the other extreme, when the O/S file cache is warm and
> the btree_map's cache is as large as the file, the btree_map is very
> similar in speed to std::map.The btree library's code is still very
> new, so timings and everything else may be subject to lots of
> revision.

Was this post prompted by the Judy tree question raised yesterday?

Is the code in the sandbox?

Now that we have broken free of the 32bit addressable limit for commodity hardware there is less need for self paging data structures than there was a few years ago.  Unless there is a way to configure it that gives a performance advantage over std::map we might have to wait until 64 bits  (or 48 as the case may be) becomes too confining.  People will generally invest in more memory than better code since memory can be mass produced in a factory while smart programmers are not yet completely commoditized.

I looked into the details a little and I found it funny that you followed the advice I gave on the geometry list a couple days ago in the discussion of the design of a "generic" tree:

"Node could even be declared as a private sub-class of tree to keep people's hands off of it and make it easier to implement by allowing it to share the template parameters of tree."

I notice you made your private branch and leaf types classes instead of structs.  Since they are tightly coupled to the tree by virtue of being private member classes I'm not sure they need data hiding to protect their members from the tree.  I would have made them structs.  You could be right, however, that protecting oneself from oneself is worthwhile.  Certainly there is rarely anyone else writing bugs and violating design intent in the details of most libraries.

Regards,
Luke