[HN Gopher] Relaxed Radix Balanced Trees (2024)
       ___________________________________________________________________
        
       Relaxed Radix Balanced Trees (2024)
        
       Author : jasonjmcghee
       Score  : 177 points
       Date   : 2025-02-19 16:05 UTC (1 days ago)
        
 (HTM) web link (peter.horne-khan.com)
 (TXT) w3m dump (peter.horne-khan.com)
        
       | lbindreiter wrote:
       | What tool were those tree structure Illustrations created with?
       | They look really nice!
        
         | jasonjmcghee wrote:
         | Not the author, but looks similar to excalidraw.
        
         | b0in wrote:
         | 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.
        
         | p-hk wrote:
         | Thanks! I used draw.io and tweaked a number of the display
         | properties to make it look more like Excalidraw.
        
           | anentropic wrote:
           | I love the styling of this blog post generally too - simple,
           | attractive and pleasant to read - kudos
        
           | dlisboa wrote:
           | Did you do them by hand or use some algorithmic way to
           | construct them?
        
       | neonsunset wrote:
       | 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...
        
       | bjoli wrote:
       | 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 wrote:
         | 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.
        
       | rtheunissen wrote:
       | 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 wrote:
         | 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 wrote:
           | Here's one in Java: https://github.com/lacuna/bifurcan/blob/m
           | aster/src/io/lacuna...
        
         | reitzensteinm wrote:
         | This guide is absolutely fantastic, thank you! You should post
         | it if it hasn't been.
        
           | jasonjmcghee wrote:
           | It has, and a pretty good discussion:
           | https://news.ycombinator.com/item?id=37130200
        
         | baruchthescribe wrote:
         | Thanks for this resource!
        
       ___________________________________________________________________
       (page generated 2025-02-20 23:02 UTC)