README
¶
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,InsertandDelete, 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:
WalkBackwardsyields 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 ownReverseIterator.DeletePrefixreports whether anything matched. Deleting a prefix from an empty tree returnsfalseand wakes nobody. The original returnstrueand 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.
Documentation
¶
Overview ¶
Package art implements an immutable adaptive radix tree.
The tree is a persistent, copy-on-write map from []byte keys to values, with prefix-based lookups, ordered iteration in both directions, and a watch channel on every node and leaf that fires when the subtree beneath it is modified. Readers need no coordination: a committed tree never changes, so a reader holding one has a stable snapshot for as long as it holds it.
The API deliberately mirrors github.com/hashicorp/go-immutable-radix, which this is a drop-in replacement for, down to the split between CommitOnly and Notify that lets a caller publish a new root before waking any watchers. The difference is underneath: inner nodes come in four sizes and grow and shrink with their child count, rather than every node paying for one shape.
Index ¶
- type Iterator
- type Node
- func (n *Node[T]) Get(k []byte) (T, bool)
- func (n *Node[T]) GetWatch(k []byte) (<-chan struct{}, T, bool)
- func (n *Node[T]) Iterator() *Iterator[T]
- func (n *Node[T]) LongestPrefix(k []byte) ([]byte, T, bool)
- func (n *Node[T]) Maximum() ([]byte, T, bool)
- func (n *Node[T]) Minimum() ([]byte, T, bool)
- func (n *Node[T]) ReverseIterator() *ReverseIterator[T]
- func (n *Node[T]) Walk(fn WalkFn[T])
- func (n *Node[T]) WalkBackwards(fn WalkFn[T])
- func (n *Node[T]) WalkPath(path []byte, fn WalkFn[T])
- func (n *Node[T]) WalkPrefix(prefix []byte, fn WalkFn[T])
- type ReverseIterator
- type Tree
- func (t *Tree[T]) Delete(k []byte) (*Tree[T], T, bool)
- func (t *Tree[T]) DeletePrefix(k []byte) (*Tree[T], bool)
- func (t *Tree[T]) Get(k []byte) (T, bool)
- func (t *Tree[T]) Insert(k []byte, v T) (*Tree[T], T, bool)
- func (t *Tree[T]) Len() int
- func (t *Tree[T]) Root() *Node[T]
- func (t *Tree[T]) Txn() *Txn[T]
- type Txn
- func (t *Txn[T]) Clone() *Txn[T]
- func (t *Txn[T]) Commit() *Tree[T]
- func (t *Txn[T]) CommitOnly() *Tree[T]
- func (t *Txn[T]) Delete(k []byte) (T, bool)
- func (t *Txn[T]) DeletePrefix(prefix []byte) bool
- func (t *Txn[T]) Get(k []byte) (T, bool)
- func (t *Txn[T]) GetWatch(k []byte) (<-chan struct{}, T, bool)
- func (t *Txn[T]) Insert(k []byte, v T) (T, bool)
- func (t *Txn[T]) Notify()
- func (t *Txn[T]) Root() *Node[T]
- func (t *Txn[T]) TrackMutate(track bool)
- type WalkFn
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Iterator ¶
type Iterator[T any] struct { // contains filtered or unexported fields }
Iterator walks a set of nodes in key order.
The traversal stack lives inside the iterator rather than on the heap. A pull iterator has to keep its stack between calls to Next, so the obvious implementation allocates one; at the sizes a prefix scan uses, that single allocation costs more than the entire rest of the scan.
The inline array is indexed, never sliced. Slicing it would make the iterator hold a pointer into itself, which forces escape analysis to give up and heap allocate the whole iterator — measurably worse than simply letting a slice grow.
func (*Iterator[T]) SeekLowerBound ¶
SeekLowerBound seeks the iterator to the smallest key that is greater than or equal to the given key.
There is no watch variant: which nodes a change would have to touch to alter the result is not predictable from the structure the way it is for a prefix.
func (*Iterator[T]) SeekPrefix ¶
SeekPrefix seeks the iterator to a given prefix.
func (*Iterator[T]) SeekPrefixWatch ¶
SeekPrefixWatch seeks the iterator to a given prefix and returns the watch channel of the finest granularity reached.
type Node ¶
type Node[T any] struct { // contains filtered or unexported fields }
Node is an immutable node in the tree.
It is also the common header that every sized node kind embeds as its first field, so a *Node[T] can be converted to the concrete kind it heads with an unsafe pointer cast. That is what lets one pointer type serve both as the public handle for read operations and as the internal, kind-dispatched representation, without an interface — an interface-typed child pointer costs an extra word per child and gives back the memory the sized kinds exist to save.
func (*Node[T]) GetWatch ¶
GetWatch looks up a specific key, returning the watch channel, the value, and whether it was found.
func (*Node[T]) Iterator ¶
Iterator returns an iterator that walks the tree from this node forwards.
The stack is primed here rather than on the first call to Next, so that Next has no "have I started yet" flag to test on every call. Every seek re-primes it, so seeking after construction costs one wasted push and nothing else.
func (*Node[T]) LongestPrefix ¶
LongestPrefix is like Get, but instead of an exact match it returns the longest prefix match.
func (*Node[T]) ReverseIterator ¶
func (n *Node[T]) ReverseIterator() *ReverseIterator[T]
ReverseIterator returns an iterator that walks the tree from this node backwards.
func (*Node[T]) WalkBackwards ¶
WalkBackwards walks the tree in reverse key order.
A node's own value is the shortest key in its subtree, so it is visited after everything beneath it. This differs from the radix tree this replaces, whose WalkBackwards visits a node's value before its children and so does not actually produce reverse key order when one key is a proper prefix of another — a case its own tests never cover, and which its ReverseIterator handles correctly. The order here matches ReverseIterator.
func (*Node[T]) WalkPath ¶
WalkPath walks the tree visiting only nodes from the root down to the given path. Where WalkPrefix walks the entries *under* a prefix, this walks the entries *above* it.
func (*Node[T]) WalkPrefix ¶
WalkPrefix walks the entries under a prefix.
type ReverseIterator ¶
type ReverseIterator[T any] struct { // contains filtered or unexported fields }
ReverseIterator walks a set of nodes in reverse key order.
It carries its traversal stack inline for the same reason Iterator does; see the note there.
The radix tree this replaces tracked which internal nodes had already had their children pushed in a map keyed by node pointer, paying a map insert and a map delete for every internal node walked. Here that state is implicit in the frame that is already on the stack.
func NewReverseIterator ¶
func NewReverseIterator[T any](n *Node[T]) *ReverseIterator[T]
NewReverseIterator returns a new ReverseIterator at a node. The stack is primed here rather than on the first call to Previous, so that Previous has no "have I started yet" flag to test on every call. Every seek re-primes it.
func (*ReverseIterator[T]) Previous ¶
func (ri *ReverseIterator[T]) Previous() ([]byte, T, bool)
Previous returns the previous node in reverse order.
func (*ReverseIterator[T]) SeekPrefix ¶
func (ri *ReverseIterator[T]) SeekPrefix(prefix []byte)
SeekPrefix seeks the iterator to a given prefix.
func (*ReverseIterator[T]) SeekPrefixWatch ¶
func (ri *ReverseIterator[T]) SeekPrefixWatch(prefix []byte) (watch <-chan struct{})
SeekPrefixWatch seeks the iterator to a given prefix and returns the watch channel of the finest granularity reached.
func (*ReverseIterator[T]) SeekReverseLowerBound ¶
func (ri *ReverseIterator[T]) SeekReverseLowerBound(key []byte)
SeekReverseLowerBound seeks the iterator to the largest key that is lower than or equal to the given key.
There is no watch variant: which nodes a change would have to touch to alter the result is not predictable from the structure the way it is for a prefix.
type Tree ¶
type Tree[T any] struct { // contains filtered or unexported fields }
Tree implements an immutable adaptive radix tree. It can be treated as a dictionary abstract data type; the advantages over a hash map are prefix-based lookups and ordered iteration. The immutability means it is safe to read from a Tree concurrently without any coordination.
The zero value is not usable; call New.
func (*Tree[T]) Delete ¶
Delete removes a given key. It returns the new tree, the old value if any, and whether the key was set.
func (*Tree[T]) DeletePrefix ¶
DeletePrefix removes all keys starting with the given prefix. It returns the new tree and whether the prefix matched anything.
func (*Tree[T]) Insert ¶
Insert adds or updates a given key. It returns the new tree, the previous value, and whether one was set.
func (*Tree[T]) Root ¶
Root returns the root node of the tree, which can be used for richer query operations.
type Txn ¶
type Txn[T any] struct { // contains filtered or unexported fields }
Txn is a transaction on the tree. It is applied atomically and returns a new tree when committed. A transaction is not thread safe and should be used by a single goroutine at a time.
func (*Txn[T]) Clone ¶
Clone makes an independent copy of the transaction.
The new transaction does not track any nodes and has TrackMutate turned off. It contains any uncommitted writes made in the original, but further mutations to either are independent and result in different trees on commit. A cloned transaction may be passed to another goroutine and mutated there, though each transaction may only be mutated from one goroutine at a time.
func (*Txn[T]) Commit ¶
Commit finalizes the transaction and returns a new tree. If mutation tracking is on, notifications are issued as well.
func (*Txn[T]) CommitOnly ¶
CommitOnly finalizes the transaction and returns a new tree, without issuing any notifications until Notify is called.
This split is what lets a caller publish the new root before waking any watcher, so a woken watcher never observes the tree it was told had changed in its pre-change state.
func (*Txn[T]) Delete ¶
Delete removes a given key, returning the old value if any and whether the key was set.
func (*Txn[T]) DeletePrefix ¶
DeletePrefix removes an entire subtree matching the prefix, returning whether anything matched.
func (*Txn[T]) GetWatch ¶
GetWatch looks up a specific key, returning the watch channel of the deepest node reached, the value, and whether it was found.
func (*Txn[T]) Insert ¶
Insert adds or updates a given key, returning the previous value and whether one was set.
func (*Txn[T]) Notify ¶
func (t *Txn[T]) Notify()
Notify triggers the notifications recorded under TrackMutate. It must only be called once a transaction has been committed via CommitOnly, and is called automatically by Commit.
func (*Txn[T]) Root ¶
Root returns the current root of the tree within this transaction. The root is not stable across inserts and deletes, but can be used to read the current state during a transaction.
func (*Txn[T]) TrackMutate ¶
TrackMutate toggles whether mutations are tracked. If enabled, notifications are issued for affected internal nodes and leaves when the transaction is committed.
Source Files