RRB-Trees: Efficient Immutable Vectors

• Publication date: 2011

Immutable vectors are a convenient data structure for functional programming and part of the standard library of modern languages like Clojure and Scala. The common implementation is based on wide trees with a fixed number of children per node, which allows fast indexed lookup and update operations. In this paper we extend the vector data type with a new underlying data structure, Relaxed Radix Balanced Trees (RRB-Trees), and show how this structure allows immutable vector concatenation, insert-at and splits in O(log N) time while maintaining the index, update and iteration speeds of the original vector data structure.

Keywords: data structures ; concatenation ; functional programming

Reference

• EPFL-REPORT-169879

Record created on 2011-10-31, modified on 2012-03-21