Re: [boost] B-tree for handling hugh datastructures (partly on disk)

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 
accurate.

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.

--Beman