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
On 09/12/2015 06:12 AM, Vadim Stadnik wrote: 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