Relaxed Radix Balanced Trees (2024)(peter.horne-khan.com)

190 pointsby jasonjmcgheeletztes Jahr15 comments

Relaxed Radix Balanced Trees (2024)

https://peter.horne-khan.com/relaxed-radix-balanced-trees/

16 comments

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

p-hkletztes Jahr

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

prosperoletztes Jahr

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

reitzensteinmletztes Jahr

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

jasonjmcgheeletztes Jahr

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

baruchthescribeletztes Jahr

Thanks for this resource!

neonsunsetletztes Jahr

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

bjoliletztes Jahr

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.

bruce343434letztes Jahr

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.

lbindreiterletztes Jahr

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

p-hkletztes Jahr

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

anentropicletztes Jahr

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

dlisboaletztes Jahr

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

jasonjmcgheeletztes Jahr

Not the author, but looks similar to excalidraw.

b0inletztes Jahr

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.

[deleted]letztes Jahr