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

[Timo Bingmann]

Hello people,

I want to ask if there is an interest in adding an in-memory B+-Tree
container implementation that I wrote some time ago:

https://github.com/bingmann/stx-btree
http://panthema.net/2007/stx-btree/

It emulates the std::set/map/multiset/multimap interfaces as far as
possible (there are some unavoidable minor exceptions). And since I keep
telling my collegues to stop using std::map for bigger instances, I
think adding it to Boost would be a good idea.

So ... I could clean up my old implementation, add C++11/Boost move
semantics, use of uninitialized objects, boostify various things, etc,
etc, and then things should be pretty fine.

I also have an idea to modify/fork the implementation to create a B-tree
(non-plus) container, which should be a bit slower, but provide an
interface even closer to std::map (only remaining unavoidable
incompatibility would be with iterator invalidation).

My main question before starting this is whether it is a better idea to
add it to Ion's existing Container library, or to add it as a separate
"library" under Boost like the existing circular_buffer, which is pretty
old. Apparently libraries have gotten bigger over Boost's life. So which
variant would be better? The "Container" library seems to be more
targeted at reimplementing STL containers with new features, and simple
new containers, not complexer ones? But it should still be a good match.

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.

Best Regards,
Timo Bingmann

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Phil Endecott]

Hi Timo,

Timo Bingmann wrote:
> I want to ask if there is an interest in adding an in-memory B+-Tree
> container implementation that I wrote some time ago:
>
> https://github.com/bingmann/stx-btree
> http://panthema.net/2007/stx-btree/

How does it compare to Google's implementation:

http://code.google.com/p/cpp-btree/

?

Basically, yes, I think this is functionality that would be worth having.



Regards, Phil.

[Zach Laine]

On Tue, Jun 9, 2015 at 11:28 AM, Phil Endecott <
spam_from...@chezphil.org> wrote:

> Hi Timo,
>
> Timo Bingmann wrote:
>
>> I want to ask if there is an interest in adding an in-memory B+-Tree
>> container implementation that I wrote some time ago:
>>
>> https://github.com/bingmann/stx-btree
>> http://panthema.net/2007/stx-btree/
>>
>
> How does it compare to Google's implementation:
>
> http://code.google.com/p/cpp-btree/
>
>

Beman Dawes has a very good implementation as well, FYI.

https://github.com/Beman/btree

Zach

[Phil Endecott]

Zach Laine <whatwasthataddress <at> gmail.com> writes:
> > Timo Bingmann wrote:
> >
> >> I want to ask if there is an interest in adding an in-memory B+-Tree
> >> container implementation that I wrote some time ago:
> >>
> >> https://github.com/bingmann/stx-btree
> >> http://panthema.net/2007/stx-btree/

> Beman Dawes has a very good implementation as well, FYI.
>
> https://github.com/Beman/btree

That's not in-memory, IIRC.


Phil.

[Zach Laine]

On Tue, Jun 9, 2015 at 12:10 PM, Phil Endecott <
spam_from...@chezphil.org> wrote:

> Zach Laine <whatwasthataddress <at> gmail.com> writes:
> > > Timo Bingmann wrote:
> > >
> > >> I want to ask if there is an interest in adding an in-memory B+-Tree
> > >> container implementation that I wrote some time ago:
> > >>
> > >> https://github.com/bingmann/stx-btree
> > >> http://panthema.net/2007/stx-btree/
>
> > Beman Dawes has a very good implementation as well, FYI.
> >
> > https://github.com/Beman/btree
>
> That's not in-memory, IIRC.

It is, optionally. And it typically outperforms std::map and friends when
it is in-memory.

Zach

[Vadim Stadnik]

On Wed, Jun 10, 2015 at 12:07 AM, Timo Bingmann <t...@panthema.net> 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