ptrie

Ptrie, short for persistent trie, is a functional data structure that implements an associative array using a trie (prefix tree) in a purely immutable way. The structure is designed so that updates such as insertion, deletion or modification produce a new version of the map while sharing unchanged sub‑tries with the previous version. This property allows efficient persistence: several versions of the map can coexist with minimal memory overhead, usually proportional to the number of changes rather than the size of the entire structure.

A typical ptrie is implemented as a tree of nodes, each node holding up to a fixed branching factor, often 32 or 256, with an array of child pointers. Keys are hashed and the hash is processed in chunks matching the branching factor to navigate the tree. Because nodes are immutable, a modification results in a new path of nodes from the root to the modified leaf, while all other branches are reused unchanged. Path copying, combined with structural sharing, gives a worst‑case time complexity of O(log_b n) for lookups and updates, where b is the branching factor. In practice, with a large branching factor and short hash paths, operations are close to constant time for typical workloads.

Ptries are used in functional programming languages such as Clojure, Scala, and in libraries like C++'s boost::ptrie, to provide efficient, thread‑safe, immutable hash maps. They are suitable for concurrent systems where multiple threads may read from or write to the map without locking. The persistence feature also makes ptries useful for undo functionality, version control systems, and in-memory databases that require snapshots.

The concept of the persistent trie dates back to the 1980s in functional data structure research, with significant development in the 1990s and popular adoption in modern programming language libraries since 2010. It represents a blend of classic trie semantics with functional persistence, offering both space efficiency and fast random access in a purely immutable context.