Re: [boost] [stl_ext_adv] ] Interest in advanced data structures

Subject: Re: [boost] [stl_ext_adv] ] Interest in advanced data structures
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2011-12-03 17:22:19

On Sun, Dec 4, 2011 at 8:34 AM, Nathan Ridge <zeratul976_at_[hidden]> wrote:

>
> > * Question #1: why augmenting on B+ trees? The augmenting idea
> > can be as easily built on top of RB-trees, which are
> > the weapon of choice for implementing associative containers.
> > Unless proved otherwise, RB-trees are assumed to be faster than B+
> > trees for in-memory structures (which your own tests hint at, cf.
> > "insert N random elements" table.)
>
> Could a B+ tree library be a basis for implementing disk-backed B+
> trees? I think that would be useful. In a clever implementation
> the memory-backed and disk-backed B+ tree might even be the same
> class, with the difference factored out into a policy template
> parameter.
>
> Regards,
> Nate
>
> I understood this comment is about adding persistence or serialization
support to the proposed B+ trees. Please correct if this is not the case.
There are two levels of complexity in this area.
A trivial one is just saving and reading data as a list, since these B+
trees are build on top of doubly linked lists. This might be sufficient for
many practical applications, but certainly not for all.
Hence there is the second and less trivial problem of saving and reading
operations which preserve topology of these B+ trees that are designed to
work in RAM. (Note: "topology" has been used here as a state of
connectivity of nodes with data stored in the nodes).
In principle, the problem can be solved for the submitted B+ trees, but I
will need some Boost specific requirements to implement this feature.

Regards,
Vadim