Re: [boost] Determining interest in container with efficient random access insert and erase

Subject: Re: [boost] Determining interest in container with efficient random access insert and erase
From: Chris Clearwater (chris_at_[hidden])
Date: 2015-09-12 10:06:02

On 09/12/2015 06:12 AM, Vadim Stadnik wrote:
> There are many variants of B+ trees. A document with explanation of the
> implemented data structure and key algorithms would be quite helpful. It
> should provide figures.
>
> Is this a level-linked variant of B+ trees or not?
No, it is not. In fact the bottom level of the tree doesn't contain any 
metadata at all. This is done to minimize cache misses. All other levels 
include parent pointer/parent index/length metadata.

> To make this B+ tree much more useful, it should supports not only
> sequences, but also std::set<T>, std::multiset<T>, std::map<T> and
> std::multimap<T>. Alternatively, you can implement all of these standard
> containers using your B+ tree as underlying data structure.
>

Yes, I agree this would increase its usefullnes, but it's not something 
I plan on supporting now.

You might also be interested to see the benchmarks[1] I've included in 
the repository. Your container is included for comparison (bpt_sequence).

[1] https://github.com/det/segmented_tree_seq/tree/benchmarks