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

Subject: Re: [boost] Interest in B-tree library for Boost?
From: Beman Dawes (bdawes_at_[hidden])
Date: 2010-09-16 17:51:37

On Thu, Sep 16, 2010 at 1:37 PM, Jose <jmalv04_at_[hidden]> wrote:
> On Wed, Sep 15, 2010 at 6:04 PM, Beman Dawes <bdawes_at_[hidden]> wrote:
>> Any interest?
>
> Wow! This is one of the most exciting library proposals I've seen.

Glad it is of interest!

> When do you plan to support variable keys/values ?

That's the next major item on my do list. But I've only gotten as far
as a conceptual approach, and haven't had a chance to look at the
implementation experience of others. I think I read that the usual
approach of others was the obvious fixed element length array on each
page, pointing to the variable length storage portion of the page, but
I don't know if that is still considered state-of-the-art.

My old C package just kept the variable length elements ordered on
each page, and then did sequential searches! I intend to do better
than that this time around.

> Also,  do you plan to provide or have some thoughts on  Hash file
> index

Hash index: No plans. I've done that, many years ago, and it can be
effective. But it is fairly special purpose and probably better done a
separate library.

>or R-Tree ?

I've done an N-tree on top of a B-tree. (An N-tree is the same thing
as a Z-tree, just rotate the image 90 degrees.) Slick. I've worked on
a project where another developer added an R-tree on top of my C
language B-tree package. Very slick, although note that different
people use the term R-tree to mean somewhat different things - we were
focused on spatial search - i.e. range trees on minimum bounding
rectangles.  Bayer is pushing UB-trees, although that may be just a
different name for an N or Z tree, perhaps extended to more
dimensions. So, yeah, I'm interested. But those would be version 2
add-ons.

Cheers,

--Beman