Interest in B-Tree and B+-Tree Implementation?
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
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.
On Tue, Jun 9, 2015 at 11:28 AM, Phil Endecott < spam_from_boost_dev@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:
Beman Dawes has a very good implementation as well, FYI. https://github.com/Beman/btree Zach
Zach Laine
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.
That's not in-memory, IIRC. Phil.
On Tue, Jun 9, 2015 at 12:10 PM, Phil Endecott < spam_from_boost_dev@chezphil.org> wrote:
Zach Laine
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.
That's not in-memory, IIRC.
It is, optionally. And it typically outperforms std::map and friends when it is in-memory. Zach
On Wed, Jun 10, 2015 at 12:07 AM, Timo Bingmann
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-Sem... 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
participants (4)
-
Phil Endecott -
Timo Bingmann -
Vadim Stadnik -
Zach Laine