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-15 21:51:02

On Wed, Sep 15, 2010 at 8:02 PM, Stefan Strasser <strasser_at_[hidden]> wrote:
> Zitat von Beman Dawes <bdawes_at_[hidden]>:
>>> http://stldb.sourceforge.net/
>>>
>>> I don`t think it implements a B-trees at this point (but some kind of
>>> tree,
>>> see trans_map), but aims to provide an infrastructure for any kind of
>>> tree
>>> or container.
>>
>> That library seems to deal with a higher, more database -like, level.
>
> I`m not sure if that`s the case. if your goal was just to implement a STL
> "map" interface with a B-tree data structure instead of a rb-tree I would
> see the difference, but you stated that your implementation is aimed towards
> disk-based B-trees.

> then I don`t see how you don`t end up with some of the things STLdb tries to
> do, like logging and crash recovery.

Applications are free to do things like logging or crash recovery if
they care too. But uses that have no need for such features shouldn't
have to pay for them.

That said, the current implementation does mark pages in such a why
that undamaged portions of a damaged file can be recovered. That has
proven useful in practice, although as systems have gotten more
reliable people don't seem to be doing that sort of damage recovery as
often as 20 years ago. Providing damaged file recovery tools is on my
do list.

> in case it is the transaction and concurrency stuff of STLdb that reminded
> you of "database-like" features, I don`t think that makes it an entirely
> different problem domain. for example, Berkeley DB can be used as a simple
> associative container on disk, without any transactions (and is even sold as
> such seperately), but can optionally be used with transactions.

The first step is having a reliable B-tree implementation. My own
experience has been in applications where subsequent interest is more
in areas like multidimensional search, but that's just because my
background is in applications where fully featured database software
was traditionally way too slow.

Thanks,

--Beman