RRB vectors

Clojure’s and Scala’s vectors are radix-balanced trees: every node has exactly 32 slots, so the index itself spells the path, 5 bits per level, and a vector indexed by 32-bit integers is at most 7 levels deep. That makes lookup and update effectively constant, but concatenating two vectors means rebuilding one of them. Phil Bagwell and Tiark Rompf’s relaxed radix-balanced trees (RRB-Trees, EPFL report 2011) allow nodes that are not completely full. An unbalanced node stores the cumulative sizes of its children, so lookup does a short search there and falls back to plain radix indexing in balanced subtrees. Concatenation merges the touching edges of the two trees and rebalances them, which keeps the height logarithmic and makes concatenation, insert-at and split O(log n).

Nicolas Stucki, Rompf, Vlad Ureche and Bagwell turned this into a practical Scala collection (ICFP 2015). Each vector caches one focused branch from the root to a leaf, which makes appends at either end, updates and deletions amortized constant time when they happen near each other. In their benchmarks memory use was on par with arrays and an order of magnitude below red-black and finger trees, sequential reads were at most 2 times slower than an array and random access 2 to 3.5 times slower. Bagwell died on 6 October 2012, before the paper appeared.

Pick an RRB vector as a default immutable sequence when you also need to join, split or insert in the middle, for example to split work across threads and join the results. Rust’s im crate has used one for Vector since 2018, and Juan Pedro Bolívar Puente’s C++ library immer offers one as flex_vector, described in Bolívar Puente’s ICFP 2017 paper.