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

From: Jooseong Lee (frozenca91_at_[hidden])
Date: 2022-07-28 13:18:33

> 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.

For std::string and its friends (i.e. not trivially copyable types) it is
stored as something like std::vector<std::string>, so it is not *that* good
(but still better than std::set<std::string>). Google Abseil's B-Tree
implementation use similar approach.

When I personally use my B-Tree for strings, I use raw char arrays like
std::array<char, 16>

> 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.

Thanks, I'll have a look.

Best,
Jooseong

On Thu, Jul 28, 2022, 9:58 PM Phil Endecott via Boost <boost_at_[hidden]>
wrote:

> 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.
>
>
>
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>