Concurrent Trees — Junior Level¶

Table of Contents¶

1. Introduction
2. Prerequisites
3. Glossary
4. Core Concepts
5. Why Not Just Use a map?
6. Real-World Analogies
7. Mental Models
8. Pros and Cons
9. Use Cases
10. Code Examples
11. Coding Patterns
12. Clean Code
13. Product Use
14. Error Handling
15. Security Considerations
16. Performance Tips
17. Best Practices
18. Edge Cases and Pitfalls
19. Common Mistakes
20. Common Misconceptions
21. Tricky Points
22. Test
23. Tricky Questions
24. Cheat Sheet
25. Self-Assessment Checklist
26. Summary
27. What You Can Build
28. Further Reading
29. Related Topics
30. Diagrams and Visual Aids

Introduction¶

Focus: "What is a balanced search tree? Why do I need ordering? How do I share one between goroutines without corruption?"

A tree, in this context, is a data structure that stores key–value pairs in sorted key order. Unlike a Go map, which is built on a hash table and offers no ordering guarantee, a tree lets you:

• Look up a specific key in O(log n) time
• Iterate keys in order: from smallest to largest, or within a range like [100, 200]
• Find "the next key greater than k" or "the largest key less than k"
• Stream records in sorted order without holding everything in memory

This second column — ordered operations — is why databases, file systems, search indexes, time-series stores, and almost every persistent storage engine in existence are built on B-trees, B+-trees, or radix trees, not on hash tables.

A concurrent tree is the same structure designed so that multiple goroutines can read and write at the same time without corrupting it. Doing this correctly and fast is one of the deepest problems in systems programming. There are entire PhD theses and decades of academic papers on it. But at the junior level, you only need to learn three things:

1. What a balanced tree looks like (a B-tree in particular, because that is what real Go libraries give you).
2. Why a plain unguarded tree breaks under concurrent writes.
3. The simplest possible way to share a tree between goroutines: put a single sync.Mutex or sync.RWMutex in front of it.

This file teaches those three things, then walks through using github.com/google/btree, the most popular Go in-memory B-tree, with safe concurrent wrappers. By the end you will be able to share an ordered key–value store across goroutines confidently, and you will know exactly why more advanced approaches (hand-over-hand, optimistic, RCU, Bw-trees) exist — even if you have not learned them yet.

You do not need to understand red-black trees, AVL rotations, B+-tree internals, latch crabbing, optimistic concurrency control, RCU, epoch-based reclamation, the Bw-tree, ART, or page eviction. Those are middle, senior, and professional material. This file is about the basics: trees, ordering, locks, and the first real Go library.

Prerequisites¶

• Required: A working Go installation (1.21+ recommended). Run go version to check.
• Required: Comfort with goroutines, go func(), and sync.WaitGroup. See the Goroutines junior file.
• Required: Comfort with sync.Mutex and sync.RWMutex. You should know what Lock(), Unlock(), RLock(), RUnlock() do and why double-locking deadlocks.
• Required: Familiarity with Go's built-in map and slice. You should know that map access is not safe under concurrent writes.
• Helpful: Some exposure to a binary search tree from a CS course. Not required.
• Helpful: Familiarity with go get and Go modules so you can install github.com/google/btree.

Verify the test environment works:

mkdir tree-junior && cd tree-junior
go mod init example.com/tree
go get github.com/google/btree

If go get succeeds and downloads btree, you are ready.

Glossary¶

Core Concepts¶

What does "ordered" mean, and why is it useful?¶

A Go map[int]string lets you do this:

m := map[int]string{1: "a", 7: "g", 3: "c"}
fmt.Println(m[3]) // "c"

But for k, v := range m gives you the keys in random order — and Go intentionally randomizes the iteration order so you do not accidentally rely on it. There is no way to ask "what is the smallest key in this map?" without scanning every entry. There is no way to ask "give me all keys between 3 and 7" without scanning every entry.

A tree gives you all of these:

• "Smallest key" — walk to the leftmost leaf, O(log n).
• "Largest key" — walk to the rightmost leaf, O(log n).
• "All keys in [lo, hi]" — find lo, then walk forward to hi in key order, O(log n + k) where k is the result count.
• "Next key after k" — find k, then take one step right, O(log n).

These are the building blocks of:

• Database indexes (SELECT * WHERE created_at BETWEEN x AND y)
• Time-series storage ("all readings in the last hour")
• Geographic indexes ("all points within this rectangle" — done with multi-dimensional trees like R-trees or BVH)
• Filesystem directory entries sorted by name
• In-memory caches that need to evict the oldest entry
• Auto-complete (find all keys with prefix p)
• Routing tables in networking (longest-prefix match uses a tree)

If you ever want any of those operations, a hash map is not enough.

A binary search tree, drawn¶

The simplest ordered tree is a BST. Each node stores one key and has two children: smaller keys go left, larger go right. To find a key, you walk from the root, comparing at each step.

            50
           /  \
          /    \
        30      70
       /  \    /  \
      20   40 60   80

Find(60): compare 60 to 50 → go right. Compare 60 to 70 → go left. Compare 60 to 60 → found.

In the worst case (a long thin tree), this is O(n). To keep it O(log n), BSTs need balancing — AVL trees, red-black trees, and many other variants. But under concurrent access, balancing is the hardest part: rotating a node touches its parent, both children, and possibly its grandparent simultaneously.

A B-tree, drawn¶

A B-tree generalizes the BST. Instead of one key per node, each node holds many keys (up to some maximum, often called the order) and many children:

                  +-------------------+
                  |  30   60   90     |  (one node, three keys, four children)
                  +-------------------+
                 /     |      |       \
               /       |      |         \
        [10,20] [40,50] [70,80]  [100,110,120]

A Find(70): compare to 30 (greater), to 60 (greater), to 90 (less). Go to the third child. Search inside it. Done.

Why bigger nodes? Two reasons:

1. Cache and disk locality. A node fits in one cache line (or one disk page). Scanning 32 keys inside a single node is much cheaper than chasing 5 pointers through a deep BST, because each pointer chase is a possible cache miss.
2. Lower height. A tree of fanout 64 storing a billion items has height ~5. The same number in a BST has height 30. Five comparisons of cache-resident nodes beats thirty pointer chases hands down.

B-trees are why every database index in the world (Postgres, MySQL's InnoDB, SQLite, Oracle, SQL Server, MongoDB's WiredTiger, BoltDB, BadgerDB, LMDB, ...) is a B-tree or B+-tree variant. They are also why google/btree and tidwall/btree exist as Go libraries: when you want sorted data in memory, you almost always want a B-tree.

What can go wrong under concurrent writes?¶

Imagine two goroutines call Insert(k, v) on the same tree at the same time. Each one:

1. Walks from the root looking for the right leaf.
2. If the leaf has space, inserts the new key there.
3. If the leaf is full, splits it into two leaves and pushes one key up to the parent.
4. If the parent is now full, splits it too. And so on recursively up to the root.

Without any synchronization, two concurrent splits can:

