Jooseong Lee wrote:
What is not stored contiguously is child, this is stored in std::vector<std::unique_ptr>. But when N keys are erased, the number of children erased is not O(N), because a node can have #(fanout) keys.
I have to correct this sentence, the number of children erased is O(N). But the coefficient is small, because practically B-Trees use large fanouts.
Most technically, a call for erase_range(a, b) would be O(log N) + O(K) where N is the number of whole keys and K is the number of keys being erased. I've updated the repo description, thanks for the catch.
Good, I'm glad I don't have to give the CS101 complexity lecture :-) One other comment - how do you deal with strings? To get the locality benefits of the B-Tree you can't store variable-size data totally out-of-band. Regarding the general "how do I get this in Boost?" question, I encourage you to look back through the mailing list archive at the last few "Is Boost interested in my XYZ libary?" threads. Some people post useful replies about what to do next which. Cynically, what happens most often is that there are one or two emails and then the library author and any replies disappear. Some persistence is required to make anything happen. One hint: put something more descriptive (i.e. "B-Tree") in your subject line! Regards, Phil.