Notes on Persistent Data Structures
Immutability is not only about purity. It can also be a performance tool.
Persistent data structures have a reputation for being elegant but impractical. That reputation is deserved in some settings and unfair in others. When implemented carefully, structural sharing can buy you excellent ergonomics and surprisingly good real-world performance.
The key mental model is that “copying” a tree does not mean duplicating all of it. Most operations only rebuild the path from the root to the modified node and reuse everything else. That means snapshots become cheap, undo history becomes natural, and concurrency gets less dramatic.
In backend systems, the benefit is often not raw speed but confidence. The less state you mutate in place, the less accidental aliasing you have to debug at 2 AM. There is also a pleasant compositional quality: old versions of a value stay meaningful.
Of course, persistence is not free. Cache locality can worsen, and constant factors matter. But if your workload needs versioning, speculative computation, or branch-heavy transformations, the tradeoff can be excellent.
I increasingly think of persistence as a design technique, not a doctrine. Use it where history matters. Use it where sharing beats copying. And use it where correctness is more expensive than memory.