Relaxed Radix Balanced Trees (2024)

What tool were those tree structure Illustrations created with? They look really nice!

Not the author, but looks similar to excalidraw.

this looks like draw.io with a custom font. edit: nope, i'm wrong, its excalidraw but the effect is almost identical in draw.io.

Thanks! I used draw.io and tweaked a number of the display properties to make it look more like Excalidraw.

If you like radix trees, you may also find this article interesting and useful: https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-lin...

I always wanted a comparison to ropes. Every time I see ropes mentioned I always think "why not use RRB trees?". It seems like less housekeeping, but with all the benefits.

I would love to add a good RRB implementation to the persistent benchmarks at [1] to get a state-of-the-art comparison between RRB and BST in a persistent context. Duration, of course, but also number of bytes copied etc.

https://rtheunissen.github.io/bst

I can't vouch for them, but there are Clojure[1] and C[2] implementations you might consider.

[1] https://github.com/clojure/core.rrb-vector

[2] https://github.com/hyPiRion/c-rrb

This guide is absolutely fantastic, thank you! You should post it if it hasn't been.

Thanks for this resource!

It has, and a pretty good discussion: https://news.ycombinator.com/item?id=37130200

Let T[] denote "dynamic array of T": rope = string[] = char[][].

As I understand it, usually each line of text is in its own memory buffer.

Here’s one in Java: https://github.com/lacuna/bifurcan/blob/master/src/io/lacuna...

I love the styling of this blog post generally too - simple, attractive and pleasant to read - kudos

Did you do them by hand or use some algorithmic way to construct them?