Skew binary trees. They're an immutable data structure combining the performance characteristics of lists (O(1) non-amortized push/pop) and b-trees (log(N) lookup and updates)
They use a sequence of complete trees, cleverly arranged using skew binary numbers so that adding an element never causes cascading updates.
In practice they're superseded by relaxed radix balanced trees.