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.