1. 6

Relaxed Radix Balanced Trees (RRB-Trees) is one of the latest members in a family of persistent tree based data-structures that combine wide branching factors with simple and relatively flat structures. Like the battle- tested immutable sequences of Clojure and Scala, they have effectively constant lookup and updates, good cache utilization, but also logarithmic concatenation and slicing. Our goal is to bring the benefits of func- tional data structures to the discipline of systems programming via generic yet efficient immutable vectors supporting transient batch updates. We describe a C++ implementation that can be integrated in the runtime of higher level languages with a C core (Lisps like Guile or Racket, but also Python or Ruby), thus widening the access to these persistent data structures.

  1. 4

    The library, Immer, is here.

    I am impressed with the author’s writing, both in this paper and in Immer’s documentation. Very clear and understandable coverage of complex topics.

    Stories with similar links:

    1. Persistence for the Masses: RRB-Vectors in a Systems Language (2017) via nickpsecurity 4 years ago | 8 points | 9 comments