[duped]

There are entire fields of research dedicated to studying cache oblivious persistent data structures, and they're almost always trees.

One of the key points of immutable datastructures is that they're easy to reason about given that the invariants are upheld. Designing an efficient memory representation that upholds those invariants is an entirely separate problem domain. Not every pointer dereference is slow, and not every tree is represented with pointers.