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

Subject: Re: [boost] [stl_ext_adv] ] Interest in advanced data structures
From: Nathan Ridge (zeratul976_at_[hidden])
Date: 2011-12-03 17:28:00

> > > * 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.

What I mean by a disk-backed B+ tree is a B+ tree where only the nodes that
are needed at a given time are loaded into memory from disk - the entire
tree on disk might be too large to even fit into memory.

Regards,
Nate