Persistent map
How immutable AVL roots share nodes and values across snapshots without parent-chain reads.
Status: Foundation. An original immutable AVL map is implemented in Zig 0.16.0. It is an in-memory component and performs no disk I/O.
One root, many owners
Map stores owned byte-string keys and values in lexicographic byte order. Empty keys, empty values and embedded zero bytes are valid. It does not interpret documents or enforce schemas.
Cloning a map retains its current root without allocating or copying its records. A put or remove returns a new owning map; the source remains unchanged. Updates copy the affected balanced-tree paths and reuse untouched subtrees.
Node and payload reference counts are separate. A copied ancestor can share its key/value storage as well as its unchanged children.
| Operation | Structural cost |
|---|---|
| Initialize, clone, count | Constant structural work. |
| Lookup | Logarithmic key comparisons; comparison cost also depends on key length. |
| Put/remove | Logarithmic path work plus new key/value bytes where needed. |
| Full iteration | Linear traversal in key order. |
| Release | Visits nodes whose last reference disappears; final release can be linear. |
These are algorithmic properties, not measured throughput claims. Reference-count contention, payload sizes and the allocator affect actual performance.
Own handles explicitly
Each successful clone or mutation returns an owner that must be released. Copying the Zig struct by assignment does not create another owner; use clone when both lifetimes are needed.
A value returned by get borrows its source snapshot's storage. Keep that handle alive while using the value. An iterator retains its own root and keeps returned key/value slices valid until the iterator is released, even after the original map is gone.
Separately retained handles support concurrent reading, mutation into new roots and release when the allocator is thread-safe. Racing a handle's own destruction with its use is invalid. Publishing a shared current root therefore requires a separate ownership-acquisition protocol.
What the tests establish
The module tests branches of branches, copied input ownership, binary keys, ordered iteration, structural sharing and release accounting. They check balancing across 1,024 inserts/deletes and compare 2,400 randomized operations over 12 snapshots with an independent model.
Allocation-failure and concurrent retained-handle tests exercise cleanup and lifetime boundaries. They do not establish durable snapshots, a branch catalog, disk garbage collection or complete database concurrency.
The prepared state engine uses this map to build branch-aware transactions.