On Wed, Sep 15, 2010 at 7:39 PM, Thorsten Ottosen <nesotto@cs.aau.dk> wrote:
Den 15-09-2010 18:04, Beman Dawes skrev:
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.
Any interest?
Yes!
Also, it would be useful to have a B-heap:
<grin> Yeah, I saw that article. Very interesting. I wonder how many other algorithms could be sped up markedly by clumping data to take advantage of cache characteristics. Once all the data is in memory, my B-tree find() function timing test actually runs a bit faster than a std::map, using the Microsoft compiler and standard library, in spite of all it's cache management overhead. I suspect that's the impact of the CPU memory cache. OTOH, the B-tree version is 20% slower than the standard library map for GCC compiler and its standard library, so it may just be a Microsoft implementation issue. Their timings are about that amount slower than GCC's. Thanks, --Beman