Re: [boost] Interest in B-Tree and B+-Tree Implementation?

Subject: Re: [boost] Interest in B-Tree and B+-Tree Implementation?
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2015-06-10 04:09:59

On Wed, Jun 10, 2015 at 12:07 AM, Timo Bingmann <tb_at_[hidden]> wrote:

>
> In the incubator I found the "STL Extensions" submission, which appears
> to be dead. It aims to provide "augmented array based B+ trees", which
> is different from the usual trees where nodes are dynamically allocated.
>
>
Thank you for mentioning “STL Extension”, although I do not understand what
you mean "it appears to be dead”?

This library was prepared for Boost review quite a while ago. There is
interest in this and similar library CounterTree written by Francisco José
Tapia, but there is a problem of finding review managers. Both libraries
offer variants of standard containers based on augmented trees.

These advanced data structures enable the representation of fundamental
math concepts with significantly better efficiency than basic data
structures used in standard containers. As an introduction to this area,
refer to the following article, which discusses one the most interesting
applications (semigroup and monoid):

http://www.codeproject.com/Articles/837555/Efficient-Representation-of-a-Semigroup-in-Cpluspl

Can you briefly describe advantages of your B and B+ trees over basic
red-black trees?

Which operations are more efficient?

In which applications they can replace standard containers with the
performance benefit for user algorithms?
Can these trees efficiently support standard sequence containers and
replace std::vector?
Can you implement in memory aggregation trees?

Regards,
Vadim Stadnik