Relaxed Radix Balanced Trees (2024)

rtheunissen · 2025-02-19T20:57:19 1739998639

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-hk · 2025-02-19T21:20:41 1740000041

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

prospero · 2025-02-20T05:23:16 1740028996

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

reitzensteinm · 2025-02-19T21:51:24 1740001884

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

jasonjmcghee · 2025-02-19T23:21:33 1740007293

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

baruchthescribe · 2025-02-19T23:02:27 1740006147

Thanks for this resource!

bjoli · 2025-02-19T20:43:04 1739997784

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.

bruce343434 · 2025-02-20T00:27:51 1740011271

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.

neonsunset · 2025-02-19T19:31:05 1739993465

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

lbindreiter · 2025-02-19T17:07:48 1739984868

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

p-hk · 2025-02-19T19:00:59 1739991659

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

anentropic · 2025-02-20T15:43:29 1740066209

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

dlisboa · 2025-02-20T16:50:45 1740070245

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

jasonjmcghee · 2025-02-19T17:14:21 1739985261

Not the author, but looks similar to excalidraw.

b0in · 2025-02-19T18:09:41 1739988581

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.