Re: [boost] Interest in B-tree library for Boost?

Subject: Re: [boost] Interest in B-tree library for Boost?
From: Cory Nelson (phrosty_at_[hidden])
Date: 2010-09-15 22:40:23

On Wed, Sep 15, 2010 at 6:08 PM, Beman Dawes <bdawes_at_[hidden]> wrote:
> On Wed, Sep 15, 2010 at 7:26 PM, Cory Nelson <phrosty_at_[hidden]> wrote:
>> - Will this support multiple B-trees in one file?
>
> Not currently. That would be relatively easy to support. What is the
> motivating use case?

Just ease of distribution, really.

I'm currently using a SQLite database to distribute a few tables of
read-only data that doesn't need SQL, relational, or ACID properties
-- it's just the best thing available in terms of ease of distribution
and portability.  I'd love to remove all the unneeded layers and just
use a B-tree directly.

>> - Will this implement ACID properties?
>
> No. The model is a standard library associative container, not a
> database. ACID properties can be built on top of B-trees, but the
> B-trees themselves don't have ACID properties, other than a few
> aspects like atomic writes.

Alright, that clears up my understanding about the scope of this.
Still sounds great!

>> - Can this be adapted for in-memory use as well, with full non-POD support?
>
> No current plans for that. Why wouldn't you just a standard library
> associative container for that?

Storing keys together improves cache usage a lot for small keys, and
allows the CPU to detect ordered iteration to prefetch the next cache
line.  It also reduces fragmentation and the maximum number of pages
that must be touched to find a result, which in turn reduces TLB
misses and page faults.  The tests here indicate that this can be very
significant with large collections:

http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

-- 
Cory Nelson
http://int64.org