Re: Questions about incorporating my library into a new library within Boost

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2022-07-28 12:57:50

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.