• Both read a parent pointer, then both try to write a new child pointer into the same slot.
• One thread sees a half-finished split where a child has been added but the parent pointer not yet updated, then it walks into a phantom subtree.
• A reader walks down a node that another writer has just freed because it was merged with a sibling.
• The root pointer itself gets overwritten by two threads racing.

The result is silent corruption: lookups return wrong values, range scans skip records or revisit them, the tree's invariants no longer hold, and a future Insert panics with an out-of-bounds slice access because the in-memory layout is no longer consistent.

This is not a theoretical concern. Run a tiny program that spawns 8 goroutines all inserting into an unguarded BST and you will see crashes within milliseconds. The Go race detector (-race) will flag the writes.

The simplest fix: one big lock¶

The first defense, and the one a junior engineer should default to, is a single mutex around the entire tree:

type SafeTree struct {
    mu sync.Mutex
    bt *btree.BTreeG[Item]
}

func (s *SafeTree) Set(it Item) {
    s.mu.Lock()
    defer s.mu.Unlock()
    s.bt.ReplaceOrInsert(it)
}

func (s *SafeTree) Get(key int) (Item, bool) {
    s.mu.Lock()
    defer s.mu.Unlock()
    it, ok := s.bt.Get(Item{Key: key})
    return it, ok
}

This is correct. It is slow if you have hundreds of cores hammering the same tree, but it is far better than a corrupt tree, and for many real workloads — admin panels, configuration services, CLIs, anything below a few thousand QPS — it is plenty.

The middle and senior files teach you how to do better than this. But you should never feel bad about starting here. "A single mutex" is the right answer to most concurrency questions you will ever face professionally, until profiling proves otherwise.

sync.RWMutex: many readers, one writer¶

If your workload is read-heavy (e.g., 99% lookups, 1% inserts), you can do better with sync.RWMutex:

type RWSafeTree struct {
    mu sync.RWMutex
    bt *btree.BTreeG[Item]
}

func (s *RWSafeTree) Get(key int) (Item, bool) {
    s.mu.RLock()
    defer s.mu.RUnlock()
    return s.bt.Get(Item{Key: key})
}

func (s *RWSafeTree) Set(it Item) {
    s.mu.Lock()
    defer s.mu.Unlock()
    s.bt.ReplaceOrInsert(it)
}

Multiple goroutines may hold RLock() at once. As soon as one goroutine calls Lock() for a write, new readers wait and the writer waits for existing readers to finish.

RWMutex is not free: its read path is a bit slower than Mutex, and on heavily contended hot keys it can perform worse. Benchmark first. For the rest of this file we will assume RWMutex is fine.

Why the next level is harder¶

Suppose you have 64 CPU cores and 99%-reader traffic. With RWMutex, all 64 cores can read concurrently — until a writer arrives. Then everything stalls. If writes are 1% of the workload, that is still hundreds of stalls per second.

The next steps are about letting writers and readers overlap safely:

• Hand-over-hand (lock-coupling): lock only the path you are walking, releasing the parent as soon as the child is safely locked.
• Optimistic concurrency: readers do not lock at all; they read, then check a version counter to confirm the data did not change underneath them.
• Copy-on-write (COW): every writer produces a brand-new tree; readers see the old immutable snapshot. Common in google/btree and tidwall/btree.
• RCU: writers replace pointers atomically while readers proceed unaware; old memory is freed only after all readers that could see it have finished.

These are middle, senior, and professional material. For now, return to the safe defaults: one Mutex or one RWMutex, and a real B-tree library.

Why Not Just Use a map?¶

It is fair to ask: when is map[K]V + sync.RWMutex enough? The answer:

• You do not need ordering, range scans, or "next greater key."
• You do not need iteration in sorted order.
• You do not need to maintain insertion order (use slice for that).

If none of those apply, a sync.Map or a guarded map is simpler, faster, and uses less memory than any tree. Reach for a tree the moment you need ordered access. Reach for sync.Map when reads vastly outnumber writes and you do not need ordering.

A quick decision table:

Real-World Analogies¶

A library card catalog. Hash maps are like a bag of cards: you can find one if you have the exact title, but you cannot ask "show me everything starting with M." A tree is the catalog itself — drawers sorted by author, then by title. Range queries are natural; ordering is preserved.

A phone book. Names sorted alphabetically. Finding "Smith" is fast (you flip to the S section, then narrow down). Finding "all names starting with Sm" is also fast. A tree behaves the same way.

The TOC of a giant manual. When you go to a 1000-page reference, you do not scan page 1 to find chapter 7. You look at the table of contents (the top of the tree), find the right section (an internal node), then find the right subsection (a deeper internal node), and only then read the page (a leaf). Each lookup is O(log n).

A locked filing cabinet shared by clerks. The first concurrent version is "only one clerk in the room at a time" — a single mutex. The second is "many clerks can read at once but only one may write" — a reader/writer mutex. The third is "each clerk locks only the drawer they are using" — hand-over-hand locking. The fourth is "each clerk takes a photocopy and writes on that; the original stays untouched" — copy-on-write. Concurrent trees evolve along the same path.

Mental Models¶

Model 1: a tree is a sorted index. Stop thinking of trees as "nodes and pointers" and start thinking of them as a sorted index over your data. Every operation — insert, delete, lookup, range scan, predecessor, successor — is a query on that sorted index. The tree structure is just a way to make those queries fast.

Model 2: a B-tree is a []Page of small sorted arrays glued together by routing keys. Each B-tree node is a sorted array. Internal nodes route you to the right child based on key comparisons. Leaves hold the actual data (in a B+-tree) or all entries (in a B-tree). Insertion that overflows a node splits it; deletion that underflows a node merges it with a sibling.

Model 3: concurrency on a tree is concurrency on a graph. Locking a tree is not like locking a slice. You may need to lock the path you walk, not the whole structure. The hierarchy of locks (root first, then child, then grandchild) matches the structural hierarchy of the tree itself. This is what makes hand-over-hand locking natural.

Model 4: most reads do not need to wait for writes — they need a stable snapshot. Almost all the cleverness in advanced concurrent trees comes from the realization that a reader does not need a fresh, just-written view of the data; it needs a consistent view. Copy-on-write, RCU, and MVCC all give readers a consistent snapshot without making them wait for writers.

Pros and Cons¶

Pros¶

• Ordered access: range scans, predecessor, successor, min, max.
• Predictable performance: O(log n) for all single-key operations, no amortized resize hiccups (a map resizes in O(n)).
• Range-based deletion and iteration are natural.
• Composable with persistent storage: the same B-tree shape works on-disk in BoltDB, BadgerDB, LMDB, SQLite, Postgres.
• Memory locality when fanout is large: a 64-key node uses one or two cache lines.

Cons¶

• More complex than a map. Every operation is recursive and balanced.
• Slower single-key lookups than a hash map when ordering is unnecessary.
• Concurrent versions are hard. A single-lock tree is easy; anything beyond that requires careful protocol design.
• GC pressure if you allocate per-key node objects (a Go-idiomatic B-tree with slice-backed nodes mitigates this).
• Memory overhead from internal nodes that hold only routing keys, not data.

