Concurrent Trees — Senior Level¶

Table of Contents¶

1. Introduction
2. Prerequisites
3. Glossary
4. Architecture of a Real Concurrent B+-Tree
5. Latching Protocols in Depth
6. The Lehman-Yao B-link Protocol, Implementation Grade
7. MVCC Integration
8. RCU and Epoch-Based Reclamation
9. Immutable Persistent Trees: HAMT and Beyond
10. Engineering Tour: PostgreSQL nbtree, BoltDB, CockroachDB Pebble
11. Coding Patterns
12. Clean Code at Scale
13. Product Use
14. Performance Tips
15. Best Practices
16. Edge Cases and Pitfalls
17. Common Mistakes
18. Common Misconceptions
19. Tricky Points
20. Test
21. Tricky Questions
22. Cheat Sheet
23. Self-Assessment Checklist
24. Summary
25. Further Reading
26. Related Topics
27. Diagrams

Introduction¶

Focus: "I am architecting an in-memory index for a service that handles 100k mixed QPS and must never block readers. What protocol do I run, why, and how do I think about it the way the database engineers do?"

This file is for engineers building or maintaining systems where a tree is a critical shared data structure: an in-memory index inside a database engine, a routing table that must serve millions of lookups per second, the working set of a key-value store. At this level "use one mutex" or even "use publish/subscribe COW" is no longer a default that you reach for blindly — it is one of many options whose trade-offs you weigh against latency budgets, memory budgets, GC budgets, and hardware reality.

We assume you have absorbed the middle file: hand-over-hand, OCC, COW, B-link, sharding, snapshot publishing, version counters. The senior file takes those building blocks and:

• Walks through the architecture of a real concurrent B+-tree the way a database engineer designs one — latching protocols, latch crabbing, S/X/SIX modes, B-link, MVCC.
• Treats the Lehman-Yao 1981 paper at implementation grade: invariants, proof sketches, common variations, in-line Go-flavoured pseudocode.
• Integrates the tree with MVCC: per-key version chains, transaction IDs, garbage collection of dead versions, snapshot isolation correctness.
• Treats RCU and epoch-based reclamation in detail — including why Go's GC means you almost never need an explicit epoch system, and the few cases where you do.
• Surveys immutable persistent trees: Hash Array Mapped Tries (HAMT), finger trees, Bw-trees (briefly; full treatment in professional file), ART.
• Tours the source of three real systems — PostgreSQL nbtree, BoltDB / bbolt, CockroachDB Pebble — and explains how each maps the theory to working code.

By the end of this file you should be able to:

• Architect a concurrent B+-tree from first principles.
• Read PostgreSQL's nbtree.c and nbtxlog.c without confusion.
• Reason about MVCC garbage collection and tombstone half-lives.
• Design epoch reclamation when Go's GC is not enough (e.g., for unsafe.Pointer adjacencies).
• Choose between COW, hand-over-hand, OCC, and B-link given a workload's read/write ratio, snapshot needs, and memory budget.

This is the level at which you stop asking "what library should I use?" and start asking "what protocol does this library run, and is it the right one for me?"

Prerequisites¶

• Fluency with the middle file.
• Familiarity with sync/atomic, atomic.Pointer[T], and the Go memory model.
• Some exposure to database internals (any of: PostgreSQL, MySQL, SQLite, BoltDB).
• Comfortable reading concurrent C or C++ — most published material is in those languages.
• Willingness to read the actual source of tidwall/btree, google/btree, and bbolt.

Glossary¶

Architecture of a Real Concurrent B+-Tree¶

A production-grade in-memory concurrent B+-tree consists of:

1. A node pool / arena. Pre-allocated, cache-aligned nodes; index into the pool is the node ID.
2. A mapping table (optional). Node IDs → node pointers; allows nodes to be "moved" without updating their parents.
3. A root pointer. Atomic; published by the writer when the root changes.
4. Per-node latches. Each node has a single latch (or a reader/writer latch) for protocol coordination.
5. High keys and right-sibling pointers. B-link style; every node has a high key and a right neighbour pointer.
6. A free list or epoch-based reclaimer. Tracks nodes that are no longer reachable but may still be in use by in-flight readers.

The protocol layered on top:

• Reads: descend from root to leaf using latch crabbing or OCC.
• Writes: descend with X-latches in latch crabbing; release X-latches as soon as splits cannot propagate further upward (preemptive split).
• Splits: create a new right sibling, atomically update the parent's child array, release latches.
• Merges: similar but rarer; often deferred (deletion marks tombstones, merge happens later in a vacuum process).

In Go, you would typically simplify some of this:

• Use []Item slices inside each node instead of cache-aligned arrays.
• Use Go's GC instead of a manual reclaimer (no epochs needed).
• Use sync.RWMutex per node instead of custom S/X latches.
• Use atomic.Pointer[Node] for the root.

The result is a simpler, slightly slower implementation than C++, but one that scales to tens of thousands of QPS comfortably.

A Go skeleton¶

package btreeplus

import (
    "sync"
    "sync/atomic"
)

const (
    leafFanout     = 64
    internalFanout = 64
)

type Item struct {
    Key   int64
    Value []byte
}

type Node struct {
    latch     sync.RWMutex
    isLeaf    bool
    items     []Item   // sorted by Key
    children  []*Node  // len(items)+1 if !isLeaf; nil if isLeaf
    highKey   int64
    rightSib  *Node    // only used on leaves in classic B+-tree, or all nodes in B-link
    version   atomic.Uint64 // optional OCC support
}

type Tree struct {
    rootMu sync.Mutex
    root   atomic.Pointer[Node]
}

We will fill in the methods as we work through the protocols.

Latching Protocols in Depth¶

Two-phase latching for inserts (CLRS preemptive splits)¶

Recall the CLRS top-down preemptive-split algorithm:

Insert(key, value):
    1. X-latch the root.
    2. If the root is full, split it (creating a new root above).
    3. node = root
    4. While node is not a leaf:
       a. Identify the child c that the key belongs in.
       b. X-latch c.
       c. If c is full, split it (the result is two children of node).
       d. Update target child to the half containing key.
       e. Release X-latch on node (now safe: node has room for any further split from below).
       f. node = c
    5. node is a leaf with room; insert (key, value).
    6. Release X-latch on node.

Invariant: when we descend into c, c has room. So any future split inside c's subtree cannot propagate up to node. Therefore we can release node.

This pattern holds at most three latches at once (parent, current child, sibling-during-split). Other inserters can be elsewhere in the tree simultaneously.

Latch crabbing for reads¶

For reads, we hold at most two latches at once:

Read(key):
    1. S-latch the root.
    2. node = root.
    3. While node is not a leaf:
       a. Identify child c.
       b. S-latch c.
       c. Release S-latch on node.
       d. node = c.
    4. Binary-search for key in node.items.
    5. Release S-latch on node.

Readers and writers can overlap freely because of the reader/writer latch semantics. But: a writer's X-latch will block readers' S-latches on the same node. Hot pages become bottlenecks.

Optimistic latching for reads (OLFIT)¶

To eliminate the read-side latch entirely:

Read(key):
    1. node = root.
    2. Loop:
       a. v1 = atomic.Load(node.version)
       b. If v1 is odd (writer in flight), spin / yield.
       c. children, items = read node fields (still racy)
       d. v2 = atomic.Load(node.version)
       e. If v2 != v1, restart from step 2.
       f. If leaf, search items and return.
       g. Find child c. node = c. Goto 2.

Writers increment version before and after their modifications:

Write(key, value):
    1. X-latch node.
    2. v = atomic.Add(node.version, 1)  // now odd
    3. Mutate.
    4. atomic.Add(node.version, 1)      // now even
    5. Release X-latch.

In Go this needs all node fields read through atomics for memory model conformance. The race detector will catch the unprotected reads; a real implementation would mark the structure as deliberately racy.

SIX (Shared-with-Intent-Exclusive) for B-tree?¶

SIX modes are rarely used in B-trees because the typical sequence is "read child, write child" or "write child without prior read." A read-then-upgrade pattern is uncommon in tree code. SIX is more common in row-level locking inside databases.

Comparison: when to use which¶

For pure in-memory Go in 2026, COW publish/subscribe with optionally sharded writers is the right architecture for almost every workload. The latch-crabbing protocols matter more in disk-backed systems where pages cannot be cheaply cloned.

The Lehman-Yao B-link Protocol, Implementation Grade¶

The Lehman-Yao 1981 paper, "Efficient Locking for Concurrent Operations on B-Trees," is the foundation of nearly every modern concurrent B-tree, including PostgreSQL's nbtree. Reading it is a rite of passage.

The key idea¶

Concurrent splits create a problem: a reader descends into node N, expecting to find the key. But while the reader is examining N, a writer splits N into N and M, pushing the median up to the parent and adding M as a new child. The reader's target key may now be in M.

Without B-link: the reader must re-acquire the parent's latch and re-traverse. This destroys concurrency.

With B-link: each node has a high key (the largest key reachable through it) and a right-sibling pointer. After a split, N's high key drops and N.rightSib = M. A reader on N checks: "is my target key > N.highKey?" If yes, follow N.rightSib to M. No parent re-latch needed.

The invariant¶

For any node N:

• N.highKey is the largest key reachable through N.
• For every key k > N.highKey that exists in the tree, k is reachable through N.rightSib.

This invariant is maintained by split protocols.

The split protocol in detail¶

When inserting into a leaf L that becomes full:

1. Allocate new leaf M.
2. Move the upper half of L.items into M.
3. Set M.highKey = L.highKey.
4. Set M.rightSib = L.rightSib.
5. Set L.highKey = median key.
6. Set L.rightSib = M. (← this is atomic in C; on Go you do atomic.Pointer.Store(&L.rightSib, M).)
7. Now the parent must be updated to know about M. Walk up:
8. X-latch the parent.
9. Insert the (median key, M) entry into parent.
10. Release parent latch.
11. If the parent split, recurse.

Step 6 is the publication point. After it, in-flight readers on L who see key > L.highKey will follow L.rightSib = M and find their key. The parent's view (the (M, key) entry) is added later.

A reader that arrives at the parent after the parent update will find M through the parent's child array directly. A reader that arrived earlier follows L.rightSib. Both paths converge correctly.

Why it works¶

The crucial property: at no point in the split is any reader's traversal invalidated. Either:

1. The reader's chosen path includes L and M via the parent (post-parent-update).
2. The reader's chosen path includes L, sees key > L.highKey, and follows rightSib to M (pre-parent-update or even concurrently with it).

There is no third path. Both routes succeed.

Pseudocode for a Lehman-Yao B-link Get¶

func (t *Tree) Get(key int64) (Item, bool) {
    n := t.root.Load()
    n.latch.RLock()
    for !n.isLeaf {
        // Follow right-sibling chain if key > highKey.
        for key > n.highKey {
            right := n.rightSib
            right.latch.RLock()
            n.latch.RUnlock()
            n = right
        }
        // Descend to the right child.
        i := childIndex(n, key)
        child := n.children[i]
        child.latch.RLock()
        n.latch.RUnlock()
        n = child
    }
    // n is a leaf; same right-walk as above.
    for key > n.highKey {
        right := n.rightSib
        right.latch.RLock()
        n.latch.RUnlock()
        n = right
    }
    i, found := findInItems(n.items, key)
    if !found {
        n.latch.RUnlock()
        return Item{}, false
    }
    it := n.items[i]
    n.latch.RUnlock()
    return it, true
}

Notice the structural similarity to plain latch crabbing — the extra logic is just the "follow right" loops before the descent.

Pseudocode for a Lehman-Yao B-link Insert¶

func (t *Tree) Insert(key int64, val []byte) {
    n := t.root.Load()
    n.latch.Lock()
    for !n.isLeaf {
        // No need to follow right-sibling on insert; we hold X-latch.
        i := childIndex(n, key)
        child := n.children[i]
        child.latch.Lock()
        n.latch.Unlock()
        n = child
    }
    // n is a leaf. Insert.
    if len(n.items) < leafFanout {
        insertItem(&n.items, key, val)
        n.latch.Unlock()
        return
    }
    // Full. Split.
    m := allocLeaf()
    mid := len(n.items) / 2
    m.items = append(m.items, n.items[mid:]...)
    n.items = n.items[:mid]
    if key >= m.items[0].Key {
        insertItem(&m.items, key, val)
    } else {
        insertItem(&n.items, key, val)
    }
    m.highKey = n.highKey
    m.rightSib = n.rightSib
    n.highKey = m.items[0].Key - 1 // simplification
    n.rightSib = m
    // Now propagate up.
    // (For simplicity assume insert into parent; real code finds parent via a stack.)
    n.latch.Unlock()
    propagateUp(n, m)
}

Real production code tracks the descent path in a stack and propagates splits up from there. The key insight is that the new right sibling is visible to in-flight readers via rightSib before the parent is updated.

Implementation pitfalls¶

• The parent walk must use a stack. Re-traversing from the root to find the parent introduces races with other concurrent splits.
• High keys must be updated atomically with the right-sibling pointer. If a reader sees the new rightSib but the old highKey, they may follow rightSib unnecessarily — usually fine, but check.
• Merges are the hard case. A merge violates the B-link invariant if not done carefully. Most production implementations defer merges (vacuum in PostgreSQL).
• Root growth requires special care. Growing the root means the old root acquires a sibling; you must publish the new root pointer atomically.

Why you almost never implement this in Go¶

Implementing Lehman-Yao correctly is a multi-month project even for experienced engineers. Production implementations have evolved over decades. You should:

• Use tidwall/btree or bbolt and accept their protocol choices.
• Understand B-link well enough to read the source of any tree library and reason about its correctness.
• Reach for B-link only if you are building a database engine.

MVCC Integration¶

A concurrent index alone is not enough for a database. You also need transactional semantics: readers see a consistent snapshot regardless of concurrent writes.

The version chain model¶

Each row in the database has a chain of versions:

key=42:
  v3 -> v2 -> v1 -> nil
  (v3 = latest, v1 = oldest)

Each version has:

type Version struct {
    Value   []byte
    XMin    int64 // transaction ID that created this version
    XMax    int64 // transaction ID that deleted this version (0 = not deleted)
    Next    *Version
}

A reader with transaction ID R:

• Starts a snapshot at time R.
• For each row, walks the version chain until it finds the version with XMin <= R && (XMax == 0 || XMax > R).
• That is the version visible to R.

The B-tree index points to the latest version of each key. The reader, after looking up the key in the index, walks the version chain to find their visible version.

Garbage collection¶

Versions older than the oldest active transaction can be reclaimed:

GC pass:
    oldest_active = min(active transaction IDs)
    for each version chain v3 -> v2 -> v1 -> nil:
        find the first version with XMin <= oldest_active.
        Truncate the chain to that point.

In PostgreSQL this is VACUUM. In MySQL InnoDB it is the purge thread. In CockroachDB it is range GC. The mechanism is the same.

Tombstones in the index¶

A delete creates a new version with XMax set. The B-tree index still points to the version chain (it does not know about deletion). Eventually, GC removes the entire chain; only then is the index entry removed.

Implications for the tree¶

• The tree is concurrent only at the structural level (latches / COW).
• MVCC is layered on top via per-row version chains.
• The tree's role is to find the index entry; the version chain is walked after.

A Go sketch:

type Row struct {
    Key      string
    Versions []Version
    mu       sync.RWMutex
}

type Version struct {
    Value []byte
    XMin  int64
    XMax  int64
}

type Index struct {
    bt *btree.BTreeG[*Row]
}

func (i *Index) Read(key string, txID int64) ([]byte, bool) {
    row, ok := i.bt.Get(&Row{Key: key})
    if !ok {
        return nil, false
    }
    row.mu.RLock()
    defer row.mu.RUnlock()
    for j := len(row.Versions) - 1; j >= 0; j-- {
        v := row.Versions[j]
        if v.XMin <= txID && (v.XMax == 0 || v.XMax > txID) {
            return v.Value, true
        }
    }
    return nil, false
}

func (i *Index) Write(key string, value []byte, txID int64) {
    row, ok := i.bt.Get(&Row{Key: key})
    if !ok {
        row = &Row{Key: key}
        i.bt.ReplaceOrInsert(row)
    }
    row.mu.Lock()
    defer row.mu.Unlock()
    if len(row.Versions) > 0 {
        row.Versions[len(row.Versions)-1].XMax = txID
    }
    row.Versions = append(row.Versions, Version{Value: value, XMin: txID})
}

The tree is one mutex; per-row version chains are their own mutexes. Snapshot reads do not block writers; writers do not block readers (assuming row locks are not contended).

Snapshot isolation correctness¶

The key property: a reader with txID = R sees a consistent view as if the database had no other concurrent transactions running. This is achieved by the version visibility rule above. Each row appears to the reader exactly as it was at time R, regardless of subsequent writes.

Snapshot isolation is not the strongest isolation level (serializable is stronger), but it is what 99% of production OLTP databases offer because the latency cost of serializable is high.

When the tree itself needs MVCC¶

In CockroachDB Pebble, the tree itself stores MVCC entries directly — keys are (userKey, timestamp) pairs, sorted by userKey ascending and timestamp descending. A "get at time T" is a single tree lookup for the largest entry with (userKey, T_or_less). No separate version chain; the tree is the version chain.

This is the cleanest design for an LSM-based MVCC store. For a B-tree-based one, the version-chain-per-row design is more common.

RCU and Epoch-Based Reclamation¶

Read-Copy-Update is the canonical lock-free read pattern in the Linux kernel. Writers swap pointers atomically; readers proceed without locks; old memory is freed only after all in-flight readers finish.

In Go, the garbage collector subsumes most of RCU's mechanics. As long as old pointers are not retained by any goroutine, they will be collected. There is no need for an explicit epoch system.

But there are a few cases where you need explicit reclamation in Go:

1. unsafe.Pointer mixed with type-punning. GC sees only typed pointers; if you cast to uintptr to embed bits, GC will collect the object.
2. sync.Pool of nodes with embedded unsafe.Pointer. If a node returned to the pool is reused while another goroutine still holds a pointer to it, you have use-after-free.
3. Interop with C via cgo. C-allocated memory is not seen by Go's GC.
4. Off-heap allocation (e.g., mmap'd regions). Same as cgo.

For pure Go code with atomic.Pointer[Node] and no unsafe, you do not need epochs.

A toy epoch reclaimer¶

For completeness:

package epoch

import (
    "sync"
    "sync/atomic"
)

type Reclaimer struct {
    epoch  atomic.Int64
    queues []sync.Mutex // per-epoch reclaim queue
    items  [][]any
}

func NewReclaimer() *Reclaimer {
    return &Reclaimer{
        queues: make([]sync.Mutex, 3),
        items:  make([][]any, 3),
    }
}

// Enter is called by a reader at the start of its critical section.
// Returns the epoch the reader is in.
func (r *Reclaimer) Enter() int64 {
    return r.epoch.Load()
}

// Exit signals the reader has left.
func (r *Reclaimer) Exit(epoch int64) {
    // Track per-epoch reader counts via a separate counter.
    // Omitted for brevity.
}

// Retire enqueues an object for reclamation in the current epoch.
func (r *Reclaimer) Retire(obj any) {
    e := r.epoch.Load() % 3
    r.queues[e].Lock()
    r.items[e] = append(r.items[e], obj)
    r.queues[e].Unlock()
}

// Advance moves to the next epoch. Items retired two epochs ago can be freed.
func (r *Reclaimer) Advance() {
    new := r.epoch.Add(1)
    old := (new - 2 + 3) % 3 // 2 epochs back
    r.queues[old].Lock()
    // Wait for all readers in epoch `old` to finish.
    // Then drop items.
    r.items[old] = nil
    r.queues[old].Unlock()
}

The epoch reclaimer works in principle but is fiddly. In Go, prefer:

• atomic.Pointer[T] for publish.
• Plain GC for reclamation.
• sync.Pool only when you can prove no concurrent reader holds the node.

Hazard pointers¶

An alternative to epoch reclamation. Each reader publishes the pointers it currently holds into a per-thread "hazard" array. Writers, before freeing a pointer, check no reader's hazard array contains it.

type HazardSlot struct {
    p atomic.Pointer[Node]
}

var hazards [maxThreads]HazardSlot

func (r *Reader) Read() *Node {
    for {
        p := globalRoot.Load()
        hazards[r.id].p.Store(p)
        // Re-check: did the global root change?
        if globalRoot.Load() != p {
            continue
        }
        return p
    }
}

func (w *Writer) Free(p *Node) {
    // Scan all hazard slots; if none contain p, free.
    for i := 0; i < maxThreads; i++ {
        if hazards[i].p.Load() == p {
            return // someone is reading; defer
        }
    }
    // safe to free
}

Hazard pointers are precise (you know exactly which objects are in use) but have higher per-read overhead than epochs. Used in some lock-free data structure papers; rare in Go (again, GC suffices).

When you do need explicit reclamation in Go¶

If you build a tree where node memory is in an arena (mmap'd region or cgo allocation), Go's GC cannot help. Then you must implement epoch or hazard reclamation manually.

Real example: bbolt uses mmap'd pages, so its readers must hold a "transaction" that is essentially an epoch. Until the transaction is closed, pages it touched are not reclaimed.

Immutable Persistent Trees: HAMT and Beyond¶

For workloads that need cheap snapshots with fully persistent semantics — every version is a first-class value, mutations produce new trees — immutable trees are the right architecture.

Hash Array Mapped Trie (HAMT)¶

The HAMT is the persistent map data structure used in Clojure (PersistentHashMap), Scala (HashMap), and many functional libraries. Key properties:

• O(log_{32} n) for lookup, insert, delete.
• Structural sharing: insert clones a path of O(log_{32} n) nodes.
• Fully persistent: every version is independently usable.
• No tree balancing: hashing distributes keys.

The structure: a tree of fan-out 32, where each node is an array of up to 32 children, and the index at each level is 5 bits of the key's hash.

package hamt

const (
    bitsPerLevel = 5
    fanout       = 1 << bitsPerLevel
    mask         = fanout - 1
)

type Node struct {
    bitmap uint32 // which slots are populated
    slots  []any  // either *Node or *Leaf
}

type Leaf struct {
    Key  uint64
    Hash uint64
    Val  any
    Next *Leaf // for hash collisions
}

func (n *Node) get(hash uint64, level int, key uint64) (any, bool) {
    idx := uint32(hash>>(level*bitsPerLevel)) & mask
    if n.bitmap&(1<<idx) == 0 {
        return nil, false
    }
    pos := bitsBelow(n.bitmap, idx)
    slot := n.slots[pos]
    switch x := slot.(type) {
    case *Node:
        return x.get(hash, level+1, key)
    case *Leaf:
        for x != nil {
            if x.Key == key {
                return x.Val, true
            }
            x = x.Next
        }
    }
    return nil, false
}

func bitsBelow(bitmap, idx uint32) int {
    return popcount(bitmap & ((1 << idx) - 1))
}

func popcount(x uint32) int {
    // ... use math/bits.OnesCount32
}

Insert is similar but allocates a new Node with the slot updated:

func (n *Node) insert(hash uint64, level int, leaf *Leaf) *Node {
    idx := uint32(hash>>(level*bitsPerLevel)) & mask
    pos := bitsBelow(n.bitmap, idx)
    if n.bitmap&(1<<idx) == 0 {
        // Insert new leaf.
        nn := &Node{
            bitmap: n.bitmap | (1 << idx),
            slots:  make([]any, len(n.slots)+1),
        }
        copy(nn.slots[:pos], n.slots[:pos])
        nn.slots[pos] = leaf
        copy(nn.slots[pos+1:], n.slots[pos:])
        return nn
    }
    // Slot occupied. Either descend or split.
    nn := &Node{bitmap: n.bitmap, slots: append([]any{}, n.slots...)}
    switch x := n.slots[pos].(type) {
    case *Node:
        nn.slots[pos] = x.insert(hash, level+1, leaf)
    case *Leaf:
        if x.Hash == leaf.Hash {
            // Hash collision; chain leaves.
            leaf.Next = x
            nn.slots[pos] = leaf
        } else {
            // Promote to subtree.
            sub := &Node{}
            sub = sub.insert(x.Hash, level+1, x)
            sub = sub.insert(leaf.Hash, level+1, leaf)
            nn.slots[pos] = sub
        }
    }
    return nn
}

Insert allocates ~O(log_{32} n) nodes. For a 1B-entry HAMT that is ~6 small allocations per write — comparable to a B-tree COW path-copy.

Why HAMT instead of COW B-tree?¶

• HAMT is unordered (hash-based). For ordered workloads, use a tree.
• HAMT has very flat tree (fanout 32 = depth ~6 for 1B entries); the per-write allocation count is bounded.
• HAMT is fully persistent — every version is usable forever without reference counting.

In Go, HAMT implementations exist (github.com/persistent/data-structures, others). They are less common than in Clojure / Scala because Go's sync.Map and a sync.RWMutex + map cover most use cases.

For an ordered fully persistent tree, the standard choice is a 2-3 finger tree or a balanced BST variant (e.g., a weight-balanced tree). These appear rarely in Go; reach for them only if your workload demands fully persistent ordered data.

Bw-tree (preview)¶

The Bw-tree is the Microsoft Research take on a lock-free B-tree:

• A mapping table maps node IDs to memory pointers.
• Nodes are modified by appending delta records to a linked chain at the node ID.
• The mapping table entry is updated via CAS to point to the new delta head.
• Periodically, a node's delta chain is consolidated into a fresh base node.
• Epoch-based reclamation handles old delta records and consolidated bases.

The result: lock-free reads and writes (only CAS contention on the mapping table). Used in Microsoft Hekaton.

Full treatment in the professional file. For now, recognize it as the apex of in-memory B-tree concurrency design.

Concurrent ART¶

The Adaptive Radix Tree is a radix trie variant whose nodes adapt their size to the number of children. It is highly cache-efficient and supports both point access and range scans.

A concurrent ART (e.g., the implementation in HyPer and DuckDB) uses OLFIT-style optimistic latching with version counters per node, similar to a concurrent B-tree but on a radix trie shape.

Go implementations: github.com/plar/go-adaptive-radix-tree is one; not currently concurrent. If you need concurrent ART in Go, you implement it yourself or use a CGo binding to a C++ library.

For ordered string keys at very high scale, ART beats B-trees on lookup latency. For mixed integer / string keys with range queries, a B-tree is still simpler.

Engineering Tour: PostgreSQL nbtree, BoltDB, CockroachDB Pebble¶

Reading the source of real systems is the best way to internalize this material.

PostgreSQL nbtree¶

src/backend/access/nbtree/ in the PostgreSQL source. Key files:

• nbtree.c — main API.
• nbtinsert.c — insertion with Lehman-Yao splits.
• nbtsearch.c — search with right-sibling chasing.
• nbtxlog.c — write-ahead logging for splits.
• README — the protocol described in English. Read this first.

The protocol is Lehman-Yao with several refinements:

• High keys are stored explicitly in every internal node.
• Right-sibling pointers are stored in every page.
• Splits are atomic with respect to readers: the new right sibling is fully populated and linked before the parent is updated.
• Deletes mark tombstones; merges happen lazily via VACUUM.

The page format uses 8 KB pages aligned to disk. Each page has a header, a sorted array of (key, child pointer) entries, and a special area for the high key and right-sibling pointer.

Read the README. It is one of the best technical documents in any open-source codebase.

BoltDB / bbolt¶

go.etcd.io/bbolt is a pure-Go B+-tree key-value store. Key properties:

• Single writer at a time. A RWTransaction is exclusive.
• Many concurrent readers. Each ReadTransaction sees a consistent snapshot.
• Copy-on-write at page granularity. A modified page is written to a new location; old pages are freed at commit.
• mmap'd file. Reads are direct memory access; no buffer pool.

Key files in bbolt:

• bucket.go — the per-bucket B+-tree.
• node.go — in-memory node representation.
• page.go — on-disk page format.
• tx.go — transaction lifecycle.

The concurrency model: one Update transaction at a time; many View transactions in parallel. Old pages are kept alive until no View transaction can see them — a manual epoch reclamation tied to the txid of the oldest active reader.

Reading bbolt's node.split and tx.Commit gives you a clean picture of how a real production B+-tree implements COW with multi-version reads.

CockroachDB Pebble¶

github.com/cockroachdb/pebble is a Go LSM-tree-based key-value store. It is the storage engine of CockroachDB.

Pebble is LSM, not B-tree, but it embeds a B-tree-flavoured structure: each SSTable is a sorted on-disk file with a small B-tree index on top. The memtable (in-memory writes before they flush to disk) is a concurrent skip list.

Worth reading for:

• How LSM and B-tree concepts interact.
• How the memtable's skip list achieves lock-free reads.
• How range deletes are encoded.
• How MVCC is layered on top (each key is suffixed with a timestamp).

Read internal/arenaskl for the lock-free skip list; read sstable/ for the B-tree-indexed sorted file.

What these systems share¶

• Single-writer or write-mostly-serial. Most systems do not let many writers contend; they either serialize via transactions or shard writes.
• Multi-version reads. Readers see a consistent snapshot regardless of writers.
• Right-sibling pointers. Either Lehman-Yao B-link or LSM range tombstones with similar effect.
• Deferred reclamation. Old versions live until no reader can see them.
• Bulk batching. Writes accumulate and flush together for efficiency.

These are the structural patterns of every production-grade concurrent ordered store. Internalize them.

Coding Patterns¶

Pattern 1: Single writer, lock-free readers.

The most common production pattern. One goroutine (or one transaction at a time) writes; readers see a consistent snapshot.

type Engine struct {
    mu       sync.Mutex
    live     *btree.BTreeG[Item]
    snapshot atomic.Pointer[btree.BTreeG[Item]]
}

Pattern 2: Transactional writes via channel.

For complex multi-step writes, dispatch to a single goroutine:

type WriteCmd struct {
    Op   string
    Item Item
    Done chan error
}

type Engine struct {
    cmds chan WriteCmd
}

func (e *Engine) writer() {
    tr := btree.NewBTreeG[Item](less)
    for cmd := range e.cmds {
        switch cmd.Op {
        case "set":
            tr.Set(cmd.Item)
        case "del":
            tr.Delete(cmd.Item)
        }
        e.publish(tr)
        cmd.Done <- nil
    }
}

Writes are serialized through the channel; readers use the published snapshot. This is the actor model applied to a tree.

Pattern 3: Per-shard publish/subscribe.

For very high throughput, shard the keyspace and use publish/subscribe per shard.

Pattern 4: Version chain on top of a tree.

For MVCC-style reads: the tree stores *Row; each row has a version chain.

Pattern 5: Tombstone + lazy merge.

Deletes leave tombstones in the tree; a background goroutine merges sparse nodes periodically. Writes never block on a merge.

Clean Code at Scale¶

• Encapsulate the protocol. Every protocol-aware piece of code lives behind a single type. Callers never see latches.
• Document invariants. Each method's preconditions and postconditions are commented. "Holds X-latch on node n on entry; releases before return."
• Use named lock types. A wrapped sync.RWMutex named Latch makes the intent clear in code review.
• Test invariants directly. A walkAndVerify function that asserts all tree invariants after each operation. Run it in tests with -tags invariants.
• Avoid global state. Latches, root pointers, mapping tables — all live inside the tree struct, not in package globals.
• Bound retries. OCC retries bounded by a constant; CAS loops bounded; if exhausted, fall through to a global lock.

Product Use¶

• In-memory database engine. Hekaton-style. Bw-tree or OLFIT-style B-tree. Per-row MVCC chains. Snapshot isolation.
• Time-series store. B+-tree of (timestamp, series_id). Lock-free reads via published snapshots. Sharded writes by series ID.
• Range-scan API. Customer-facing pagination by cursor. The tree's Ascend is the engine; the cursor is the snapshot version.
• Routing table for an API gateway. B-tree of route prefixes. Updates from a control plane; reads on every request. COW + atomic publish is the right shape.
• Live dashboards. Read-mostly with periodic writes; publish/subscribe COW.
• Game leaderboards. Updates per game tick; reads per UI refresh. Per-game sharding with snapshot publishing.

Performance Tips¶

• Profile before optimizing. Use runtime/pprof and runtime/trace. The hottest things are rarely what you assumed.
• Watch GC pressure. COW snapshots produce garbage. GOGC and GOMEMLIMIT knobs matter. Profile heap allocations.
• Cache-align nodes. A B-tree node should fit in a small number of cache lines. Padding to 64 bytes can help.
• Avoid pointer-heavy items. Inline values in nodes when possible.
• Batch writes. One snapshot publish per N writes amortizes allocation.
• Pre-allocate node slices. A node's items slice should be pre-sized to the max fanout to avoid append reallocations.
• Tune fanout to your workload. Lower fanout (16) reduces per-write copy cost. Higher (64) reduces tree depth. Benchmark.
• Avoid interface{} items in the tree. Use concrete types via generics.
• Reuse *btree.BTreeG allocations. A sync.Pool of cleared trees can help if you build many short-lived trees.

Best Practices¶

• Choose the simplest protocol that meets your performance budget.
• Default to publish/subscribe COW with tidwall/btree.
• Promote to sharded only with profiling evidence.
• Promote to hand-over-hand or OCC only if you are building a database engine.
• Always test with -race.
• Always benchmark on realistic hardware and realistic workloads.
• Document the protocol's invariants in the type's doc comment.
• Encapsulate the protocol behind a clean API.

Edge Cases and Pitfalls¶

• Reader holding a snapshot indefinitely. Pins memory; old nodes never collected. Bound snapshot lifetimes.
• Writer races to publish. With multiple writer goroutines, you need a mutex around the publish to avoid lost updates.
• GC pauses under heavy COW. A 10ms STW pause can ruin tail latency. Tune GOGC.
• B-link right-sibling on the rightmost node. It is nil; readers must check.
• MVCC garbage accumulation. A long-running transaction prevents version GC. Monitor.
• Tombstone accumulation. Deletes that are never followed by a merge bloat the tree. Periodic VACUUM.

Common Mistakes¶

1. Implementing your own B-link instead of using bbolt or a similar library.
2. Forgetting to release a latch on every code path.
3. Holding the writer mutex during the Copy() (it is cheap but every nanosecond counts).
4. Publishing inside a hot loop without batching.
5. Mixing snapshot reads with live reads in the same query path.
6. Not handling the rightmost-node case in B-link traversal.
7. Garbage-collecting versions still visible to an active transaction.
8. Letting a snapshot leak in a global map.
9. Implementing MVCC version chains as []Version with locked mutation, which becomes the new contention point.
10. Trying to make every operation lock-free when the workload does not need it.

Common Misconceptions¶

• "B-link eliminates all latches." It eliminates parent re-latching on read after a split. Other latches remain.
• "OCC is lock-free." No; writers still take a per-node latch. Readers are lock-free.
• "MVCC is free." No; version chains cost storage and GC effort.
• "COW always wins." COW pays per-write allocation. For write-heavy workloads, hand-over-hand may win.
• "Sharding solves all concurrency." It solves point-access scalability but breaks range queries.
• "You should use a Bw-tree because it is lock-free." Maybe. Bw-trees are extremely complex and bug-prone. Use one only if you genuinely need its properties.

Tricky Points¶

• B-link split visibility. The right sibling pointer must be published before readers can see the parent update. Atomic write order matters.
• MVCC garbage collection horizon. Determining the oldest active transaction is itself a concurrent problem.
• Snapshot reuse. A snapshot acquired by one goroutine and stored in a global may be referenced long after its acquirer is gone. Document lifecycle.
• GC and pinned unsafe.Pointer. A uintptr does not pin the underlying object. Use runtime.KeepAlive if you need it.
• atomic.Pointer[T] after struct embedding. Be careful with field offsets; atomic must be aligned.

Test¶

package btree_test

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

    "github.com/tidwall/btree"
)

type Item struct {
    Key int
    Val int
}

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

type Engine struct {
    mu       sync.Mutex
    live     *btree.BTreeG[Item]
    snapshot atomic.Pointer[btree.BTreeG[Item]]
}

func newEngine() *Engine {
    e := &Engine{live: btree.NewBTreeG[Item](less)}
    e.snapshot.Store(e.live.Copy())
    return e
}

func (e *Engine) Set(it Item) {
    e.mu.Lock()
    defer e.mu.Unlock()
    e.live.Set(it)
    e.snapshot.Store(e.live.Copy())
}

func (e *Engine) Get(k int) (Item, bool) {
    return e.snapshot.Load().Get(Item{Key: k})
}

func TestSnapshotIsolation(t *testing.T) {
    e := newEngine()
    for i := 0; i < 100; i++ {
        e.Set(Item{Key: i, Val: i})
    }
    snap1 := e.snapshot.Load()
    for i := 100; i < 200; i++ {
        e.Set(Item{Key: i, Val: i})
    }
    if snap1.Len() != 100 {
        t.Fatalf("snap1.Len=%d", snap1.Len())
    }
    if e.snapshot.Load().Len() != 200 {
        t.Fatalf("current.Len=%d", e.snapshot.Load().Len())
    }
}

func TestConcurrentReadDuringWrite(t *testing.T) {
    e := newEngine()
    for i := 0; i < 10_000; i++ {
        e.Set(Item{Key: i, Val: i})
    }
    var wg sync.WaitGroup
    // Writer
    wg.Add(1)
    go func() {
        defer wg.Done()
        for i := 10_000; i < 20_000; i++ {
            e.Set(Item{Key: i, Val: i})
        }
    }()
    // Many readers
    for r := 0; r < 8; r++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            for i := 0; i < 20_000; i++ {
                k := rand.Intn(20_000)
                e.Get(k)
            }
        }()
    }
    wg.Wait()
}

Run with go test -race -count=10.

Tricky Questions¶

Q1. Why does Lehman-Yao not need to re-latch the parent on a missed split? A. Because the right-sibling pointer makes the new sibling reachable to in-flight readers without parent involvement.

Q2. In MVCC, how do we know it is safe to garbage collect a version? A. When its XMax is less than the oldest active transaction's snapshot timestamp.

Q3. Why does Go's GC subsume RCU? A. Because GC observes all reachable typed pointers. As soon as a node is unreachable, it is collected. No explicit epoch needed.

Q4. When is an explicit epoch reclaimer necessary in Go? A. When using unsafe.Pointer, cgo, or mmap'd memory that Go's GC does not own.

Q5. What is the worst-case allocation rate of COW for a tree of fanout 32 and 1B entries under continuous writes? A. ~6 nodes per write (height ~6). At 100 KB per node, that is ~600 KB/write. At 10k writes/sec, ~6 GB/sec — too much. In practice nodes are smaller (~1 KB) so 6 KB/write, 60 MB/sec — fine.

Q6. How does PostgreSQL handle B-tree merges? A. It defers them. Deletes mark tombstones; VACUUM merges sparse pages later.

Q7. What is the difference between a B-tree and a B+-tree from a concurrency standpoint? A. B+-tree leaves are linked into a doubly-linked list, enabling efficient range scans without parent involvement. Concurrent splits must also update sibling links.

Q8. Why is the Bw-tree's mapping table key to its design? A. It indirects from node IDs to memory pointers, allowing nodes to be "moved" (consolidated) without updating all parents.

Q9. What makes ART more cache-efficient than a B-tree? A. ART nodes are sized to the actual number of children (4 / 16 / 48 / 256), wasting no memory on empty slots, and traversal indexes directly by key byte.

Q10. What is OLFIT and why does it matter? A. Optimistic Latch-Free Index Traversal. Readers do not take latches; they validate against per-node version counters. Combined with B-link, it achieves lock-free reads on a B-tree.

Cheat Sheet¶

Self-Assessment Checklist¶

• Explain Lehman-Yao B-link in your own words.
• Write the descent loop of a B-link reader.
• Architect an MVCC version-chain layer on top of a concurrent tree.
• Explain why Go's GC subsumes RCU and when it does not.
• Implement a HAMT in Go.
• Read PostgreSQL nbtree's README without confusion.
• Choose between hand-over-hand, OCC, and COW with reasoning.
• Debug a B-tree split race with the help of -race.
• Design a sharded publish/subscribe ordered store.
• Recognize when to reach for ART, Bw-tree, or stick with B-tree.

Summary¶

The senior level is about architecting real systems. The protocols are tools; the architecture is the design. For Go in 2026, the dominant architecture is:

• Publish/subscribe COW with tidwall/btree for in-memory ordered concurrent data.
• bbolt for on-disk single-writer MVCC.
• Pebble for LSM-based large-scale ordered storage.

If you build outside these, you are building a database engine — which is a multi-year project. Read PostgreSQL's nbtree README, BoltDB's source, Pebble's memtable. Internalize Lehman-Yao. Then come back, find the simplest published library that fits your workload, and use it.

The professional file goes further: Bw-trees, concurrent ART, hardware transactional memory, and the inside of Hekaton-class systems.

Further Reading¶

• Lehman, Yao, Efficient Locking for Concurrent Operations on B-Trees (1981).
• Levandoski et al., The Bw-Tree (2013).
• Leis et al., The Adaptive Radix Tree (2013).
• Cha et al., OLFIT (2001).
• Mao et al., MassTree (2012).
• PostgreSQL source: src/backend/access/nbtree/README.
• bbolt source: bucket.go, node.go, tx.go.
• Pebble source: internal/arenaskl/ and sstable/.
• McKenney, Is Parallel Programming Hard? — RCU bible.

Related Topics¶

• Professional file — Bw-trees, concurrent ART, hardware transactional memory.
• MVCC — full treatment of multi-version concurrency.
• Copy-on-Write — broader pattern.
• Concurrent Skip List — alternative ordered structure.

Diagrams¶

Lehman-Yao B-link search¶

target = 75

walk root:
  root.highKey = 1000, key=75 <= highKey, ok.
  child = root.children[1]  (covering [50, 100])
  RLock(child); RUnlock(root)
walk child:
  child.highKey = 90, key=75 <= highKey, ok.
  leaf = child.children[0]  (covering [50, 90])
  RLock(leaf); RUnlock(child)
at leaf:
  leaf.highKey = 80, key=75 <= highKey, found.
return value

If a split had happened concurrently:

at leaf:
  leaf.highKey = 60, key=75 > highKey.
  rightSib = newLeaf
  RLock(rightSib); RUnlock(leaf)
at rightSib:
  rightSib.highKey = 80, key=75 <= highKey, found.

MVCC version chain¶

key=42:
  index_entry -> Row {
    Versions:
      [0] {Value: "a", XMin: 100, XMax: 200}   <- visible to txID in [100, 200)
      [1] {Value: "b", XMin: 200, XMax: 300}   <- visible to txID in [200, 300)
      [2] {Value: "c", XMin: 300, XMax: 0}     <- visible to txID >= 300
  }

reader with txID = 250:
  walk chain, find first version where XMin <= 250 < XMax (or XMax=0).
  v[1] matches: XMin=200, XMax=300. Return "b".

Publish/subscribe COW¶

time -->

writer: Set(it1) Copy() Store(s1)
                       Set(it2) Copy() Store(s2)
                                      Set(it3) Copy() Store(s3)

reader1: Load(s1) ... walks immutable s1 ... done
reader2:          Load(s2) ... walks immutable s2 ... done
reader3:                   Load(s3) ... walks immutable s3 ... done

Each snapshot is reachable until no goroutine retains it, then GC reclaims.

B-tree fanout vs depth¶

fanout: 2   4   8   16   32   64   128
1k:     10   5   4   3    2    2    2
1M:     20  10   7   5    4    4    3
1B:     30  15  10   8    6    5    5
1T:     40  20  14  10    8    7    6

Higher fanout = flatter tree = fewer levels = fewer latch acquisitions = faster.

Appendix A: A complete Lehman-Yao B-link B+-tree skeleton in Go¶

Below is a working (though deliberately small) Lehman-Yao B+-tree of int64 keys to string values. About 250 lines. Read it slowly.

package blink

import (
    "sort"
    "sync"
    "sync/atomic"
)

const fanout = 32

type Node struct {
    latch    sync.RWMutex
    isLeaf   bool
    items    []item            // sorted by Key
    children []*Node           // len(items)+1 if !isLeaf; nil if isLeaf
    highKey  int64             // largest key reachable through this node
    rightSib *Node             // right sibling
    version  atomic.Uint64
}

type item struct {
    Key int64
    Val string
}

type Tree struct {
    rootMu sync.Mutex
    root   atomic.Pointer[Node]
}

func New() *Tree {
    t := &Tree{}
    t.root.Store(&Node{isLeaf: true, highKey: maxInt64})
    return t
}

const maxInt64 = int64(^uint64(0) >> 1)

func findItem(items []item, key int64) (int, bool) {
    lo, hi := 0, len(items)
    for lo < hi {
        mid := int(uint(lo+hi) >> 1)
        if items[mid].Key < key {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    if lo < len(items) && items[lo].Key == key {
        return lo, true
    }
    return lo, false
}

func (t *Tree) Get(key int64) (string, bool) {
    n := t.root.Load()
    n.latch.RLock()
    for !n.isLeaf {
        // Follow right sibling chain if key > highKey.
        for key > n.highKey && n.rightSib != nil {
            next := n.rightSib
            next.latch.RLock()
            n.latch.RUnlock()
            n = next
        }
        i := internalChild(n, key)
        child := n.children[i]
        child.latch.RLock()
        n.latch.RUnlock()
        n = child
    }
    for key > n.highKey && n.rightSib != nil {
        next := n.rightSib
        next.latch.RLock()
        n.latch.RUnlock()
        n = next
    }
    i, found := findItem(n.items, key)
    if !found {
        n.latch.RUnlock()
        return "", false
    }
    v := n.items[i].Val
    n.latch.RUnlock()
    return v, true
}

func internalChild(n *Node, key int64) int {
    // children[i] covers keys <= items[i].Key.
    // Find first items[i].Key >= key.
    i := sort.Search(len(n.items), func(i int) bool {
        return n.items[i].Key >= key
    })
    if i < len(n.items) && n.items[i].Key == key {
        return i + 1
    }
    return i
}

// Set inserts or replaces. Uses simple top-down latching with preemptive splits.
// For brevity, propagation up uses a stack maintained during descent.
func (t *Tree) Set(key int64, val string) {
    t.rootMu.Lock()
    type frame struct {
        node *Node
    }
    var stack []frame
    n := t.root.Load()
    n.latch.Lock()

    // If root is full, grow.
    if len(n.items) == fanout {
        newRoot := &Node{
            isLeaf:   false,
            highKey:  maxInt64,
            children: []*Node{n},
        }
        newRoot.latch.Lock()
        t.root.Store(newRoot)
        splitChildLocked(newRoot, 0)
        n.latch.Unlock()
        n = newRoot
    }
    t.rootMu.Unlock()
    stack = append(stack, frame{n})

    for !n.isLeaf {
        // Follow right-sibling if necessary (in case of concurrent split below).
        for key > n.highKey && n.rightSib != nil {
            right := n.rightSib
            right.latch.Lock()
            n.latch.Unlock()
            n = right
            stack[len(stack)-1] = frame{n}
        }
        i := internalChild(n, key)
        child := n.children[i]
        child.latch.Lock()
        if len(child.items) == fanout {
            splitChildLocked(n, i)
            if key > n.items[i].Key {
                child.latch.Unlock()
                child = n.children[i+1]
                child.latch.Lock()
            }
        }
        n.latch.Unlock()
        n = child
        stack = append(stack, frame{n})
    }

    // n is a leaf with room.
    insertItemSorted(&n.items, key, val)
    if key > n.highKey {
        n.highKey = key
    }
    n.latch.Unlock()
}

// splitChildLocked splits parent.children[i] into two.
// parent must be X-latched; child also X-latched.
func splitChildLocked(parent *Node, i int) {
    child := parent.children[i]
    mid := len(child.items) / 2
    medianKey := child.items[mid].Key
    right := &Node{
        isLeaf:  child.isLeaf,
        highKey: child.highKey,
        rightSib: child.rightSib,
    }
    right.items = append(right.items, child.items[mid:]...)
    if !child.isLeaf {
        right.children = append(right.children, child.children[mid+1:]...)
        child.children = child.children[:mid+1]
    }
    child.items = child.items[:mid]
    child.highKey = medianKey - 1
    child.rightSib = right
    // Insert medianKey into parent.items at i.
    parent.items = append(parent.items, item{})
    copy(parent.items[i+1:], parent.items[i:])
    parent.items[i] = item{Key: medianKey}
    parent.children = append(parent.children, nil)
    copy(parent.children[i+2:], parent.children[i+1:])
    parent.children[i+1] = right
}

func insertItemSorted(items *[]item, key int64, val string) {
    s := *items
    i := sort.Search(len(s), func(i int) bool { return s[i].Key >= key })
    if i < len(s) && s[i].Key == key {
        s[i].Val = val
        return
    }
    s = append(s, item{})
    copy(s[i+1:], s[i:])
    s[i] = item{Key: key, Val: val}
    *items = s
}

What this skeleton illustrates:

• Per-node latches.
• Right-sibling chasing in Get.
• Preemptive splits on the way down (write path).
• High keys updated atomically with right-sibling pointers.

Not shown (left as exercises):

• Deletes and merges.
• Range iteration via leaf linked list.
• Stack-based parent recovery for B-link writes (this skeleton avoids it by re-locking the root for each operation, which is a simplification).
• B-link writes that fully exploit the right-sibling protocol (rather than re-locking the root).

Read this carefully, run it under -race with a stress test, and you have a working B-link tree.

Appendix B: A worked MVCC reader/writer¶

Here is a full MVCC store with snapshot isolation in Go.

package mvcc

import (
    "sync"
    "sync/atomic"

    "github.com/tidwall/btree"
)

type Version struct {
    Value string
    XMin  int64
    XMax  int64
    Next  *Version // older versions
}

type Row struct {
    Key      string
    Newest   *Version // atomic.Pointer would be better; mutex is simpler
    mu       sync.RWMutex
}

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

type Store struct {
    mu       sync.Mutex
    bt       *btree.BTreeG[*Row]
    snapshot atomic.Pointer[btree.BTreeG[*Row]]
    txCounter atomic.Int64
}

func New() *Store {
    s := &Store{bt: btree.NewBTreeG[*Row](less)}
    s.snapshot.Store(s.bt.Copy())
    return s
}

// Begin returns a new transaction ID.
func (s *Store) Begin() int64 {
    return s.txCounter.Add(1)
}

// Write inserts a new version of (key, value) for transaction txID.
func (s *Store) Write(key, value string, txID int64) {
    s.mu.Lock()
    defer s.mu.Unlock()
    row, ok := s.bt.Get(&Row{Key: key})
    if !ok {
        row = &Row{Key: key}
        s.bt.Set(row)
    }
    row.mu.Lock()
    if row.Newest != nil {
        row.Newest.XMax = txID
    }
    row.Newest = &Version{Value: value, XMin: txID, XMax: 0, Next: row.Newest}
    row.mu.Unlock()
    s.snapshot.Store(s.bt.Copy())
}

// Read returns the value visible at transaction txID.
func (s *Store) Read(key string, txID int64) (string, bool) {
    snap := s.snapshot.Load()
    row, ok := snap.Get(&Row{Key: key})
    if !ok {
        return "", false
    }
    row.mu.RLock()
    defer row.mu.RUnlock()
    for v := row.Newest; v != nil; v = v.Next {
        if v.XMin <= txID && (v.XMax == 0 || v.XMax > txID) {
            return v.Value, true
        }
    }
    return "", false
}

// GC removes versions older than minActive (smallest active transaction's snapshot ID).
func (s *Store) GC(minActive int64) {
    s.mu.Lock()
    defer s.mu.Unlock()
    s.bt.Scan(func(row *Row) bool {
        row.mu.Lock()
        for v := row.Newest; v != nil && v.Next != nil; v = v.Next {
            if v.Next.XMax != 0 && v.Next.XMax < minActive {
                v.Next = nil
                break
            }
        }
        row.mu.Unlock()
        return true
    })
}