tidwall/btree: an ordered map for Go, with hints and copy-on-write

What the package is, and the one job it does

tidwall/btree is described as an efficient B-tree implementation in Go, and the module is minimal to the point of being self-contained. The go.mod declares the module as github.com/tidwall/btree with a Go version of 1.20 and no dependencies at all, which is a meaningful property for a data structure library, because a B-tree is exactly the kind of thing you drop into the bottom of a system and never look at again. The feature list tells you what the author considered worth building. There is support for generics on Go 1.18 and later, Map and Set types for ordered key-value maps and sets, fast bulk loading for pre-ordered data through a Load() method, a Copy() method with copy-on-write support, path hinting as an optimisation for operations with nearby keys, and array-like operations in the style of a counted B-tree. The set of choices says something about the intended use: an ordered container that is cheap to copy, fast to fill from a sorted source, and efficient when you access a moving window of keys.

Four types, two of which are the same idea

The package ships four B-tree types and the README groups them by how much you have to think about them. btree.Map is a fast B-tree for storing ordered key value pairs, and btree.Set is like Map but only for storing keys, so the value half of the pair is simply absent. Those two are the convenience layer, with generics and no comparator to write. btree.BTreeG is a feature-rich B-tree for storing data using a custom comparator, and it is thread-safe. btree.BTree is like BTreeG but uses the interface{} type for data, and it is described as backwards compatible, and it is also thread-safe. So the choice for a new project is between Map or Set if your key type is ordered the way you need, and BTreeG if you need to control the ordering, with BTree there for code that predates generics. The example for BTreeG makes the custom comparator concrete, building two trees over the same items, one sorted by the Key field and one sorted by the Val field, which is the clearest demonstration of why you would want a comparator at all.

The Map surface, including the array-like operations

The Map API is where most usage lands, and it is worth reading as a list of intentions. The basic operations are Set to insert or replace, Get, Delete and Len. The iteration operations are Scan in ascending order, Reverse in descending order, Ascend and Descend which scan only the items greater than or equal to, or less than or equal to, a given key, and Iter which returns a read-only iterator for for-loops. Then there is the part that distinguishes this from a sorted slice, which is the array-like operations, GetAt returning the item at an index and DeleteAt deleting the item at an index. That combination is the reason to use a B-tree here: you get both an ordered view by key and a positional view by index, which a Go map plus a sort gives you only after rebuilding the slice. The usage example is short, creating a map of user identifiers to names, scanning them in order, deleting two, and scanning again.

Path hinting, and the copy-on-write escape

Two of the more unusual features belong to BTreeG rather than to Map. The first is path hinting, which the README lists as an optimisation for operations with nearby keys, and which has its own document, PATH_HINT.md. The idea is that a B-tree walk costs something at every level, and if a caller already knows where the last operation landed, it can hand that path back to the next one and the tree can start nearer the target. The API reflects that with a family of hint-taking methods, SetHint, GetHint, DeleteHint, AscendHint, DescendHint and SeekHint, each of which takes the extra hint argument. The second is copy-on-write, exposed as a Copy() method that copies the B-tree, which is the fast way to take a snapshot of a tree that you are about to mutate heavily without disturbing readers. Both features are opt-in and both cost something in complexity, which is why they live on the feature-rich type rather than on Map.

Bulk loading, and the shape of the repository

The Load() method is the one to reach for when you are inserting a lot of already-sorted data, and the README describes it as fast bulk loading for pre-ordered data, with a Load method on each of the four types, taking a key and a value for Map and a key for Set, and an item for the B-tree types. Filling a B-tree one insert at a time is the classic mistake, and a Load path avoids it. The repository is correspondingly small and legible: btree.go and btreeg.go hold the two B-tree implementations, map.go and set.go hold the convenience types, and each has a matching test file, with PATH_HINT.md alongside. The installation is a single command:

$ go get github.com/tidwall/btree

and the example usage shows the whole surface in one program, a map of users iterated with Scan and then pruned with Delete.

Where the btree package is the wrong tool

Four limits are clear. The first is that if you only need hash lookup, a B-tree is the wrong structure, and Go's built-in map is both faster and simpler. The B-tree earns its keep with ordered iteration, range queries, and the index-like access, and if none of those is in your requirements then you are adding a dependency to do something a map already does. The second is the API surface, which is wide, and the fact that the array-like operations sit next to the key-based ones means it is easy to reach for GetAt on a hot path where the ordered iteration would have been the natural fit. The third is concurrency, and it is a real limit rather than a defect. Only the BTree and BTreeG types are documented as thread-safe, while Map and Set are not described that way, so a Map shared across goroutines needs a lock that you supply and a discipline that is yours to maintain. The fourth is the maintenance signal, and it is the reason to read the source rather than assume. There are no GitHub releases, the go.mod still declares Go 1.20, and the last push was on 2026-09-29, so this is a stable library with an active but unhurried maintainer, not one with a release train behind it.

Editorial conclusion

Adopt tidwall/btree if you need ordered iteration, range scans or an ordered map with a better memory profile than a Go map plus a sort, and you are willing to work with an API that has not changed in years. Do not adopt it if you only need hash lookups, because a map is faster and simpler for that, and do not expect a maintained release stream, since the repository publishes no GitHub releases and the last push was on 2026-09-29. Before you rely on the path hinting optimisation, read PATH_HINT.md, because the hint is stateful and using it wrong can cost you correctness as well as speed.

Frequently asked questions

Official sources

1. Issues
2. License: MIT
3. README
4. tidwall/btree on GitHub