Subject: [boost] Interest in B-tree library for Boost?
From: Beman Dawes (bdawes_at_[hidden])
Date: 2010-09-15 12:04:08
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
If you don't know what a B-tree is, or think that "B-tree" is an
abbreviation for "Binary tree", you might want to read the Wikipedia
B-Tree article: http://en.wikipedia.org/wiki/B-tree. Knuth and other
computer science texts also supply descriptions.
See http://mysite.verizon.net/beman/btree/index.html for a more
complete description of the proposed library.
A preliminary implementation is available. Download
http://mysite.verizon.net/beman/btree/btree-preview-1.zip, and unpack
into a current Boost distribution. A few existing Jamfiles will be
overwritten. The only compilers tested and working so far are VC++ 10
and GCC/MinGW 4.5.
You can view the library online at http://github.com/Beman/Boost-Btree
There is no detailed documentation yet, but if you know how to use
std::map and other standard library associative containers, you
already know most of what you need to know. Critical differences are
documented in the Library Characteristics section of the index.html
page referenced above.
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk