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

Subject: Re: [boost] Interest in B-tree library for Boost?
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2010-09-20 19:48:53

Hi Beman,

Beman Dawes wrote:
> A Boost B-tree library would provide disk-based associative containers
> that scale all the way from really, really, small to really, really,
> large.

> Any interest?

Yes, of course!  A couple of questions:

Does anyone have any thoughts about how atomic inserts can be 
implemented on top of this?  I'm not too concerned about recovering 
from random disk corruption, but I'd like to survive in the case where 
the program dies (e.g. another thread segfaults!) while inserting a new 
record.  Or, is the implementation "not quite atomic but safe enough" 
?  I have various lumps of code where the data is either read-only or 
append-only and this is not a problem.  I'm now faced with something 
where I need proper safe writes; I don't want to have to use SQLlite....

I'm also interested in spatial applications.  I have successfully used 
Z-curve techniques to adapt 1D containers for storing 2D (or higher) 
values and I'm sure this could also be used here (I guess that's what 
you mean by "Z or N tree").  Harder is the implementation of range 
storage (1D or e.g. bounding rectangles); Beman, you mentioned that 
someone had implemented an R-tree on top of your previous B-tree; can 
you say something about how that is done?  I have sometimes thought 
about how one could implement an interval tree as a layer on top of a 
simpler associative container, but have not found a solution.

Thanks,  Phil.