Use Cases¶

• In-memory sorted indexes for a microservice: latest 1000 events by timestamp.
• Range queries in admin tools: "all users created between 2024-01-01 and 2024-06-30."
• Cursor-based pagination that needs WHERE id > last_id ORDER BY id LIMIT 100.
• Auto-complete with prefix scans (using a string key and a B-tree).
• Time-series buffers that accept inserts and stream out in order.
• Priority queues with mutations. A heap is faster for fixed priorities, but a tree lets you Update(key, newPriority) cheaply.
• Schedulers that need "next deadline" in O(log n).

Code Examples¶

Example 1: starting with google/btree¶

github.com/google/btree is the simplest, most idiomatic in-memory B-tree in Go.

package main

import (
    "fmt"

    "github.com/google/btree"
)

type Item struct {
    Key   int
    Value string
}

// Less implements btree.Item via the BTreeG[Item] generic API.
func (a Item) Less(b Item) bool { return a.Key < b.Key }

func main() {
    // Degree 32: each node holds up to 63 items, has up to 64 children.
    tr := btree.NewG[Item](32, func(a, b Item) bool { return a.Less(b) })

    tr.ReplaceOrInsert(Item{Key: 10, Value: "ten"})
    tr.ReplaceOrInsert(Item{Key: 1, Value: "one"})
    tr.ReplaceOrInsert(Item{Key: 5, Value: "five"})

    // Lookup
    if v, ok := tr.Get(Item{Key: 5}); ok {
        fmt.Println("got", v.Value) // got five
    }

    // Ordered iteration
    tr.Ascend(func(it Item) bool {
        fmt.Println(it.Key, it.Value)
        return true
    })
    // 1 one
    // 5 five
    // 10 ten

    // Range scan
    tr.AscendRange(Item{Key: 2}, Item{Key: 10}, func(it Item) bool {
        fmt.Println("in range", it.Key)
        return true
    })
    // in range 5
}

btree.NewG[T] is the generic constructor. The argument 32 is the degree; the package documents it as "minimum degree," which means each non-root node has between degree-1 and 2*degree-1 items. Higher degree means flatter tree, more in-node comparisons, better cache behavior.

This btree.BTreeG is not safe for concurrent writers. Reading the doc carefully: "Write operations are not safe for concurrent mutation by multiple goroutines, but Read operations are." That is a very specific promise: a goroutine that only calls Get, Ascend, etc., does not need to lock — as long as no writer is active. We must enforce that separation with our own locks.

Example 2: wrap it in sync.RWMutex¶

package safetree

import (
    "sync"

    "github.com/google/btree"
)

type Item struct {
    Key   int
    Value string
}

type Tree struct {
    mu sync.RWMutex
    bt *btree.BTreeG[Item]
}

func New(degree int) *Tree {
    return &Tree{
        bt: btree.NewG[Item](degree, func(a, b Item) bool { return a.Key < b.Key }),
    }
}

func (t *Tree) Set(it Item) {
    t.mu.Lock()
    defer t.mu.Unlock()
    t.bt.ReplaceOrInsert(it)
}

func (t *Tree) Get(key int) (Item, bool) {
    t.mu.RLock()
    defer t.mu.RUnlock()
    return t.bt.Get(Item{Key: key})
}

func (t *Tree) Delete(key int) (Item, bool) {
    t.mu.Lock()
    defer t.mu.Unlock()
    return t.bt.Delete(Item{Key: key})
}

func (t *Tree) Len() int {
    t.mu.RLock()
    defer t.mu.RUnlock()
    return t.bt.Len()
}

// Range iterates [lo, hi). The callback returns false to stop early.
// Note: the callback runs WHILE we hold the read lock. Do not call
// back into the tree from it.
func (t *Tree) Range(lo, hi int, fn func(Item) bool) {
    t.mu.RLock()
    defer t.mu.RUnlock()
    t.bt.AscendRange(Item{Key: lo}, Item{Key: hi}, fn)
}

This is the standard, safe, junior-level concurrent tree in Go. It does not scale to dozens of cores under write contention, but it never corrupts, and the read path is genuinely concurrent.

Example 3: a quick benchmark of the safe wrapper¶

package safetree_test

import (
    "math/rand"
    "sync"
    "testing"
)

func BenchmarkTreeReadHeavy(b *testing.B) {
    tr := New(32)
    for i := 0; i < 10_000; i++ {
        tr.Set(Item{Key: i, Value: "x"})
    }
    b.ResetTimer()
    b.RunParallel(func(pb *testing.PB) {
        r := rand.New(rand.NewSource(rand.Int63()))
        for pb.Next() {
            tr.Get(r.Intn(10_000))
        }
    })
}

func BenchmarkTreeMixed(b *testing.B) {
    tr := New(32)
    var wg sync.WaitGroup
    b.ResetTimer()
    b.RunParallel(func(pb *testing.PB) {
        r := rand.New(rand.NewSource(rand.Int63()))
        for pb.Next() {
            k := r.Intn(10_000)
            if r.Intn(10) == 0 {
                tr.Set(Item{Key: k, Value: "x"})
            } else {
                tr.Get(k)
            }
        }
    })
    wg.Wait()
}

Run with:

go test -bench=. -benchmem -cpu=1,2,4,8

You will see the read-heavy benchmark scale roughly linearly until the write benchmark hits the writer-exclusive bottleneck. That gap is exactly what middle-level techniques (hand-over-hand, COW, RCU) aim to close.

Example 4: range scan in a real product¶

A typical use case: an in-memory store of recent log lines, keyed by timestamp, served to a debugging UI:

type LogLine struct {
    TSNanos int64
    Line    string
}

type LogIndex struct {
    mu sync.RWMutex
    bt *btree.BTreeG[LogLine]
}

func NewLogIndex() *LogIndex {
    return &LogIndex{
        bt: btree.NewG[LogLine](64, func(a, b LogLine) bool {
            return a.TSNanos < b.TSNanos
        }),
    }
}

func (li *LogIndex) Append(line string, tsNanos int64) {
    li.mu.Lock()
    defer li.mu.Unlock()
    li.bt.ReplaceOrInsert(LogLine{TSNanos: tsNanos, Line: line})
}

// Tail returns the most recent N lines in chronological order.
func (li *LogIndex) Tail(n int) []LogLine {
    li.mu.RLock()
    defer li.mu.RUnlock()
    out := make([]LogLine, 0, n)
    li.bt.Descend(func(l LogLine) bool {
        out = append(out, l)
        return len(out) < n
    })
    // Reverse for chronological order.
    for i, j := 0, len(out)-1; i < j; i, j = i+1, j-1 {
        out[i], out[j] = out[j], out[i]
    }
    return out
}

// Between returns lines with timestamps in [lo, hi).
func (li *LogIndex) Between(loNanos, hiNanos int64) []LogLine {
    li.mu.RLock()
    defer li.mu.RUnlock()
    var out []LogLine
    li.bt.AscendRange(
        LogLine{TSNanos: loNanos},
        LogLine{TSNanos: hiNanos},
        func(l LogLine) bool { out = append(out, l); return true },
    )
    return out
}

