From: Beman Dawes (bdawes_at_[hidden])
Date: 2003-12-16 06:43:45
At 10:17 AM 12/15/2003, Jeremy Maitin-Shepard wrote:
>"Toon Knapen" <toon.knapen_at_[hidden]> writes:
>> A few months ago there was some initial discussion about implementing a
>> B-tree to handle hugh datastructures by storing parts of the B-tree on
>> Could someone tell me if there is still something going in this area
>Such a library would probably depend on a serialization library
>(i.e. Robert Ramey's).
Not likely. Actually, that's too mild. "No chance at all" would be more
While a B-tree built on top of a serialization library might meet the
description of B-trees given in entry-level computer science texts, a
practical implementation is going to use some very low-level techniques to
achieve very high performance.
For example, put "B-tree key compression" into Google and read a few of the
entries to get an overview of some of the pre-compression and
post-compression techniques used to minimize the size of keys.
A Boost B-tree might want to avoid some of the more extreme optimization
techniques. Their benefit / cost ratio isn't high enough. But almost any
production quality B-tree will be implemented via very low-level binary
I/O, with carefully tailored caching.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk