go-immutable-radix gives you a sorted key space where every write copies the path
An immutable radix tree implementation in Golang
At a glance
- What is it?
- The iradix package from HashiCorp is a small MPL-2.0 licensed Go library that implements an immutable radix tree, so an insert returns a new tree rather than mutating the old one, and readers never see a partial update. It costs you a copy on write, and it buys ordered iteration, prefix matching and O of k lookups without a hash function.
- Who is it for?
- go-immutable-radix fits a Go service that needs a sorted, prefix-matchable key space and wants readers to keep seeing a consistent snapshot while a writer updates it, for example a routing table or a prefix-keyed configuration. It does not fit a write-heavy workload, since every mutation copies the affected path, and it does not fit a plain key-value lookup where ordering buys nothing.
- Can I use it commercially?
- Yes, with conditions. MPL-2.0 is a weak copyleft licence: you can use it inside commercial and closed-source software, but if you distribute changes to its own files, you must publish those changes under the same licence.
- Is it still maintained?
- Yes. The repository last received commits 10 days ago.
- What is it written in?
- Mainly Go, according to GitHub's language statistics.
Answers come from the project's GitHub data, last synced on October 22, 2026, and from our analysis. They are not legal advice.
Editorial analysis
Every insert returns a new tree and leaves the old one alone
The package is called iradix, and it provides a single Tree implementation, optimized for sparse nodes. The word that matters is immutable, and the example in the README shows what it means in practice.
// Create a tree
r := iradix.New[int]()
r, _, _ = r.Insert([]byte("foo"), 1)
r, _, _ = r.Insert([]byte("bar"), 2)
r, _, _ = r.Insert([]byte("foobar"), 2)The insert does not modify r. It returns a new tree, and the caller reassigns it. The other two return values are the previous value at that key and whether the key was newly created, which is the information you need to implement insert-if-absent or update-if-present semantics without a second lookup.
The consequence is that any goroutine holding the old tree keeps seeing exactly the state it had. There is no lock, no copy-on-write bookkeeping and no read-write mutex in the picture, because the sharing is structural. A writer publishes a new root, and readers that already captured the old root are unaffected.
That is the entire reason to accept the cost of copying. If your workload is read-mostly with occasional whole-snapshot swaps, immutability is nearly free in practice, because the copy is proportional to the size of the changed path rather than the size of the tree. If your workload writes continuously, you are paying for a new tree on every single update, and the README is direct about where to go instead: for a mutable variant, see go-radix.
The library also exposes the root directly, which is how you take a snapshot. Everything read-oriented hangs off r.Root().
O of k lookups, and the argument against hashing
The README states the radix tree properties in a short list, and the first one carries an argument rather than a slogan. As a radix tree it provides O(k) operations. In many cases, this can be faster than a hash table since the hash function is an O(k) operation, and hash tables have very poor cache locality.
That is a specific performance argument about a specific workload, and it is worth taking apart. A hash lookup is not O(1) in practice, it is O(k) for the key length plus a memory access into a table whose entries are scattered across the heap, so every lookup is a cache miss or two. A radix tree walk touches nodes along the key, and those nodes are laid out close to each other, so the traversal is a sequence of cheap, adjacent accesses.
The trade is that the constant factor depends on key shape. Keys that share long prefixes are cheap, keys that are uniformly random are not, and the README's claim about sparse nodes is the tell: the implementation is optimized for a key space where most nodes have few children, which is the opposite of a hash table's uniform bucket distribution.
Two other properties come from the tree structure rather than from the hash comparison, and they are free once you have a radix tree. Minimum and maximum value lookups are available, and iteration is ordered. The first means the extremes of the key space are cheap to find. The second means you can walk the keys in sorted order, which is the feature that a hash map simply cannot provide, and it is the reason the range scan in the README example exists at all.
Transactions exist so a batch of writes does not copy the tree repeatedly
The naive way to use an immutable tree is to call Insert once per key and reassign the root each time. Every one of those calls copies the path from the root to the affected node, so inserting a thousand keys one at a time is a thousand partial copies, and the intermediate trees are thrown away immediately.
The library addresses this directly. A tree supports using a transaction to batch multiple updates, insert and delete, in a more efficient manner than performing each operation one at a time.
This is the standard pattern for persistent data structures and it is worth being concrete about what it buys. Inside a transaction, writes accumulate against an in-progress tree, and the copy work is done once when the transaction commits and the new root is produced. If you are loading a routing table of ten thousand prefixes, the difference between a thousand tree copies and one is the difference between a visible pause and nothing.
The repository layout matches the API. The core tree and node types live in iradix.go and node.go, and edges.go holds the edge structure that a radix tree uses to represent the compressed paths between branch points.
The transactional model also composes with the immutability guarantee in a useful way. A transaction produces a new root, and until you commit it, no reader sees any of it. If a batch of updates fails validation partway through, nothing is published, which is the property you want when the updates come from an untrusted source or from a config file that might be half written.
Ordered iteration is the feature a map cannot give you
The README's second example is a range scan, and it is the clearest demonstration of what the tree buys over a map.
// Create a tree
r := iradix.New[int]()
r, _, _ = r.Insert([]byte("001"), 1)
r, _, _ = r.Insert([]byte("002"), 2)
r, _, _ = r.Insert([]byte("005"), 5)
r, _, _ = r.Insert([]byte("010"), 10)
r, _, _ = r.Insert([]byte("100"), 10)
// Range scan over the keys that sort lexicographically between [003, 050)
it := r.Root().Iterator()
it.SeekLowerBound([]byte("003"))
for key, _, ok := it.Next(); ok; key, _, ok = it.Next() {
if string(key) >= "050" {
break
}
fmt.Println(string(key))
}The iterator starts at an arbitrary lower bound with SeekLowerBound and then walks forward, so a range query is a seek plus a walk, not a scan of the whole key space. That is the difference between O(k) plus the matching range and O(N) over everything.
Prefix matching is the other tree-native operation, and the first example uses it. The root has a LongestPrefix method, and given the key foozip it returns foo, with the remaining bytes and the value. That is the operation you want for a longest-prefix-match router, for a configuration lookup where keys are dotted paths and the most specific match wins, and for any lookup where a partial key should resolve to the closest stored prefix.
The file list shows the iterator family is not just one implementation. There is iter.go for the main iterator, reverse_iter.go for the backwards direction, raw_iter.go for a lower-level walk, and path_iter.go for iterating over paths..
A third operation, minimum and maximum lookup, is the cheapest way to answer questions like what is the first key in the tree, and it is a single descent rather than an iteration.
v2 replaced interface{} with generics
The v2 section of the README is short and it describes the one breaking change that matters. The v2 of go-immutable-radix introduces generics to improve compile-time type safety for users of the package, and the module name for v2 is github.com/hashicorp/go-immutable-radix/v2.
That is a real change for anyone upgrading. The tree in v1 was untyped, and v2 is parameterised, which is why the example reads iradix.New[int]() rather than a bare New(). The value type is now checked at compile time, so a tree holding strings cannot be handed to a function expecting a tree holding integers, and the compiler catches it rather than a type assertion at runtime.
The module path change follows the usual Go semantic import versioning rules, so the two major versions can coexist in one dependency graph, which is what a library used by several HashiCorp products needs.
The dependency list is short and tells you what the library does not do. The go.mod requires go-uuid, golang-lru/v2 and golang.org/x/exp, and nothing else. There is no serialization library, no dependency on a specific hash implementation, and no transitive framework. The LRU cache is notable, because it suggests the implementation keeps some node-level caching, and x/exp is where the Go standard library keeps its experimental packages.
The Go version floor is 1.18, which is the release that introduced generics, so the version constraint and the language feature line up exactly.
MPL-2.0, a small codebase, and a release gap
The licence is MPL-2.0, with the LICENSE file at the repository root and a CHANGELOG.md alongside it. The MPL is a file-level copyleft, so if you modify a file of the library and distribute it, that file carries the obligation, while the rest of your codebase does not. That is a licensing fact rather than legal advice, and for a library you vendor into a service it is usually a workable middle ground.
The codebase is genuinely small, and that is a feature for a data structure. The Go files at the root are edges.go, iradix.go, iter.go, node.go, path_iter.go, raw_iter.go and reverse_iter.go, and there is a.golangci.yml, a.go-version and a GitHub Actions workflow for the CI tests.
The release history is where a reader should slow down. The listed releases are v2.1.0 on 2023-11-21, v2.0.0 on 2022-12-16 and v1.3.1 on 2021-06-28. The last push to the repository was on 2026-10-13, and the repository is not archived with master as the default branch, so the code is still receiving work, but the published versions stopped some time ago.
That combination, a healthy commit stream with a gap in tagged releases, is worth checking before you pin. A project that has not cut a release in a while will not be picked up automatically by a dependency updater, and if you are reading the CHANGELOG to find out what changed since v2.1.0, the answers will be in the commit history rather than in the release notes.
For a data structure this small, the practical risk of drift is low. The larger question is whether the API you depend on is stable, and the v2 generics change is the kind of thing that will not happen again now that the major version is done.
Editorial conclusion
go-immutable-radix fits a Go service that needs a sorted, prefix-matchable key space and wants readers to keep seeing a consistent snapshot while a writer updates it, for example a routing table or a prefix-keyed configuration. It does not fit a write-heavy workload, since every mutation copies the affected path, and it does not fit a plain key-value lookup where ordering buys nothing. Before adopting it, measure the copy cost of your update rate, and if you only need mutability, look at the mutable go-radix variant the README points to rather than paying for immutability you do not use.
Frequently asked questions
What does the iradix package provide?
It provides a single Tree implementation of an immutable radix tree, optimized for sparse nodes, with O of k operations, minimum and maximum value lookups, ordered iteration, longest prefix matching, and a transaction API for batching inserts and deletes more efficiently than one operation at a time.
How do I create a tree and insert keys in go-immutable-radix?
Create it with iradix.New[int]() and reassign the result of each Insert, since the tree is immutable and Insert returns a new tree along with the previous value and whether the key was newly created. The README example inserts foo, bar and foobar and then uses r.Root() to read from the resulting tree.
What is the difference between go-immutable-radix and go-radix?
go-immutable-radix is the immutable variant, where every write returns a new tree, and the README points at go-radix as the mutable variant for cases where you want in-place updates. Using the immutable one means readers keep a consistent snapshot while a writer publishes a new root.
How do I run a range scan over keys in go-immutable-radix?
Get an iterator from the root with r.Root().Iterator(), position it with SeekLowerBound, and then loop on it.Next() until the iterator is exhausted or you break out. The README example scans the keys that sort lexicographically between two bounds and prints them in order.
What changed in version 2 of go-immutable-radix?
The v2 release introduces generics to improve compile-time type safety, so the tree is parameterised by its value type and constructed with iradix.New[int](). The module path for v2 is github.com/hashicorp/go-immutable-radix/v2, and the go.mod requires Go 1.18, the version that introduced generics.
Official sources
Add this badge to your README
If you maintain this project, the badge below links readers to this analysis and shows its maintenance status from the daily GitHub snapshot. Paste the markdown into your README; add ?metric=license or ?metric=stars to the image URL for a different field.
[](https://hysenlabs.com/projects/hashicorp-go-immutable-radix)Was this useful?