A real implementation would also bound the index size (drop entries older than now - 1h), which a tree handles naturally via AscendLessThan(cutoff, ...) + Delete.

Example 5: tidwall/btree for generic, snapshot-friendly use¶

github.com/tidwall/btree is a competing library with one big extra feature: cheap copy-on-write snapshots.

package main

import (
    "fmt"

    "github.com/tidwall/btree"
)

type Item struct {
    Key   string
    Value int
}

func less(a, b Item) bool { return a.Key < b.Key }

func main() {
    tr := btree.NewBTreeG[Item](less)

    tr.Set(Item{Key: "a", Value: 1})
    tr.Set(Item{Key: "b", Value: 2})

    // O(1) snapshot. Both 'tr' and 'snap' can mutate independently
    // — internal nodes are shared and copied on write.
    snap := tr.Copy()

    tr.Set(Item{Key: "c", Value: 3})

    fmt.Println(tr.Len())   // 3
    fmt.Println(snap.Len()) // 2

    snap.Set(Item{Key: "x", Value: 99})
    if _, ok := tr.Get(Item{Key: "x"}); !ok {
        fmt.Println("tr does not see snapshot mutations")
    }
}

That Copy() returns in O(1) — it just bumps a reference count on the root. The trees diverge as either side writes. This is persistent data structure territory and you will meet it again in the middle and senior files. For now: know it exists, and that for snapshot-heavy workloads tidwall/btree may be a better fit than google/btree.

tidwall/btree also offers btree.BTreeG[T] with a Less function, and a Hint-based fast path for repeated nearby accesses. The package documentation is excellent and worth reading end-to-end before you commit to a choice.

Example 6: detecting the bug yourself¶

To convince yourself you really do need locks, here is a tiny program that breaks a google/btree under concurrent writes:

package main

import (
    "fmt"
    "sync"

    "github.com/google/btree"
)

type Item struct{ K int }

func less(a, b Item) bool { return a.K < b.K }

func main() {
    tr := btree.NewG[Item](16, less)
    var wg sync.WaitGroup
    for w := 0; w < 4; w++ {
        wg.Add(1)
        go func(seed int) {
            defer wg.Done()
            for i := 0; i < 50_000; i++ {
                tr.ReplaceOrInsert(Item{K: seed*100_000 + i})
            }
        }(w)
    }
    wg.Wait()
    fmt.Println("len:", tr.Len()) // often much less than 200_000, or panic
}

Run it under go run -race main.go. The race detector will scream about concurrent writes to the same B-tree nodes. Drop the -race and run it many times — you will see crashes, panics, or wildly wrong Len() values. Wrapping every call in a single sync.Mutex makes the program correct.

Example 7: comparing map+RWMutex to btree+RWMutex for read latency¶

When ordering is not required, a map is strictly faster. The point of using a tree is the ordered operations. Here is a tiny benchmark sketch:

func BenchmarkMapGet(b *testing.B) {
    m := make(map[int]string)
    var mu sync.RWMutex
    for i := 0; i < 10_000; i++ {
        m[i] = "x"
    }
    b.ResetTimer()
    b.RunParallel(func(pb *testing.PB) {
        i := 0
        for pb.Next() {
            mu.RLock()
            _ = m[i%10_000]
            mu.RUnlock()
            i++
        }
    })
}

You will typically see map reads at 2–4x the throughput of btree reads. Trees pay for ordering. Use them when you need it; use a map when you do not.

Example 8: avoid leaking the iteration callback¶

A common junior mistake is to forget that the iteration callback runs while holding the read lock:

// BAD: deadlock waiting to happen.
func (li *LogIndex) PrintAll(fn func(LogLine)) {
    li.mu.RLock()
    defer li.mu.RUnlock()
    li.bt.Ascend(func(l LogLine) bool {
        fn(l)            // user-supplied! Could call back into LogIndex!
        return true
    })
}

If fn calls li.Append(...), the goroutine deadlocks: it is trying to take the write lock while holding the read lock. The fix is either:

1. Collect into a slice under the lock, then call fn outside:

func (li *LogIndex) PrintAll(fn func(LogLine)) {
    li.mu.RLock()
    var snapshot []LogLine
    li.bt.Ascend(func(l LogLine) bool {
        snapshot = append(snapshot, l)
        return true
    })
    li.mu.RUnlock()
    for _, l := range snapshot {
        fn(l)
    }
}

1. Or document loudly that callbacks must not re-enter the tree.

Almost every junior-level bug with concurrent trees is some variant of "I called something inside the lock that took the lock again."

Coding Patterns¶

Pattern 1: one struct, one mutex, all methods take the lock. The simplest concurrent tree exports only methods on a struct. Direct access to the underlying *btree.BTreeG is hidden. This makes the locking discipline a property of the type, not of every caller.

Pattern 2: read methods take RLock, mutation methods take Lock. Be strict. A method that might mutate must take Lock. Conditional logic ("only lock if we are about to write") is a deadlock waiting to happen — use Lock always for mutators.

Pattern 3: return slices from range queries, not iterators. Resist the temptation to return a chan Item or a callback-style iterator. Both surface the lock to the caller. Materialize a []Item under the lock and return it. Pay the allocation; keep the API safe.

Pattern 4: use COW snapshots for read-heavy "long" queries. If a query takes seconds (a full export, a backup, a JSON dump), do not hold the read lock that long — switch to tidwall/btree and Copy() the tree, then dump from the snapshot.

Pattern 5: split the tree by shard for write throughput. A simple, scalable trick: maintain N independent trees keyed by hash(key) % N and have one mutex per shard. Reads to disjoint shards never contend. Writes to disjoint shards never contend. This is "poor man's hand-over-hand," and it works astonishingly well.

type ShardedTree struct {
    shards [16]*Tree
}

func NewSharded() *ShardedTree {
    var s ShardedTree
    for i := range s.shards {
        s.shards[i] = New(32)
    }
    return &s
}

func (s *ShardedTree) shard(k int) *Tree { return s.shards[uint(k)%16] }
func (s *ShardedTree) Set(it Item)        { s.shard(it.Key).Set(it) }
func (s *ShardedTree) Get(k int) (Item, bool) { return s.shard(k).Get(k) }

The downside: range queries that span shards must visit them all and merge. If range queries matter, use one tree.

Clean Code¶

• Name the type after the purpose, not the data structure. LogIndex, EventQueue, RouteTable — not BTreeWrapper.
• Hide the library choice. Do not expose *btree.BTreeG[Item] in your public API. If you later switch from google/btree to tidwall/btree, callers must not have to change.
• Group every lock with a comment explaining the invariant.

// mu protects bt and len.
// Always take mu before reading or writing either field.
mu  sync.RWMutex
bt  *btree.BTreeG[Item]
len int // duplicated for O(1) Len() without lock — wait, no: see Len() below.

• Prefer immutable items. If Item has mutable fields and you mutate one outside the tree, you have invented a race that the tree cannot help you with. Treat items in the tree as immutable; produce a new item to update.
• Define Less once and document it. A subtle bug source: two libraries with slightly different Less semantics on nil items, or Less that is not a strict weak order (e.g., <= instead of <).

Product Use¶

A common shape in real Go services:

• MetricsBuffer — a B-tree of (timestamp, metricID) for a 5-minute sliding window of in-memory observations. Background goroutine evicts entries older than the window. Mutex-protected.
• SessionStore — a B-tree keyed by (userID, sessionID) so all sessions of a user can be enumerated. RWMutex-protected.
• AuditLogTail — a B-tree of recent audit events, served via an admin UI that wants last 1000 or last hour.
• Scheduler — a B-tree keyed by next deadline. Workers Min() it, take the next item, and run.
• OrderBook — a financial trading order book is two B-trees: bids and asks. Hand-over-hand or sharded locking when latency matters.

In every case the rule is the same: start with one mutex and a google/btree. Profile. Only graduate to more advanced techniques once you can prove the lock is your bottleneck.

Error Handling¶

Tree operations rarely fail — they succeed or report "not found." But there are a few error-shaped concerns:

• Get returning a zero value. btree.BTreeG[T].Get returns (T, bool). Always check the bool. A zero-valued Item{Key: 0} looks like a real item.
• Iteration callbacks that panic. A panic inside an Ascend callback unwinds through the tree's iteration code. With google/btree this is safe — but you may still hold the mutex when the panic propagates out of your method, which is fine if you used defer Unlock(). If you forgot defer, the panic permanently locks the tree.
• Out-of-memory. A 10-million-entry tree of Item{Value string} uses several hundred MB. Bound the size or evict.
• Stale iterators. google/btree returns no iterator object — only callbacks — so this is less of a concern than in C++ STL maps. Good.

Security Considerations¶

• Untrusted keys. If the keys come from user input, an attacker may craft inputs designed to cause hash collisions or pathological balancing. A balanced B-tree is robust here (every operation is O(log n) regardless of key distribution), but you should still bound the total number of keys an attacker can insert.
• Range scan as a denial-of-service vector. AscendRange(0, MaxInt) on a 10-million-entry tree under a single read lock will block writers for a long time. Always bound page size in user-facing APIs.
• Sensitive values. If items contain secrets, prefer []byte you can zero after use rather than string (strings cannot be wiped because Go interns / shares them).
• Snapshots and disclosure. A COW snapshot of the tree retains a reference to every key and value visible at snapshot time, preventing them from being GC'd. If those entries contain secrets, the snapshot is also sensitive.

Performance Tips¶

• Choose the right degree. For google/btree, degree 32 to 64 is a good default for in-memory use. Higher degrees flatten the tree (good) but make per-node scans longer (sometimes bad).
• Avoid pointer-heavy item types. A B-tree of Item{Key int; Value string} keeps everything inline. A B-tree of Item{Key int; Value *BigStruct} chases a pointer on every visit.
• Pre-size on bulk load. If you can sort your data first and insert in order, both google/btree and tidwall/btree accept that gracefully and build a compact tree.
• Avoid Len() if you do not need it. It is O(1) in both libraries (they cache the count), but every method call is at minimum a mutex acquisition.
• Avoid creating throwaway items for lookups. tr.Get(Item{Key: 5}) allocates if Item is a large struct. Use a tiny key-only struct or a custom Less that ignores everything except the key.
• Profile before sharding. "Add a mutex per shard" is the most over-applied advice in concurrent Go. Most workloads are not write-bound enough to justify it.

Best Practices¶

• Default to one mutex per tree. Add complexity only if profiling shows the lock is hot.
• Default to RWMutex if reads outnumber writes by 5x or more, Mutex otherwise.
• Never expose the underlying *btree.BTreeG outside its owning type.
• Always validate Less is a strict weak order. Reflexivity (Less(a, a) == false) and asymmetry (Less(a,b) && !Less(b,a)) matter.
• Document the iteration contract: "callback runs while the tree is locked; do not re-enter."
• Run the race detector in CI: go test -race ./....
• Treat tree items as immutable. Replace, do not mutate.
• For high snapshot churn, prefer tidwall/btree. For simple sorted in-memory state, prefer google/btree.

Edge Cases and Pitfalls¶

• Inserting an item that already exists. Both libraries' ReplaceOrInsert / Set overwrite by key. If you want "insert if absent," check with Get first — but doing so without holding the lock between Get and Set races. Do it under one acquisition.
• Deleting during iteration. Most B-tree iterators are not safe against in-flight mutations. Buffer the keys to delete, then delete after the iteration returns.
• Less panics. A Less that does nil pointer dereferences will panic inside the tree, leaving the tree in an unknown state. Make Less total.
• A Min() on an empty tree. Returns the zero value with ok=false in google/btree. Do not forget the ok.
• A tree of float keys with NaN. NaN < NaN is false, so Less is not a strict weak order if you allow NaN. Reject NaN on insert.
• Long-running iteration callbacks. The lock is held the whole time. A 10-second callback blocks all writers for 10 seconds.
• Snapshot fan-out. tidwall/btree.Copy() is cheap, but each unique snapshot retains its diverged subtree. Holding 1000 snapshots costs.

Common Mistakes¶

1. Sharing a google/btree directly between goroutines. It is not safe for concurrent writes. Always wrap.
2. Using RWMutex when writes dominate. The reader/writer machinery is slightly slower than Mutex. If writes are 50% of operations, plain Mutex is faster.
3. Returning a callback iterator that holds the lock. Caller deadlocks the moment they call back into the tree.
4. Forgetting to defer Unlock. A panic mid-method leaves the tree locked forever.
5. Comparing keys with == when you defined a custom Less. They must agree: a == b iff !Less(a,b) && !Less(b,a).
6. Spawning a goroutine inside a method that holds the lock and waiting for it. The goroutine cannot acquire the same lock — deadlock.
7. Assuming Len() is free. It is fast, but it still takes the lock.
8. Storing pointers to items returned from the tree and mutating them. You have mutated the tree's internal state.
9. Using a B-tree when a hash map would do. Slower, more memory, more complex. Use the right tool.
10. Building one tree per request. A tree is meant to live for the process lifetime. Per-request allocation defeats the cache locality.

Common Misconceptions¶

• "B-trees are only for disk." No. They are excellent in-memory structures because they are cache-friendly.
• "A sync.Map is always faster than a tree." No. sync.Map is optimized for "many keys, mostly written once, read many times." It is not faster than a guarded map or tree for general workloads.
• "My read lock means I am safe to mutate the data items." Wrong. The lock guards the tree's structure, not the data inside items. Treat items as immutable.
• "If I use RWMutex everywhere, my reads scale linearly." Only until a writer arrives. Writers force all readers to wait, and all subsequent readers wait too.
• "Copy-on-write is free." It is O(1) per snapshot, but writes after a snapshot are slower (they may have to clone a path).
• "google/btree and tidwall/btree are interchangeable." The APIs are similar; the trade-offs differ. tidwall/btree shines for snapshots; google/btree for raw lookup speed.
• "A balanced tree is always faster than a slice for small N." No. For N < ~50, a sorted slice with binary search is often faster than any tree, especially in cache misses.

Tricky Points¶

• Less total order. Less(a,b) || Less(b,a) || a == b must hold. NaN floats break this.
• Race between snapshot and write. In tidwall/btree, taking Copy() while a writer is mid-Set is safe only if both happen under your own external lock. The library does not provide thread-safety on its own.
• Iteration "stop early" semantics. Ascend(fn) keeps calling fn while it returns true. Returning false stops. Reversing this convention is a bug.
• Min and Max on a single-element tree. Both return the same item. Make sure your callers handle that.
• Empty range queries. AscendRange(5, 5) returns nothing because the range is half-open [5, 5) = {}.
• Modifying the key of an item already in the tree. Even outside the tree, if your Less reads Item.Key, mutating it corrupts ordering. Always remove, mutate, re-insert.

Test¶

package safetree_test

import (
    "sync"
    "testing"

    "example.com/safetree"
)

func TestBasic(t *testing.T) {
    tr := safetree.New(8)
    tr.Set(safetree.Item{Key: 1, Value: "one"})
    tr.Set(safetree.Item{Key: 2, Value: "two"})
    if it, ok := tr.Get(1); !ok || it.Value != "one" {
        t.Fatalf("get(1) = %+v, %v", it, ok)
    }
    if tr.Len() != 2 {
        t.Fatalf("len = %d", tr.Len())
    }
}

func TestRange(t *testing.T) {
    tr := safetree.New(8)
    for i := 0; i < 100; i++ {
        tr.Set(safetree.Item{Key: i})
    }
    var got []int
    tr.Range(10, 20, func(it safetree.Item) bool {
        got = append(got, it.Key)
        return true
    })
    if len(got) != 10 || got[0] != 10 || got[9] != 19 {
        t.Fatalf("range = %v", got)
    }
}

func TestConcurrent(t *testing.T) {
    tr := safetree.New(32)
    var wg sync.WaitGroup
    const writers = 8
    const perWriter = 10_000
    for w := 0; w < writers; w++ {
        wg.Add(1)
        go func(seed int) {
            defer wg.Done()
            for i := 0; i < perWriter; i++ {
                tr.Set(safetree.Item{Key: seed*perWriter + i})
            }
        }(w)
    }
    // Concurrent readers
    for r := 0; r < 4; r++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            for i := 0; i < 50_000; i++ {
                tr.Get(i % 1000)
            }
        }()
    }
    wg.Wait()
    if tr.Len() != writers*perWriter {
        t.Fatalf("len = %d, want %d", tr.Len(), writers*perWriter)
    }
}

Run with go test -race. The test passes only if the wrapper's locks are correct.

Tricky Questions¶

Q1. What does tr.AscendRange(Item{Key: 5}, Item{Key: 5}, ...) return? A. Nothing — AscendRange(lo, hi, ...) is a half-open [lo, hi) interval, so [5,5) is empty.

Q2. If two goroutines both call tr.Set on the same key, who wins? A. The last one to acquire the write lock — both succeed, but only the second's value remains in the tree.

Q3. Is tr.Len() O(1) or O(n)? A. O(1) for both google/btree and tidwall/btree. They cache the count.

Q4. Can two goroutines hold RLock() and both iterate the tree at the same time? A. Yes, that is the whole point of RWMutex. As long as no writer holds Lock, any number of readers may proceed.

Q5. I want "insert if absent." How do I do that race-free? A. Acquire the write lock, then if _, ok := bt.Get(item); !ok { bt.ReplaceOrInsert(item) }, then unlock. A Get followed by a Set under separate lock acquisitions is a race.

Q6. My write throughput is too low — should I switch to a lock-free tree? A. No. First, profile. Then try sharding (multiple trees, one lock each). Then try RWMutex if reads dominate. Then consider COW. Only after all that should you reach for hand-over-hand or RCU.

Q7. Does tidwall/btree.Copy() really run in O(1)? A. Yes — it bumps a reference count on the root node. The cost is paid lazily on the first subsequent write to either tree, which may have to clone one root-to-leaf path.

Q8. Why is google/btree.BTreeG documented as "read operations are safe for concurrent use" but "write operations are not"? Surely a read while a write is in progress is unsafe? A. Yes. The docs mean: reads are safe with reads; writes are not safe with anything else. You still need a RWMutex.

Q9. I have 200 million entries. Is a B-tree the right call? A. For in-memory, yes — but ensure your machine has enough RAM (~100 bytes per entry is a fair rough estimate; multiply). For on-disk, look at BoltDB / BadgerDB / LMDB.

Q10. Should I use a B-tree or a skip list for an in-memory ordered index? A. They are competitive. Skip lists are easier to make concurrent (each node has independent forward pointers). B-trees are more cache-friendly and faster in single-threaded benchmarks. Both are fine choices.

Cheat Sheet¶

Defaults:

Self-Assessment Checklist¶

You are ready to move to middle.md when you can:

• Explain in one sentence what an ordered search tree is.
• Draw a B-tree of degree 3 holding 10 random keys.
• Explain why map + RWMutex is wrong when you need range queries.
• Write a Mutex-protected wrapper around google/btree.
• Decide between Mutex and RWMutex based on read/write ratio.
• Spot the "callback re-enters the tree" deadlock in code review.
• Run go test -race on a concurrent tree test and interpret the output.
• Recognize when sharding will help and when it will not.
• Name three alternatives the middle file will explore.
• Explain why Less must be a strict weak order.

Summary¶

A tree is an ordered key–value store. You reach for one when you need range scans, predecessor / successor queries, or sorted iteration — things a hash map cannot give you. In Go, github.com/google/btree and github.com/tidwall/btree are the two libraries you will almost always pick.

Neither is safe for concurrent writes out of the box. The junior-level fix is the right one for the vast majority of programs: wrap the tree in a struct, put a sync.Mutex (or sync.RWMutex if reads dominate) inside it, and have every method take the lock. Hide the underlying library type, document the iteration contract, and test with go test -race.

From there, advanced techniques — hand-over-hand, optimistic, copy-on-write, RCU, Bw-trees, ART — exist to reduce the time the single lock is held. They are subjects of the middle, senior, and professional files. Master the basics first.

What You Can Build¶

• A real-time in-memory log tail server with range-by-timestamp queries.
• An admin dashboard backed by a sorted in-memory index of user actions.
• A scheduler that runs the next task by deadline.
• A bounded "recent N events" buffer that supports since(timestamp) queries.
• A leader-election helper that orders candidates by priority.
• A simple in-memory key–value store with prefix scan.
• A unit-test fixture that simulates a B-tree-backed index for a database service.

Further Reading¶

• github.com/google/btree — package documentation and source.
• github.com/tidwall/btree — package documentation and README.
• Introduction to Algorithms, CLRS, Chapter 18 (B-Trees).
• Go blog: "Go maps in action" (for the comparison baseline).
• The runtime/proc.go source for how Go schedules many goroutines (helpful context for why "lots of small reads" actually scale).
• The Lehman-Yao 1981 paper Efficient Locking for Concurrent Operations on B-Trees (read at middle level — it is short and lovely).
• The Wikipedia entries on AVL trees, red-black trees, B-trees, B+-trees.

Related Topics¶

• Concurrent Skip List — the other classic ordered concurrent structure.
• LRU Concurrent — caches that need ordered eviction.
• Copy-on-Write — the technique under tidwall/btree.Copy().
• sync.RWMutex — the lock you will pair with the tree.
• Channels — an alternative pattern for serializing access (one goroutine owns the tree, others send requests on a channel).

Diagrams and Visual Aids¶

A B-tree of degree 3 (max 2 keys per node)¶

                  [ 30 | 60 ]
                 /     |    \
                /      |     \
        [10|20]   [40|50]   [70|80]

Each internal node has at most 2 keys and 3 children. Leaves hold values; internal keys are routing markers.

What happens when a leaf overflows¶

Before inserting 25 into [10|20]:

        [ 30 | 60 ]
       /     |    \
  [10|20] [40|50] [70|80]

After:

        [ 20 | 30 | 60 ]            <- 20 pushed up; root may itself split
       /    |    |    \
   [10] [25]  [40|50] [70|80]

Splits propagate upward until a node has room. Concurrent splits without locking corrupt the parent's child array.

Lock ladder (single mutex vs sharded)¶

Single mutex:                 Sharded:
    goroutines                    goroutines
    | | | | |                     | | | | | | | |
       v                          / | | | | | | \
      [MUTEX]              [M0][M1][M2][M3]...[M15]
       |                    |   |   |   |       |
      [TREE]              [T0][T1][T2][T3]...[T15]

The single mutex serializes all access. The sharded layout lets N non-colliding operations proceed in parallel.

Reader/writer lock timing¶

time -->

readers:  R1 ===========>
          R2     ===========>
          R3              =====>
writer:                          W1 ============>
readers:                                          R4 ===>
                                                  R5 ===>

Readers may overlap freely. A writer blocks all subsequent readers (and any in-flight reader must finish before the writer gets the lock). After the writer releases, readers may resume.

Why the next files exist¶

junior:     [one tree] <- [one mutex] <- [all goroutines]
middle:     [one tree] <- [many fine-grained locks one per node]
senior:     [one tree] <- [B-link optimistic + RCU readers]
pro:        [Bw-tree: mapping table + delta chains + epochs]

Each step trades complexity for the ability to let writers and readers overlap.

Appendix A: The BST in detail (the bottom of the rabbit hole)¶

Before B-trees were invented, the standard ordered structure was the binary search tree. Even though you will almost never use a plain BST in production Go (no balancing, terrible cache behaviour, easy to break), understanding one cements all the language you need for everything else.

The data shape¶

type BSTNode struct {
    Key   int
    Value string
    Left  *BSTNode
    Right *BSTNode
}

type BST struct {
    root *BSTNode
}

That is it. A BST is a pointer to a root node, each node holds a key, a value, and two child pointers. The invariant: for every node n, every key in n.Left's subtree is < n.Key, and every key in n.Right's subtree is > n.Key.

Insert¶

func (t *BST) Insert(k int, v string) {
    t.root = insert(t.root, k, v)
}

func insert(n *BSTNode, k int, v string) *BSTNode {
    if n == nil {
        return &BSTNode{Key: k, Value: v}
    }
    switch {
    case k < n.Key:
        n.Left = insert(n.Left, k, v)
    case k > n.Key:
        n.Right = insert(n.Right, k, v)
    default:
        n.Value = v // overwrite on equal key
    }
    return n
}

This is the recursive functional pattern: each call returns a (possibly new) subtree root, and the caller stitches it in. That same shape generalizes to copy-on-write trees in the middle file.

Lookup¶

func (t *BST) Get(k int) (string, bool) {
    for n := t.root; n != nil; {
        switch {
        case k < n.Key:
            n = n.Left
        case k > n.Key:
            n = n.Right
        default:
            return n.Value, true
        }
    }
    return "", false
}

Iterative; faster than recursive lookup because no function-call overhead. Both are O(h) where h is height.

The pathological insert¶

func main() {
    var t BST
    for i := 1; i <= 1_000_000; i++ {
        t.Insert(i, "x") // keys in sorted order
    }
    // The tree is now a 1,000,000-node linked list.
    // Get(1_000_000) takes 1,000,000 comparisons.
}

Inserting in sorted order gives you the worst possible BST: a thin chain. Lookups degrade to O(n). This is why balancing exists.

Why a balanced BST is hard concurrently¶

Balancing involves rotations. A right rotation around x:

Before:                 After:
        x                       y
       / \                     / \
      y   C        =>         A   x
     / \                         / \
    A   B                       B   C

To do this concurrently, you must lock x, y, A, B, C, and x's parent. Many threads doing many rotations simultaneously can interlock and deadlock unless you have a global lock ordering. This is exactly why B-trees beat balanced BSTs in concurrent workloads: each node holds many keys, so splits and merges happen 1/B as often.

Appendix B: The B-tree in detail¶

A B-tree of minimum degree t has:

• Each node holds between t-1 and 2t-1 keys (so each internal node has between t and 2t children).
• All leaves at the same depth.
• Keys within a node are sorted.
• For an internal node with keys k1 < k2 < ... < kn and children c0, c1, ..., cn, every key in c_i is between k_i and k_{i+1}.

This is the textbook definition (CLRS chapter 18). google/btree uses exactly this convention with BTreeG[T] constructed via NewG[T](degree, less).

Walking a B-tree¶

// Pseudocode using a hypothetical exposed Node type.
func find(n *Node, k Item) (Item, bool) {
    // Binary search inside the node for k.
    i := sort.Search(len(n.items), func(i int) bool {
        return !less(n.items[i], k) // first item >= k
    })
    if i < len(n.items) && !less(k, n.items[i]) {
        return n.items[i], true // exact match
    }
    if n.IsLeaf() {
        return Item{}, false
    }
    return find(n.children[i], k)
}

A real B-tree uses linear scan for small nodes (faster than binary search up to ~16 keys because of branch prediction) and binary search above that.

Insertion: top-down split¶

The classic algorithm (CLRS): walk down the tree, and whenever you encounter a full node (2t-1 keys), split it preemptively. That guarantees that when you reach the leaf, the parent has room to absorb a key pushed up.

Before: parent has room. Child is full [a|b|c|d|e].
Insert into parent:
   - Split child into [a|b] and [d|e], pushing c up.
   - Parent now has c and points to the two halves.
   - Recurse into whichever half holds the key.

This is why B-trees never overflow without being noticed: every step down validates the path will accept a split.

Deletion: bottom-up merge¶

Deletion is the tricky one. CLRS describes a single-pass top-down algorithm that ensures every node on the path has at least t keys (more than the minimum), so deleting from a leaf cannot underflow the parent. Production implementations (including google/btree) take various shortcuts because writes are exclusive.

Concurrency on B-trees: the menu¶

You will recognize each of these names again. For now you only need the first three.

Appendix C: Choosing between google/btree and tidwall/btree¶

Both libraries:

• Provide a generic BTreeG[T] with a less func(a, b T) bool.
• Are pure Go, zero external dependencies.
• Have excellent test suites.
• Are not safe for concurrent writes without external locking.

Differences:

A short rule:

• Need ordered map, will lock externally, do not need snapshots. → google/btree.
• Need ordered map with frequent cheap snapshots. → tidwall/btree.
• Need on-disk B+-tree. → bbolt, BadgerDB, or LMDB (out of scope here).

A side-by-side Set/Get/Range benchmark sketch¶

package main

import (
    "fmt"
    "math/rand"
    "testing"

    gbt "github.com/google/btree"
    tbt "github.com/tidwall/btree"
)

type item struct{ k int }

func lessG(a, b item) bool { return a.k < b.k }
func lessT(a, b item) bool { return a.k < b.k }

func BenchmarkGoogleSet(b *testing.B) {
    tr := gbt.NewG[item](32, lessG)
    for i := 0; i < b.N; i++ {
        tr.ReplaceOrInsert(item{k: rand.Int()})
    }
}

func BenchmarkTidwallSet(b *testing.B) {
    tr := tbt.NewBTreeG[item](lessT)
    for i := 0; i < b.N; i++ {
        tr.Set(item{k: rand.Int()})
    }
}

func main() {
    res := testing.Benchmark(BenchmarkGoogleSet)
    fmt.Println("google:", res)
    res = testing.Benchmark(BenchmarkTidwallSet)
    fmt.Println("tidwall:", res)
}

On most hardware in 2025 the two libraries land within 10% of each other on Set. For Get, google/btree is typically slightly ahead. For Copy + diverge, tidwall/btree wins decisively. Always benchmark on your real data.

Appendix D: Five extended examples¶

D.1 In-memory ordered cache with TTL¶

package cache

import (
    "sync"
    "time"

    "github.com/google/btree"
)

type Entry struct {
    Key    string
    Value  any
    Expire time.Time
}

func (e Entry) less(b Entry) bool {
    if !e.Expire.Equal(b.Expire) {
        return e.Expire.Before(b.Expire)
    }
    return e.Key < b.Key
}

// Ordered by expiry so we can sweep the oldest in O(log n + k).
type Cache struct {
    mu    sync.Mutex
    byTTL *btree.BTreeG[Entry]
    byKey map[string]Entry
}

func New() *Cache {
    return &Cache{
        byTTL: btree.NewG[Entry](32, func(a, b Entry) bool { return a.less(b) }),
        byKey: make(map[string]Entry),
    }
}

func (c *Cache) Set(k string, v any, ttl time.Duration) {
    c.mu.Lock()
    defer c.mu.Unlock()
    if old, ok := c.byKey[k]; ok {
        c.byTTL.Delete(old)
    }
    e := Entry{Key: k, Value: v, Expire: time.Now().Add(ttl)}
    c.byKey[k] = e
    c.byTTL.ReplaceOrInsert(e)
}

func (c *Cache) Get(k string) (any, bool) {
    c.mu.Lock()
    defer c.mu.Unlock()
    e, ok := c.byKey[k]
    if !ok || time.Now().After(e.Expire) {
        return nil, false
    }
    return e.Value, true
}

// SweepExpired removes all expired entries. Runs in O(k log n) where k is expired count.
func (c *Cache) SweepExpired(now time.Time) int {
    c.mu.Lock()
    defer c.mu.Unlock()
    var toDelete []Entry
    c.byTTL.AscendLessThan(Entry{Expire: now}, func(e Entry) bool {
        toDelete = append(toDelete, e)
        return true
    })
    for _, e := range toDelete {
        c.byTTL.Delete(e)
        delete(c.byKey, e.Key)
    }
    return len(toDelete)
}

Two indexes — a map[string]Entry for O(1) keyed lookup and a B-tree for ordered eviction — combined under one mutex. This pattern is everywhere: every TTL cache, every priority queue with mutations, every LRU-by-time.

D.2 An audit log with per-tenant scoping¶

package audit

import (
    "sync"

    "github.com/google/btree"
)

type Event struct {
    Tenant string
    Time   int64
    Body   string
}

func less(a, b Event) bool {
    if a.Tenant != b.Tenant {
        return a.Tenant < b.Tenant
    }
    return a.Time < b.Time
}

type Log struct {
    mu sync.RWMutex
    bt *btree.BTreeG[Event]
}

func New() *Log {
    return &Log{bt: btree.NewG[Event](64, less)}
}

func (l *Log) Append(e Event) {
    l.mu.Lock()
    defer l.mu.Unlock()
    l.bt.ReplaceOrInsert(e)
}

// QueryTenant returns events for one tenant between lo and hi (half-open).
func (l *Log) QueryTenant(tenant string, lo, hi int64) []Event {
    l.mu.RLock()
    defer l.mu.RUnlock()
    var out []Event
    l.bt.AscendRange(
        Event{Tenant: tenant, Time: lo},
        Event{Tenant: tenant, Time: hi},
        func(e Event) bool { out = append(out, e); return true },
    )
    return out
}

Composite keys (tenant, time) and the tree's ordered iteration give you per-tenant range scans for free, as long as the comparator puts tenant first. This is the same trick relational databases use with composite indexes.

D.3 A priority queue you can update¶

package pq

import (
    "sync"

    "github.com/google/btree"
)

type Task struct {
    ID       string
    Deadline int64
}

func less(a, b Task) bool {
    if a.Deadline != b.Deadline {
        return a.Deadline < b.Deadline
    }
    return a.ID < b.ID
}

type Queue struct {
    mu sync.Mutex
    bt *btree.BTreeG[Task]
    by map[string]Task // ID -> Task for O(log n) "update by ID"
}

func New() *Queue {
    return &Queue{
        bt: btree.NewG[Task](32, less),
        by: make(map[string]Task),
    }
}

func (q *Queue) Push(t Task) {
    q.mu.Lock()
    defer q.mu.Unlock()
    if old, ok := q.by[t.ID]; ok {
        q.bt.Delete(old)
    }
    q.bt.ReplaceOrInsert(t)
    q.by[t.ID] = t
}

func (q *Queue) PopMin() (Task, bool) {
    q.mu.Lock()
    defer q.mu.Unlock()
    t, ok := q.bt.Min()
    if !ok {
        return Task{}, false
    }
    q.bt.Delete(t)
    delete(q.by, t.ID)
    return t, true
}

func (q *Queue) UpdateDeadline(id string, newDeadline int64) bool {
    q.mu.Lock()
    defer q.mu.Unlock()
    old, ok := q.by[id]
    if !ok {
        return false
    }
    q.bt.Delete(old)
    nt := Task{ID: id, Deadline: newDeadline}
    q.bt.ReplaceOrInsert(nt)
    q.by[id] = nt
    return true
}