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