go-immutable-art

An immutable adaptive radix tree for Go.

A persistent, copy-on-write map from []byte keys to values. Every write returns a new tree and leaves the old one untouched, so readers need no locks and no coordination.

• O(k) Get, Insert and Delete, where k is the key length.
• Ordered iteration forwards and backwards, with prefix scans and lower-bound seeks.
• Watch channels on every node and leaf, fired when the subtree beneath them changes.
• Transactions that batch many writes into one new root.
• Sized nodes — inner nodes hold 4, 16, 48 or 256 children and grow and shrink with their child count, instead of every node paying for one shape.
• No dependencies, and a drop-in API for hashicorp/go-immutable-radix.

Install

go get github.com/kswap/go-immutable-art

Usage

import art "github.com/kswap/go-immutable-art"

tree := art.New[string]()
tree, _, _ = tree.Insert([]byte("hello"), "world")

v, ok := tree.Get([]byte("hello"))     // "world", true

Batch writes in a transaction:

txn := tree.Txn()
txn.Insert([]byte("a/1"), "one")
txn.Insert([]byte("a/2"), "two")
tree = txn.Commit()

Iterate in key order, or over a prefix:

it := tree.Root().Iterator()
it.SeekPrefix([]byte("a/"))
for key, val, ok := it.Next(); ok; key, val, ok = it.Next() {
    fmt.Println(string(key), val)
}

Watch a subtree for changes. CommitOnly publishes the new root and Notify wakes watchers afterwards, so a watcher that wakes always reads the new tree:

it := tree.Root().Iterator()
ch := it.SeekPrefixWatch([]byte("a/"))

txn := tree.Txn()
txn.TrackMutate(true)
txn.Insert([]byte("a/3"), "three")
tree = txn.CommitOnly()
txn.Notify()

<-ch // fires

Documentation

Full API reference at pkg.go.dev.

Benchmarks

Against hashicorp/go-immutable-radix, both trees driven directly with no interface shim in any measured path, over one shared corpus of 200,000 keys encoded the way a database index encodes them: strings null-terminated, integers big-endian, UUIDs as 16 raw bytes.

Apple M4 Max, Go 1.25.7, -count=8, medians via benchstat. Faster figure in bold.

Operation	Dataset	go-immutable-art	go-immutable-radix
Get (hit)	uuid	36.0 ns	122.1 ns
	word	69.8 ns	132.4 ns
	sequint	13.9 ns	33.9 ns
	compound	47.2 ns	50.2 ns
Get (miss)	uuid	9.7 ns	21.9 ns
	word	3.0 ns	4.0 ns
	sequint	3.0 ns	3.2 ns
	compound	3.0 ns	3.1 ns
Insert, 1 key	uuid	83.3 ns	198.8 ns
	sequint	83.2 ns	198.7 ns
Insert, 10,000 keys	uuid	636.8 µs	1504.5 µs
	sequint	499.5 µs	835.1 µs
Update	uuid	842 ns	2122 ns
	word	484 ns	1200 ns
	sequint	607 ns	1636 ns
	compound	358 ns	1022 ns
Iterate, 200,000 keys	uuid	2.13 ms	2.54 ms
	word	2.09 ms	2.66 ms
	sequint	556 µs	414 µs
	compound	750 µs	734 µs
LowerBound + 10 keys	sequint	91 ns	143 ns
	randuint	236 ns	404 ns
LowerBound + 1000 keys	sequint	2.91 µs	2.18 µs
	randuint	10.2 µs	12.3 µs
Prefix scan, 10 keys	compound	105 ns	94.6 ns
Memory	uuid	127.6 B/key	161.4 B/key
	word	127.8 B/key	159.4 B/key
	sequint	105.0 B/key	131.3 B/key
	compound	118.7 B/key	152.0 B/key

Two further datasets are measured and left out of the table because they track the ones above: randuint matches uuid, and prefixstr matches compound — except on Get (hit), where prefixstr is the one case that loses, at 48.3 ns against 46.2 ns.

Takeaways

Reads depend on the key shape. High-entropy keys — UUIDs, random integers — are around 3× faster, because every byte branches and a sized node indexes its children directly where a radix node searches an edge slice. Keys with long shared prefixes come out level: both trees compress the prefix, so the lookup is the same comparison in both.

Writes are faster on every shape measured, by 1.7× to 2.9×, and hold about a fifth less memory per key. Path copying rebuilds a node sized to its children rather than one shape for every node, so an update allocates 5–10 objects where the radix tree allocates 23–44.

Iteration is faster on sparse keys and slower on dense ones. Sequential integers pack their nodes completely, which is where a flat edge slice is at its best; the same scan over UUID or word keys is 15–22% faster. Iterators allocate one object here against four or five, so a scan that is slower in time can still be cheaper under GC pressure.

Differences from go-immutable-radix

Two behaviours are deliberately not reproduced, both cases the original leaves untested:

• WalkBackwards yields true reverse key order. A node's own value is the shortest key in its subtree, so it is visited after everything beneath it. The original visits it first, which is not reverse key order when one key is a proper prefix of another — and disagrees with the original's own ReverseIterator.
• DeletePrefix reports whether anything matched. Deleting a prefix from an empty tree returns false and wakes nobody. The original returns true and wakes the root's watchers.

Testing

Every read is checked against a differential oracle — a map and a sorted key slice — over seven key corpora chosen to drive different node shapes. Fuzz targets replay operation sequences against that same oracle. A structural invariant check runs after every mutation, so a bad node shape fails at the operation that caused it rather than as a wrong answer much later. Node-kind transitions are walked 0→4→16→48→256 and back down, verified against an oracle at every step in three insertion orders. Watch tests lead with a positive control, because a spurious-wakeup count of zero means nothing until wakeups are known to fire when they should.

go test -race -count=2 ./...
go test -run '^$' -fuzz FuzzTreeOps -fuzztime=10m

License

MIT. See LICENSE.