trie: a path-compressed Go trie for prefix and fuzzy search

Path compression is the idea worth knowing

trie is described as a generic Go trie, a prefix tree, for fast prefix and fuzzy string searching, optimized for memory efficiency and minimal allocations.

The optimisation is stated in one sentence and it is the whole design. The tree is path-compressed, so single-child chains collapse into one node holding a whole string segment rather than a character.

A classic trie allocates a node per character, which means a key such as a long URL costs a node per character, and a trie of a few hundred thousand long strings is a few million allocations. Path compression changes the shape: the common prefix is still shared, but the tail of a key becomes one node with a string in it. The README gives the consequence directly, a trie of long keys with few branch points stays small.

The other property stated in the same paragraph is concurrency. All exported methods are safe for concurrent use, which means a trie can be shared between goroutines without a lock on the caller's side.

The package is versioned as a major version three module, so the import path carries the version suffix, and the module declares a minimum Go version of 1.26, which the README notes is what the toolchain will accept.

It is a small library with a narrow job, and the narrowness is the point: one data structure, done carefully, with a generic value type so you are not forced into a string to string map.

Creating a trie and adding keys

The type parameter decides what is stored alongside each key.

import "github.com/derekparker/trie/v3"

t := trie.New[int]()

The README is clear that the type parameter can be anything, including a struct or any if you want to store heterogeneous values.

Adding a key takes the value to associate with it.

t.Add("foobar", 1)

Two edge cases are documented, and they are the kind of detail that saves a debugging session. Re-adding an existing key updates its value without growing the trie, so you do not need to check for existence first. And adding the empty string is a no-op that returns nil.

That second behaviour connects to the test files in the repository, where one is named for the empty prefix and another for the node value accessor, which suggests the author wrote tests for exactly these corners.

Removing a key is a single call.

t.Remove("foobar")

The API surface is small enough to hold in your head, which is the other reason this library is pleasant to use: there is no builder, no configuration and no options struct, because the design decisions are fixed at the type level.

Lookup, prefix search and the cheap existence test

Finding a key returns the node, and the value comes from the node.

node, ok := t.Find("foobar")
if ok {
    value := node.Val() // 1
}

The two value return is the Go convention for a lookup that can fail, and it is worth noting what Find does not do. It is an exact match, so it will not report foobar as a hit for foo. If you want the prefix behaviour, that is a different call.

Prefix search returns every key beginning with the prefix.

t.PrefixSearch("foo") // ["foobar", ...]

And there is a separate method for the case where you only care whether anything matches, without building the slice of results.

t.HasKeysWithPrefix("foo")

That distinction is a real design decision rather than a convenience. A membership test that returns a boolean does not allocate the result set, which matters when the caller is on a hot path and the prefix is short enough to match a large number of keys. The README frames it as a fast test for whether any key has a prefix, without collecting the matches.

For enumeration there are two more methods. Keys returns every key currently stored, and AllKeyValues returns every key with its value as a map, which is the shape you want when you are serialising the whole trie or handing it to another system.

Fuzzy search and the ordering rule

Fuzzy search returns every key containing the pattern's runes in order, not necessarily adjacent, and the README is explicit that the result set is sorted shortest-first with ties broken lexicographically.

t.FuzzySearch("fb") // matches "foobar"

So fb matches foobar because the f comes before the b and both are present, even though they are not side by side. That is a subsequence match rather than a substring match, and it is a considerably broader query than the name might suggest.

The ordering is a deliberate contract rather than an accident of the implementation, and it has a practical consequence. If you are looking for the closest match to a typed prefix, the shortest candidate is usually the one the user meant, so sorting shortest-first is a reasonable default. But if you are presenting all matches to a user, the ordering is fixed by the library rather than by any similarity score, and there is no ranking by edit distance or by position of the match.

That is the boundary of this library. It answers prefix and subsequence questions quickly and cheaply. It does not do relevance ranking, and it is not a substitute for a full text search engine if that is what you are building.

Iterators, and the locking caveat that comes with them

Each search has a lazy counterpart that yields results as it finds them rather than building a slice, and the README says these are worth reaching for when the result set is large or when you plan to stop early.

