Boost logo

Boost :

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
>> disk.
>> 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, gregod at, cpdaniel at, john at