for key, value := range t.PrefixSearchIter("foo") {
    fmt.Println(key, value)
}

for key := range t.FuzzySearchIter("fb") {
    fmt.Println(key)
}

for key, value := range t.AllKeyValuesIter() {
    fmt.Println(key, value)
}

Unlike the eager variants, the iterators do not sort, and keys are yielded in the order they are found. That is the price of laziness, and it is usually the right trade when you are going to break out of the loop early.

The caveat is set in bold in the README and it is the one thing to get right here. The iterators hold the trie's read lock for the duration of the iteration, not just while the iterator is constructed. Calling Add or Remove on the same trie from inside the loop self-deadlocks. You have to break out of the loop first, or use the eager variants, which return a snapshot you can iterate freely.

That is a real trap in an otherwise pleasant API, because the deadlock happens in a program that looks correct. The eager versions are not deprecated, they are the right choice whenever the loop body might touch the trie, and the difference in cost is a slice allocation that the lazy version exists to avoid.

Testing, the race detector and a benchmark with a hidden dependency

The contributing section asks you to fork the repository and run the tests with the race detector enabled.

	go test -race

The README explains why that flag matters: several tests exist specifically to catch data races and deadlocks, and they pass trivially without it. Given that the library claims all exported methods are safe for concurrent use, and that the iterators hold a read lock across their whole duration, that is exactly the kind of claim that needs a race detector to verify.

The benchmarks have their own instruction, with memory statistics enabled.

	go test -bench=. -benchmem

And then there is the detail that will bite anyone who runs the benchmarks on a machine that is not set up like the author's. The build and prefix-search benchmarks read a system dictionary file of about 236 thousand entries rather than the small fixture file in the repository, and they abort the benchmark run outright on a machine that lacks that file.

So the benchmarks are not hermetic. They depend on a word list that most Linux desktops have and most containers do not, and the failure mode is an aborted run rather than a skipped test. That is worth knowing before you conclude something is wrong with your checkout.

The workflow the README asks for is otherwise conventional: create a feature branch, write your tests and your code, and open a pull request.

Versions, layout and what to check first

The release tags are v3.2.1 from 2025-10-15, v3.2.0 from 2025-09-02 and v3.1.0 from 2025-08-20, and the last push was on 2026-10-16. The default branch is the v3 branch, which matches the major version in the module path.

The repository is small, which is appropriate for a single data structure. The implementation is in one file, trie.go, and the tests are split across several files at the root, one for the general behaviour, one for regressions, one for the empty prefix case and one for the node value accessor. There is a fixtures directory with the small test file the benchmarks prefer not to use, and a module file and a licence file.

That layout is worth reading as a signal. The implementation is in a single file, which means you can read the whole thing in an afternoon, and the test files are named after the behaviours they protect, which tells you what the author considered worth pinning down.

Three checks before you depend on it.

The Go version. The module declares 1.26, and the README says that is the minimum the toolchain will accept, so an older Go will refuse to build it rather than degrade.

The locking rule, if you intend to use the iterators. Mutating the trie inside an iteration self-deadlocks, and the eager variants are the safe choice whenever the loop body might touch the trie.

And the shape of your queries. If you need relevance ranked full text search, this library is not that, and pairing it with a real search engine is a bigger design decision than the API suggests.

Editorial conclusion

trie suits a Go service that needs prefix lookups over a large set of string keys, from an autocomplete endpoint to a routing table, because the path compression keeps the structure small and the generic value type means you are not writing a second copy of it for your payload. It is the wrong choice if you need full text search rather than prefix or subsequence matching, since fuzzy search here is a rune containment test and not a relevance ranked query, and the wrong choice if your keys are short and few, where a map and a sort will do. Verify first that your minimum Go version is new enough for the module declaration, that you never mutate the trie inside an iterator loop because that self-deadlocks, and that the machine running the benchmarks has the dictionary file the benchmark suite expects.

Frequently asked questions

Official sources

1. derekparker/trie on GitHub
2. Issues
3. License: MIT
4. README
5. Releases