Concurrent Trees — Professional Level¶

Table of Contents¶

1. Introduction
2. Prerequisites
3. Glossary
4. The Bw-Tree in Implementation Depth
5. Concurrent ART (Adaptive Radix Tree)
6. Hardware Transactional Memory (Intel TSX, ARMv8.1 LSE)
7. OLFIT and MassTree in Depth
8. Hekaton-Class In-Memory Engines
9. Comparative Engine Tour
10. Hardware-Aware Tree Design
11. Profiling at the Microbenchmark Level
12. Coding Patterns
13. Clean Code at Engine Scale
14. Product Use
15. Performance Tips
16. Best Practices
17. Edge Cases and Pitfalls
18. Common Mistakes
19. Common Misconceptions
20. Tricky Points
21. Tricky Questions
22. Test
23. Cheat Sheet
24. Self-Assessment Checklist
25. Summary
26. Further Reading
27. Related Topics
28. Diagrams

Introduction¶

Focus: "I am building or maintaining an in-memory engine where every nanosecond and cache line counts. The advanced literature is now my baseline."

This file is for the very small set of engineers who design, implement, or maintain in-memory database engines, in-process columnar stores, or research-grade ordered data structures. By "very small" we mean: at most a few hundred working engineers worldwide. The techniques here are not appropriate for general-purpose Go services — they are the apex of what is possible in concurrent ordered data, and applying them in the wrong context yields complex, buggy code that runs no faster than tidwall/btree with publish/subscribe COW.

We assume you have absorbed the junior, middle, and senior files. The professional file takes you deeper into:

• The Bw-tree (Microsoft Research, 2013): mapping tables, delta chains, consolidation, epoch reclamation, structure modifications. A lock-free B-tree at full implementation grade.
• Concurrent ART (Adaptive Radix Tree): byte-indexed adaptive nodes, prefix compression, optimistic concurrency, SIMD-accelerated lookups.
• Hardware transactional memory (Intel TSX, ARMv8.1 LSE): how xbegin/xend can replace fine-grained latches for short critical sections.
• OLFIT and MassTree: B-link with full OCC, used in HyPer, Hekaton, MassTree itself.
• Hekaton internals: Microsoft's in-memory engine for SQL Server. How it integrates Bw-tree, MVCC, and transaction logging.
• A comparative tour: PostgreSQL nbtree, MySQL InnoDB, Oracle TimesTen, SAP HANA, MS SQL Server Hekaton, Google Spanner. What each one's tree looks like and why.
• Hardware-aware design: cache lines, prefetch, branch prediction, NUMA effects, persistent memory.
• Microbenchmarking discipline: how to measure correctly at the nanosecond scale.

You leave this file able to read any paper in the area, debate trade-offs with database engineers, and architect engines at the bleeding edge of what is possible.

A caveat: almost none of this matters for ordinary Go services. If you are building a payments backend, a CRUD API, a SaaS dashboard, you do not need this material. You need the publish/subscribe COW pattern from the middle file. The professional file is for the case where that pattern is not enough — which is rare.

Prerequisites¶

• All previous files in this section.
• Fluency with C / C++. The published literature is in those languages.
• Familiarity with hardware concepts: cache lines, memory hierarchy, branch prediction, NUMA, prefetching.
• Familiarity with at least one database engine's source.
• Patience to read research papers carefully.

Glossary¶

The Bw-Tree in Implementation Depth¶

The Bw-tree is one of the most fascinating data structures in computer science. Read the original paper (Levandoski, Lomet, Sengupta, 2013) carefully; this section is commentary, not a substitute.

The big picture¶

A standard B+-tree mutates nodes in place. A Bw-tree never mutates a node in place. Instead:

1. Each node has an identifier (a NodeID, typically 32 or 64 bits).
2. A global mapping table maps NodeID → memory pointer to the node's current state.
3. To modify a node, allocate a new delta record (e.g., "insert key K with value V"), link it to the current state, then CAS the mapping table entry to the delta head.
4. Readers walk the delta chain plus the base node when they look up a key.
5. When a delta chain gets long, consolidate: allocate a fresh base node that represents the chain's combined effect, then CAS the mapping table entry.
6. Structure modifications (split, merge) are special delta records that change the tree's topology.

The combined effect: lock-free reads, lock-free writes (just CAS on the mapping table), no in-place mutation. Ideal for flash storage and high-concurrency CPUs.

The mapping table¶

type MappingTable struct {
    entries []atomic.Pointer[Node]
}

func (mt *MappingTable) Get(id NodeID) *Node {
    return mt.entries[id].Load()
}

func (mt *MappingTable) CAS(id NodeID, old, new *Node) bool {
    return mt.entries[id].CompareAndSwap(old, new)
}

The table is the single source of truth for which physical node corresponds to a logical node ID. Updates always go through CAS on the table.

Why the indirection? Because the alternative — every parent pointing directly to a child's memory pointer — means moving a child requires updating every parent. With the mapping table, a child can be "moved" (consolidated) without touching any parents: just CAS the table entry.

Delta records¶

A delta record is a small struct describing an incremental change:

type DeltaKind int

const (
    DeltaInsert DeltaKind = iota
    DeltaDelete
    DeltaUpdate
    DeltaSplit
    DeltaMerge
    DeltaRemoveNode
)

type Delta struct {
    Kind    DeltaKind
    Key     int64
    Value   []byte
    Next    *Node    // the next state (delta or base)
    // For Split/Merge:
    SiblingID NodeID
    Pivot     int64
}

type Node struct {
    IsDelta bool
    // If !IsDelta, this is a base node with items.
    Items   []item
    HighKey int64
    RightSib NodeID
    // If IsDelta:
    Delta *Delta
}

Reading a key from a Bw-tree:

func (t *BwTree) Get(key int64) ([]byte, bool) {
    id := t.rootID
    for {
        n := t.mapping.Get(id)
        if found, val := walkDeltaChain(n, key); found {
            return val, true
        }
        // Need to descend to a child. Walk the chain to find the right child ID.
        childID := findChild(n, key)
        if childID == 0 {
            return nil, false
        }
        id = childID
    }
}

func walkDeltaChain(n *Node, key int64) (bool, []byte) {
    for n.IsDelta {
        d := n.Delta
        switch d.Kind {
        case DeltaInsert:
            if d.Key == key {
                return true, d.Value
            }
        case DeltaDelete:
            if d.Key == key {
                return false, nil // tombstoned
            }
        }
        n = d.Next
    }
    // Reached the base.
    return findInBase(n, key)
}

For each key lookup, the reader walks the delta chain and combines its effect with the base. This is more work per read than a B-tree, but writes are lock-free.

Writes¶

func (t *BwTree) Insert(key int64, value []byte) {
    id := findLeaf(t, key) // descends to the leaf, returns its NodeID
    for {
        old := t.mapping.Get(id)
        delta := &Node{
            IsDelta: true,
            Delta: &Delta{Kind: DeltaInsert, Key: key, Value: value, Next: old},
        }
        if t.mapping.CAS(id, old, delta) {
            return
        }
        // Someone else updated; retry.
    }
}

The write allocates a delta record, links it to the current state, and CASs the mapping table entry. If the CAS fails (another thread won), retry.

Multiple writers can succeed against different node IDs; they only contend on the same leaf.

Consolidation¶

When the delta chain reaches a threshold length (say, 8 records), the next reader to encounter it triggers consolidation:

func (t *BwTree) maybeConsolidate(id NodeID, n *Node) *Node {
    chainLen := lengthOfChain(n)
    if chainLen < consolidationThreshold {
        return n
    }
    fresh := consolidate(n)
    if t.mapping.CAS(id, n, fresh) {
        // We own the old chain; epoch-retire it.
        t.epoch.Retire(n)
        return fresh
    }
    // Someone else consolidated first. Use their version.
    return t.mapping.Get(id)
}

func consolidate(n *Node) *Node {
    items := walkChainToItems(n)
    return &Node{Items: items, HighKey: n.HighKey, RightSib: n.RightSib}
}

Consolidation:

• Walks the chain, applying inserts / deletes / updates to a fresh items slice.
• Allocates a new base node.
• CASs the mapping table to point to it.
• Retires the old chain to an epoch reclaimer.

If two threads try to consolidate simultaneously, only one's CAS succeeds; the other's work is wasted (but the chain is now consolidated by the winner).

Splits and merges¶

Structure modifications are also delta records, with extra fields:

type Delta struct {
    Kind    DeltaKind
    // For DeltaSplit:
    Pivot   int64
    SiblingID NodeID
    Next    *Node
}

A split:

1. Allocate the new right sibling. Install it in the mapping table with a fresh NodeID.
2. The new sibling's content: the upper half of the splitting node's items.
3. Atomically post a SplitDelta to the splitting node: "items >= Pivot now live in SiblingID."
4. Readers seeing the SplitDelta know: "if the key >= Pivot, go to SiblingID."
5. Eventually, post the new sibling to the parent via another delta record.

This is the same architectural idea as Lehman-Yao's right-sibling pointer, but expressed entirely as deltas and CAS operations — no latches required.

Epoch reclamation¶

The Bw-tree must ensure that old base nodes and delta records are not freed while in-flight readers may still see them. This is exactly the RCU problem.

Each reader enters an epoch on every operation:

type Epoch struct {
    counter atomic.Int64
    queues  []sync.Mutex
    items   [][]any
}

func (e *Epoch) Enter() int64 {
    return e.counter.Load()
}

func (e *Epoch) Exit(epoch int64) {
    // Decrement active count for this epoch. Real impl uses per-thread counters.
}

func (e *Epoch) Retire(obj any) {
    cur := e.counter.Load()
    e.queues[cur%3].Lock()
    e.items[cur%3] = append(e.items[cur%3], obj)
    e.queues[cur%3].Unlock()
}

func (e *Epoch) Advance() {
    new := e.counter.Add(1)
    // Wait for all readers in epoch (new-2) to finish.
    // Then free items from queue (new-2)%3.
}

Real Bw-tree implementations use sophisticated epoch trackers (per-thread counters, lock-free queues). Microsoft's implementation is open-sourced in their BzTree research code.

In Go, the GC subsumes most of this. As long as no goroutine retains a pointer to the old chain, it is collected. You only need explicit epoch tracking if you use unsafe.Pointer or cgo.

Why Bw-trees are hard¶

The Bw-tree's correctness depends on:

• Each delta record being atomically published via CAS.
• Consolidation never losing data (must correctly fold the entire chain).
• Splits being seen by all readers in the right order.
• Epoch reclamation freeing only truly unreachable memory.

Bugs in any of these can be silent and very hard to reproduce. Microsoft's original Bw-tree had known correctness bugs that took years to fix. The 2013 paper has been revised multiple times.

For Go, the realistic stance: understand the Bw-tree's protocol, but do not implement one from scratch. If you need its properties, use a library or fork the Microsoft reference code via cgo.

A Go skeleton¶

For pedagogical completeness, a minimal Bw-tree skeleton in Go:

package bwtree

import (
    "sync"
    "sync/atomic"
)

type NodeID uint32

type Node struct {
    isDelta  bool
    isLeaf   bool
    // Base node fields:
    items    []item
    highKey  int64
    rightSib NodeID
    // Delta fields:
    deltaKind DeltaKind
    deltaKey  int64
    deltaVal  []byte
    deltaNext *Node
    // Split delta:
    splitPivot   int64
    splitSibling NodeID
}

type item struct {
    Key int64
    Val []byte
}

type DeltaKind int

const (
    DKInsert DeltaKind = iota
    DKDelete
    DKSplit
)

type BwTree struct {
    mu      sync.Mutex // protects allocation of node IDs
    mapping []atomic.Pointer[Node]
    rootID  NodeID
    nextID  atomic.Uint32
}

func New() *BwTree {
    t := &BwTree{}
    t.mapping = make([]atomic.Pointer[Node], 1<<16)
    root := &Node{isLeaf: true, highKey: 1<<62}
    rootID := NodeID(t.nextID.Add(1))
    t.mapping[rootID].Store(root)
    t.rootID = rootID
    return t
}

func (t *BwTree) Get(key int64) ([]byte, bool) {
    id := t.rootID
    for {
        n := t.mapping[id].Load()
        if found, val, deleted := walkChain(n, key); deleted {
            return nil, false
        } else if found {
            return val, true
        }
        // Walk down to a child.
        leaf, childID := findLeafOrChild(t, n, key)
        if leaf {
            return nil, false
        }
        id = childID
    }
}

func walkChain(n *Node, key int64) (found bool, val []byte, deleted bool) {
    for n.isDelta {
        switch n.deltaKind {
        case DKInsert:
            if n.deltaKey == key {
                return true, n.deltaVal, false
            }
        case DKDelete:
            if n.deltaKey == key {
                return false, nil, true
            }
        case DKSplit:
            if key >= n.splitPivot {
                // Caller must descend into splitSibling.
                return false, nil, false
            }
        }
        n = n.deltaNext
    }
    // Base.
    for _, it := range n.items {
        if it.Key == key {
            return true, it.Val, false
        }
    }
    return false, nil, false
}

func (t *BwTree) Insert(key int64, val []byte) {
    id := findLeafID(t, key)
    for {
        old := t.mapping[id].Load()
        delta := &Node{
            isDelta:   true,
            deltaKind: DKInsert,
            deltaKey:  key,
            deltaVal:  val,
            deltaNext: old,
        }
        if t.mapping[id].CompareAndSwap(old, delta) {
            return
        }
    }
}

This sketch elides:

• Consolidation.
• Splits and merges.
• Epoch reclamation.
• Mapping table growth.
• Concurrent mapping table resizing.

A complete implementation is 5000+ lines of careful Go. Read the paper before attempting it.

When (rarely) to consider a Bw-tree in Go¶

You should consider a Bw-tree if:

• You are building an in-memory database engine.
• Your CAS rate on a single hot node exceeds what tidwall/btree can sustain (millions per second).
• You can afford the implementation cost and the testing budget.

In every other case, publish/subscribe COW is the answer.

Concurrent ART (Adaptive Radix Tree)¶

ART is a radix trie variant where each node adapts its size to the number of children:

• Node4: up to 4 children. Two arrays of 4 bytes (keys) and 4 pointers (children). Linear scan.
• Node16: up to 16 children. Same shape, sized 16. Linear scan or SIMD comparison.
• Node48: up to 48 children. A 256-byte index array mapping each possible byte to a slot in a 48-pointer array, plus the array.
• Node256: 256 children, direct indexing. One pointer per possible byte.

A trie's traversal indexes by key byte, so finding the child at level L is O(1) in a Node256 and O(log 16) (binary search or SIMD) in smaller nodes.

For concurrency, ART uses OLFIT (Optimistic Latch-Free Index Traversal): per-node version counters; readers validate; writers latch one node at a time.

Layout¶

type NodeKind uint8

const (
    Node4 NodeKind = iota
    Node16
    Node48
    Node256
    Leaf
)

type Node struct {
    kind     NodeKind
    version  atomic.Uint64
    writeMu  sync.Mutex
    prefix   []byte
    numChildren uint16
    // ... shape-specific fields
}

type Node4Body struct {
    keys     [4]byte
    children [4]*Node
}

type Node16Body struct {
    keys     [16]byte
    children [16]*Node
}

type Node48Body struct {
    indices  [256]uint8 // 0xff = empty
    children [48]*Node
}

type Node256Body struct {
    children [256]*Node
}

type LeafBody struct {
    key   []byte
    value []byte
}

Real implementations pack the body inline via tagged pointers; in Go we would use a struct with kind discriminator and interface dispatch (with allocation tradeoffs).

Lookup¶

func (t *ART) Get(key []byte) ([]byte, bool) {
    for retries := 0; retries < 64; retries++ {
        n := t.root.Load()
        depth := 0
    walk:
        for {
            if n.kind == Leaf {
                if bytesEqual(n.leafKey(), key) {
                    return n.leafValue(), true
                }
                return nil, false
            }
            v1 := n.version.Load()
            if v1&1 == 1 {
                runtime.Gosched()
                break walk
            }
            if !matchPrefix(n.prefix, key, depth) {
                if n.version.Load() != v1 {
                    break walk
                }
                return nil, false
            }
            depth += len(n.prefix)
            if depth >= len(key) {
                if n.version.Load() != v1 {
                    break walk
                }
                return nil, false
            }
            child := findChild(n, key[depth])
            if child == nil {
                if n.version.Load() != v1 {
                    break walk
                }
                return nil, false
            }
            if n.version.Load() != v1 {
                break walk
            }
            n = child
            depth++
        }
    }
    panic("too many retries")
}

The pattern is the same as OCC B-tree: read fields, validate version, restart on conflict.

Adaptive resizing¶

When a Node4 fills up, it is replaced by a Node16. When a Node16 fills, Node48. When a Node48 fills, Node256. When a node shrinks below the lower threshold, it is replaced by the next smaller size.

Replacement is non-trivial under concurrency: the parent's pointer to the resizing node must be updated atomically. Options:

• Indirection: each node has a generation counter; readers re-validate after observing a generation mismatch.
• CAS on parent: atomically swap parent's child pointer from old node to new.
• Mapping table (like Bw-tree): indirect via a node ID.

Real ART implementations (DuckDB, HyPer) use a combination.

Prefix compression¶

A trie's depth equals the key length. For 256-bit keys, that is 32 byte-levels. Most levels would have a single child; ART compresses these into a "prefix" stored in the parent.

Without prefix compression:
[a] -> [b] -> [c] -> Leaf("abc": ...)
[a] -> [b] -> [d] -> Leaf("abd": ...)

With prefix compression:
Node prefix="ab"
  [c] -> Leaf("abc": ...)
  [d] -> Leaf("abd": ...)

Prefix compression dramatically shortens the tree and improves cache behavior. The cost: comparing the prefix against the search key on every traversal.

SIMD acceleration¶

Node16's "find child for byte K" is a search over 16 sorted bytes. Modern CPUs have SIMD instructions (e.g., AVX2 _mm256_cmpeq_epi8) that can compare 16 bytes in one instruction, plus _mm256_movemask_epi8 to extract the match.

In Go, you cannot use intrinsics directly. Options:

• Use golang.org/x/sys/cpu to detect SIMD support and call assembly.
• Use linear scan; modern branch predictors are quite good.
• Use binary search (slower than linear for 16 elements due to branch misprediction).

In practice, Go ART implementations use linear scan and accept the small slowdown vs C++ SIMD-optimized versions.

Concurrent ART in production¶

HyPer, DuckDB, and several other database engines use concurrent ART. In Go, no production-grade concurrent ART exists. If you need one, the realistic path is:

• Implement a single-threaded ART with OLFIT-style version counters.
• Wrap with publish/subscribe COW for concurrency.
• Accept that performance will be 50-70% of a tuned C++ implementation.

For string-keyed in-memory indexes at very high scale, ART is the right choice. For mixed int/string keys with range queries, a B+-tree is simpler and competitive.

Hardware Transactional Memory (Intel TSX, ARMv8.1 LSE)¶

HTM provides hardware support for atomic execution of arbitrary code blocks. The protocol:

1. xbegin: start a hardware transaction. Returns a fallback address.
2. Read and write memory normally.
3. xend: commit. If no conflict, all reads and writes appear atomic.
4. If a conflict is detected (another core writes to a cache line you read), xabort is triggered and execution jumps to the fallback.

For trees, HTM can replace fine-grained latches: wrap a small critical section in xbegin/xend, fall back to a mutex on abort.

Intel TSX example (pseudocode)¶

status = _xbegin();
if (status == _XBEGIN_STARTED) {
    // Critical section: lock-free under HTM
    bt_insert(key, val);
    _xend();
} else {
    // Fallback: use the mutex
    mutex_lock();
    bt_insert(key, val);
    mutex_unlock();
}

If the transaction commits, we have the speed of a critical-section-free path. If it aborts, we fall back to the mutex.

When does HTM help?¶

• Short critical sections.
• Low write conflict rate.
• Many concurrent operations.

For long critical sections, HTM aborts due to cache evictions. For high-conflict workloads, HTM aborts due to conflicts. In either case, you spend most time in the fallback.

Reality check¶

Intel TSX has had a turbulent history: bugs in early implementations forced disablement on many CPUs. By 2025, TSX is available on most server-class Intel chips but is rarely used in production code outside of niche cases (some HPC, some research databases).

ARMv8.1 LSE provides atomic CAS instructions but not full HTM. ARM has Pointer Authentication and Memory Tagging but not TSX-equivalent.

Using HTM from Go¶

Go does not provide direct access to xbegin/xend. You would need cgo to call assembly. Even then, Go's runtime can preempt goroutines at any point, which interacts poorly with HTM (a preempted goroutine in a transaction aborts and falls back).

For Go in 2026, HTM is essentially unavailable. The senior file's discussion of HTM is intellectual completeness; in practice, you will not use it.

What HTM tells us about latch design¶

The interesting lesson from HTM is: critical sections must be short and simple to be fast. This is true even without HTM. Any time you hold a latch:

• Cache lines you touch must be exclusive (HTM teaches us how few you can have).
• Branch mispredictions cost.
• Function calls are expensive.
• Allocations are very expensive.

A well-designed latched B-tree mimics HTM's discipline even without HTM hardware: minimize the critical section to the smallest possible work.

OLFIT and MassTree in Depth¶

The OLFIT paper (Cha et al., 2001) and the MassTree paper (Mao et al., 2012) describe two related protocols for highly concurrent B+-trees in memory.

OLFIT mechanism¶

• Each node has a 32- or 64-bit version counter.
• Readers do not take latches; they validate the version before and after reading.
• Writers take an exclusive latch on a node, increment the version twice (start: odd, end: even), mutate, release.
• A reader seeing an odd version yields and retries.
• A reader whose pre/post version comparison differs retries.

For B-trees, OLFIT alone is not enough — concurrent splits leave readers in the wrong node. OLFIT is paired with B-link's right-sibling pointers to handle splits.

The protocol's strength: read throughput is limited only by memory bandwidth, not by lock contention. Writes still serialize per-node.

MassTree¶

MassTree extends OLFIT with two innovations:

1. Multi-level trie of B+-trees. The top level is a B+-tree of 8-byte key fragments; each leaf points to a sub-tree for keys with that prefix. This compresses common prefixes and avoids per-key string comparison overhead.
2. Versioned permuted keys. Each B+-tree node stores keys in insertion order, plus a separate "permutation" array that gives the sorted order. Inserts append + update the permutation; the version counter increments. Readers walk the permutation to find keys in sorted order.

MassTree's claimed throughput in 2012 was ~10M reads/sec per core, ~1M writes/sec per core on a 16-core machine — among the fastest in-memory B+-trees ever measured.

Implementing OLFIT in Go¶

A skeleton (extending the senior file's OCC sketch with B-link):

type Node struct {
    version  atomic.Uint64
    writeMu  sync.Mutex
    isLeaf   bool
    items    []item
    children []*Node
    highKey  int64
    rightSib *Node
}

func (t *OLFITree) Get(key int64) ([]byte, bool) {
    n := t.root.Load()
restart:
    for retries := 0; retries < 64; retries++ {
        if n == nil {
            return nil, false
        }
        v1 := n.version.Load()
        if v1&1 == 1 {
            runtime.Gosched()
            continue
        }
        // Read all fields.
        highKey := n.highKey
        items := n.items
        children := n.children
        rightSib := n.rightSib
        // Re-validate.
        v2 := n.version.Load()
        if v2 != v1 {
            n = t.root.Load()
            continue restart
        }
        // Use the values.
        if key > highKey {
            n = rightSib
            continue
        }
        if n.isLeaf {
            i, found := findItem(items, key)
            if !found {
                return nil, false
            }
            return items[i].val, true
        }
        i := childIndex(items, key)
        n = children[i]
    }
    panic("too many retries")
}

Note the careful re-validation after every node read. The runtime.Gosched() on observing an odd version is a small backoff.

Combine with B-link's split protocol and you have a functional OLFIT in Go. The implementation is ~500 lines for a complete B+-tree.

For Go production, this is not worth the complexity vs publish/subscribe COW. For an in-memory database engine, it might be.

Hekaton-Class In-Memory Engines¶

Microsoft SQL Server's Hekaton (released 2014, refined since) is the canonical example of an in-memory engine using all the techniques in this file:

• Bw-tree indexes for ordered access.
• Hash indexes (separate from the trees) for point access.
• MVCC with per-row version chains.
• Optimistic transactions: each transaction tracks its read set and validates at commit.
• No locks: pessimistic locking is replaced entirely by MVCC + OCC.
• In-memory transaction log with delayed durability.

The architecture:

[Transaction] -> [In-memory rows with version chains] -> [Bw-tree indexes] -> [Mapping table]
                                          \
                                           -> [Optional hash index for point access]

Each row is a record with:

• A pointer to the previous version.
• XMin (created-by transaction ID).
• XMax (deleted-by transaction ID, 0 if not deleted).
• Column data.

Inserts create a new row version and update both indexes (Bw-tree and hash). Deletes set XMax and add a delete marker to indexes. Updates create a new version and link it.

Concurrent transactions validate at commit: their read set's versions must still be the latest (or at least visible to their snapshot). If validation fails, abort and retry.

This design eliminates pessimistic locking entirely; everything is optimistic. For high-throughput workloads with low conflict rates, it can sustain millions of transactions per second on a single multicore machine.

What we learn from Hekaton¶

• Lock-free indexes are achievable with Bw-trees.
• MVCC + OCC can replace pessimistic locking for OLTP.
• In-memory engines have fundamentally different design points from disk-based engines.
• Hardware matters: Hekaton is heavily tuned for NUMA, cache hierarchies, and TSX (in the era when it was available).

For Go, building a Hekaton-class engine is a multi-year project. The closest equivalents in Go are CockroachDB (which uses Pebble + serializable isolation) and TiDB / TiKV (Rust, not Go, but architecturally similar).

Comparative Engine Tour¶

A brief survey of how major database engines implement their indexes:

PostgreSQL nbtree¶

• B+-tree with Lehman-Yao B-link protocol.
• Per-page latches.
• MVCC via transaction ID stamps on tuples.
• Vacuum process reclaims dead versions.
• WAL-protected for durability.

MySQL InnoDB¶

• Clustered B+-tree (primary key is the data).
• Per-page latches with deadlock detection.
• MVCC via undo logs (an alternative to per-row version chains).
• Adaptive Hash Index on top for very hot keys.

SQLite¶

• B+-tree per table or index.
• Single-writer (no concurrent writers).
• WAL or rollback journal for durability.
• Very different design point: embedded, low-concurrency.

Oracle TimesTen¶

• B-tree and hash indexes.
• In-memory; can be transient or durable.
• Locking-based concurrency.

SAP HANA¶

• Column-store main + delta merge architecture.
• Row-store for OLTP via a different tree.
• MVCC via tuple timestamps.
• Heavily SIMD-optimized.

MS SQL Server Hekaton¶

• Bw-trees + hash indexes.
• MVCC + OCC.
• Optimistic transactions.

Google Spanner¶

• Distributed B-tree with TrueTime.
• Multi-version with strict serializability.
• Snapshot reads at any past timestamp.
• Synchronously replicated across data centers.

CockroachDB¶

• Pebble (LSM) as the storage engine.
• Range-based sharding ("ranges" of ~64 MB each).
• Multi-version via timestamped keys.
• Distributed transactions via two-phase commit.

TiDB / TiKV¶

• TiKV is the Rust storage layer, RocksDB-based.
• TiDB is the SQL layer in Go.
• Distributed transactions via Percolator protocol.

Aerospike¶

• Hybrid hash + B-tree.
• Persistent storage with SSD-aware access.
• High throughput via lock-free reads.

MongoDB WiredTiger¶

• B+-tree on disk with skiplist memtables.
• MVCC via timestamps.
• LSM mode also available.

Reading the source of any one of these is a multi-month commitment. Reading the design documents (READMEs, blog posts) for two or three of them is more achievable and educational.

Hardware-Aware Tree Design¶

At the professional level, hardware details directly shape protocol choices.

Cache lines¶

• x86 cache line: 64 bytes.
• ARMv8 cache line: 64 or 128 bytes.
• POWER cache line: 128 bytes.

A B-tree node should ideally fit in one or two cache lines. A 64-byte node holds about 4-8 items depending on item size. For larger fanouts, you accept multiple cache lines but try to keep them aligned.

Go does not give you cache-line alignment directly, but runtime.Compactify-style tricks work. The simplest is:

type CacheLineNode struct {
    _    [0]byte // ensure alignment
    data [56]byte // header data
    _    [8]byte // padding to fill cache line
}

For Go tree libraries, cache-line alignment is mostly handled by Go's allocator already; explicit alignment helps only at the margins.

Prefetching¶

A CPU instruction prefetcht0 (Intel) loads a cache line into L1 before it is needed. For tree traversal, you can prefetch the next node while processing the current.

In Go, no direct prefetch instruction. Some tricks:

• Read a non-essential field of the next node to trigger the load.
• Use SIMD-style libraries that wrap intrinsics.

Real impact: maybe 10-20% on tight microbenchmarks. Rarely worth the complexity in Go.

Branch prediction¶

Modern CPUs predict branches with >95% accuracy on regular patterns. For tree traversal, the descent direction is data-dependent, so branch prediction often fails — each comparison is a potential misprediction.

Tricks to reduce mispredictions:

• Use branchless code where possible (a = (cond ? x : y) becomes a CMOV).
• Sort branches by likelihood; mark with likely/unlikely (no Go equivalent).
• Use linear scan in small nodes; the predictor handles it well.

Go's compiler is conservative about branchless code; you may need to write subtle expressions that survive optimization.

NUMA¶

On multi-socket machines, memory accesses across sockets cost 2-3x more than local accesses. For an in-memory tree:

• Pin goroutines to specific sockets (unix.SchedSetaffinity, requires syscall).
• Allocate the tree on a specific NUMA node (numa_alloc_onnode, via cgo).
• Replicate read-only data per socket.

For Go services on a single socket, NUMA does not matter. For very large servers, it does.

Persistent Memory¶

Intel Optane DCPMM (discontinued 2022) was the most prominent persistent memory product. Trees on persistent memory require:

• Crash-consistency: ensure writes hit persistence before subsequent dependent writes.
• clflushopt, clwb, pcommit instructions to flush cache lines.
• Special protocols for safe in-place updates.

Real impact on Go: low. Most Go databases use OS-level persistence (write to file + fsync), not direct persistent memory access.

Profiling at the Microbenchmark Level¶

At the professional level, profiling tools must measure at the nanosecond scale.

go test -bench is the starting point¶

go test -bench=BenchmarkInsert -benchmem -benchtime=10s -count=5

-count=5 runs each benchmark 5 times so you can see variance. -benchtime=10s runs each iteration for 10 seconds to amortize startup.

pprof for CPU profiling¶

go test -bench=BenchmarkInsert -cpuprofile=cpu.prof
go tool pprof cpu.prof

In pprof, top10 shows the hottest functions. web (requires graphviz) shows the call graph. disasm shows annotated assembly.

For tree code, the hottest functions are typically findInItems, insertItemSorted, and the comparator. Optimizing them helps.

runtime/trace for scheduling and latency¶

go test -bench=BenchmarkInsert -trace=trace.out
go tool trace trace.out

Trace shows goroutine states, blocking events, GC pauses. Useful for diagnosing why a workload is not scaling with cores.

perf (Linux) for hardware counters¶

perf stat -e cache-misses,branch-misses,instructions ./bench

Shows L1/L2/LLC cache misses, branch mispredictions, IPC. For tuned tree code, you want:

• IPC > 2.
• Cache miss rate < 1% per instruction.
• Branch misprediction < 1% per branch.

If any of these are off, optimize for cache or branches.

Microbenchmark discipline¶

A few rules:

• Always run multiple iterations and check variance.
• Always use b.RunParallel for concurrency benchmarks.
• Always pin the GOMAXPROCS to avoid scheduler noise.
• Watch out for compiler optimizations that elide the work you are trying to measure (use b.SetBytes and stash results).
• Re-measure after each change; do not trust intuition.

For nanosecond-scale measurements, the noise floor matters. Take the median of 10 runs, not the mean.

Coding Patterns¶

At the professional level:

Pattern 1: Lock-free + epoch reclamation. For data structures that cannot be GC'd cleanly (unsafe.Pointer, cgo).

Pattern 2: Mapping-table indirection. Decouple logical IDs from memory pointers. Enables consolidation, migration, replication.

Pattern 3: Delta records + lazy consolidation. Write-once, read-many-then-fold.

Pattern 4: Per-thread caches. Each goroutine maintains its own short-lived cache that synchronizes occasionally with the global state.

Pattern 5: NUMA-aware sharding. Pin shards to NUMA nodes; route requests to the right shard based on key.

Pattern 6: HTM with mutex fallback. Optimistic fast path; pessimistic fallback. (Rarely applicable in Go.)

Pattern 7: Hardware-aware layout. Cache-aligned nodes, hot-cold field separation, branch-predictable comparators.

Clean Code at Engine Scale¶

• Treat the data structure as an artifact. Document every invariant, every CAS, every memory ordering decision.
• Pair every invariant with a runtime check (under a debug tag) that asserts it.
• Use named lock types that signal intent: WriteLatch, ReadLatch.
• No global state except for explicitly singleton resources (e.g., the mapping table).
• Fuzz the protocol. Random sequence of operations + invariant check.
• Model check the protocol (TLA+, Promela) if it is novel.

Engine code is shipped once, debugged forever. Discipline is everything.

Product Use¶

Realistic use cases for professional-level techniques:

• An in-memory transactional engine (Hekaton, MemSQL).
• A distributed database's local storage (CockroachDB, TiDB, FoundationDB).
• A real-time analytics engine (HyPer, ClickHouse).
• A search index (Elasticsearch's Lucene segments).
• A high-frequency-trading order book.
• An adtech bidding system.

In each case, the tree is the critical component, and squeezing the last percent of throughput is worth months of engineering.

For everything else: use tidwall/btree with publish/subscribe COW.

Performance Tips¶

• Profile with hardware counters. Cache misses and branch mispredictions dominate.
• Minimize allocations. Use arenas or pre-allocated pools.
• Pack nodes tightly. Fewer cache lines per node = fewer cache misses.
• Avoid pointer chasing. Inline what you can.
• Use SIMD where available. (Hard in Go; requires assembly.)
• NUMA-aware allocation. Pin to local memory.
• Batch operations. Reduce per-call overhead.

Best Practices¶

• Build on top of a published, well-tested protocol. Do not invent.
• Test exhaustively, including under random fault injection.
• Document the protocol's correctness argument.
• Compare against published benchmarks; if you cannot beat the literature, do not deploy.
• Have a backup plan if the advanced protocol underperforms.

Edge Cases and Pitfalls¶

• Memory pressure under heavy COW. Bound the working set.
• GC pauses under heavy allocation. Tune GC, consider non-Go languages for the inner loop.
• NUMA imbalance. Shard to balance memory access.
• Persistent memory crash consistency. Get this wrong and you lose data.
• CAS livelock. A backoff is essential.
• HTM aborts under cache pressure. Have a fast fallback.

Common Mistakes¶

1. Implementing a Bw-tree because it sounds cool.
2. Using HTM without a proper fallback.
3. Ignoring NUMA on a multi-socket machine.
4. Microbenchmarking with too few iterations.
5. Trusting your intuition about hot paths without profiling.
6. Building a custom tree when an established library exists.

Common Misconceptions¶

• "Lock-free is always faster." Often the same or slower than fine-grained locking. Profile.
• "HTM is the future." It was, briefly. Now it is a niche.
• "In-memory engines do not need persistence." They do (write-ahead logging, periodic snapshots).
• "Bigger fanout is always better." Diminishing returns; comparison cost grows.
• "More concurrency is always better." No — coordinated coordination beats heroic concurrency.

Tricky Points¶

• Mapping table resizing under concurrent access. A classic concurrent data structure problem.
• Delta chain consolidation under contention. Two threads consolidating simultaneously.
• Split delta visibility. Ensuring all readers see the split before the parent is updated.
• Epoch garbage collection of long-lived objects. Bounding the epoch list.
• HTM transaction size. Cache footprint limits.

Tricky Questions¶

1. Why does the Bw-tree's mapping table CAS make the protocol lock-free for writes?
2. How does ART's prefix compression interact with concurrent inserts?
3. Why is HTM rarely used in production?
4. What is the worst-case throughput of a Bw-tree under heavy write conflict on a single leaf?
5. How does Hekaton's optimistic transaction protocol handle write-write conflicts?
6. Why does MassTree split its tree by 8-byte key fragments?
7. What is the trade-off between consolidation threshold and read latency?
8. How does PostgreSQL's vacuum interact with concurrent updates?
9. Why is NUMA awareness essential for engines exceeding one socket's capacity?
10. What is the difference between MVCC via version chains and MVCC via undo logs?

For each, articulate the answer with hardware-level reasoning.

Test¶

For professional-level work, testing includes:

• Unit tests with invariant assertions.
• Property-based tests (e.g., quickcheck-style).
• Fuzz tests for protocol robustness.
• Long-running stress tests.
• Hardware-specific tests (NUMA, multi-socket).
• Comparison benchmarks against literature.

A professional codebase has thousands of tests covering all of these.

Cheat Sheet¶

Self-Assessment Checklist¶

• Explain the Bw-tree mapping table.
• Walk through a delta chain lookup.
• Describe ART's adaptive node sizes.
• Compare OLFIT to plain hand-over-hand.
• Explain Hekaton's optimistic transaction protocol.
• Identify cache-line and NUMA impacts on a tree's performance.
• Set up a hardware-counter-based profile.
• Decide when (almost never) to deploy these techniques.

Summary¶

The professional level is where research meets engineering. Bw-trees, concurrent ART, HTM, OLFIT — these are the techniques at the bleeding edge of in-memory database engine design. They are powerful, expensive to implement, and rarely necessary outside their target use cases.

For Go in 2026, the professional-level conclusion is consistent with the senior file: publish/subscribe COW with tidwall/btree is the default. Reach for these advanced techniques only when you are building an in-memory database engine and the throughput targets demand them.

The value of this file is intellectual: you can now read any paper, debate trade-offs with database engineers, and architect engines at the apex of the design space.

Further Reading¶

• Levandoski et al., The Bw-Tree.
• Wang et al., Building a Bw-tree Takes More Than Just Buzz Words — a 2018 paper detailing implementation lessons.
• Leis et al., The Adaptive Radix Tree.
• Cha et al., OLFIT.
• Mao et al., MassTree.
• Larson et al., High-Performance Concurrency Control Mechanisms for Main-Memory Databases — Hekaton's MVCC + OCC.
• Diaconu et al., Hekaton: SQL Server's Memory-Optimized OLTP Engine.
• Kemper, Neumann, HyPer: Hybrid OLTP&OLAP High-Performance Database System.
• Faerber et al., SAP HANA Database: Data Management for Modern Business Applications.
• The Linux kernel RCU documentation.
• McKenney, Is Parallel Programming Hard? — RCU bible.

Related Topics¶

• Senior file — foundational concurrent tree material.
• MVCC — full MVCC treatment.
• Concurrent Skip List — alternative ordered structure.

Diagrams¶

Bw-tree mapping table¶

Mapping Table:
  ID=1 -> [Base node A]
  ID=2 -> [Delta(insert k=5, val=v) -> Delta(insert k=8, val=w) -> Base node B]
  ID=3 -> [Base node C]

Writer inserts k=10 into ID=2:
  new_delta = Delta(insert k=10, val=x, next=current head)
  CAS mapping[2] from old head to new_delta

The mapping table is the source of truth. Updates are CAS operations on table entries.

ART node sizes¶

Node4:   keys=[0x41, 0x42, 0x43, 0x44]  children=[*,*,*,*]
Node16:  keys=[16 sorted bytes]          children=[16 pointers]
Node48:  indices=[256 bytes mapping byte->slot]  children=[48 pointers]
Node256: children=[256 pointers, one per byte]

Adaptive resizing: when Node4 fills, replace with Node16; etc.

Appendix A: Bw-tree consolidation in implementation detail¶

Consolidation is the most subtle operation in a Bw-tree. Let's walk through it carefully.

When a delta chain reaches threshold length (typically 8-16 records), the next reader triggers consolidation:

func (t *BwTree) maybeConsolidate(id NodeID, n *Node) *Node {
    if chainLength(n) < threshold {
        return n
    }
    // Build the consolidated base.
    base := &Node{
        isDelta: false,
        isLeaf:  n.isLeafChain(),
    }
    // Walk the chain in reverse to apply deltas in order.
    deltas := collectChain(n)
    base.items = applyDeltas(deltas)
    base.highKey = n.highKey
    base.rightSib = n.rightSib
    // Attempt the CAS.
    if t.mapping[id].CompareAndSwap(n, base) {
        // We won. Retire the old chain.
        t.epoch.Retire(n)
        return base
    }
    // Lost. Someone else consolidated. Re-read.
    return t.mapping[id].Load()
}

func collectChain(n *Node) []*Delta {
    var deltas []*Delta
    for n.isDelta {
        deltas = append(deltas, n.delta)
        n = n.delta.Next
    }
    // n is now the base.
    return deltas
}

func applyDeltas(deltas []*Delta) []item {
    // Start from base.items (visible at the end of the chain).
    // Apply deltas in reverse (oldest first).
    base := deltas[len(deltas)-1].Next // the base node
    items := append([]item{}, base.items...)
    for i := len(deltas) - 2; i >= 0; i-- {
        d := deltas[i]
        switch d.Kind {
        case DKInsert:
            items = insertSorted(items, d.Key, d.Value)
        case DKDelete:
            items = removeKey(items, d.Key)
        }
    }
    return items
}

Subtleties:

1. Two concurrent consolidations. Both threads build a base; only one's CAS succeeds. The loser's work is wasted (could be wasted significantly if the chain is long). Mitigation: random backoff before consolidating, so consolidators don't all start simultaneously.

2. Concurrent insert during consolidation. While a consolidator is building the base, another writer adds a delta to the head of the chain. The consolidator's CAS sees the new head and fails. The consolidator must restart or give up.

3. Memory reclamation. The old chain (now retired) cannot be freed until no thread can see it. Epoch-based reclamation handles this. In Go, the GC handles it as long as no goroutine retains a reference to the old chain.

4. Split delta in the chain. If the chain contains a DeltaSplit, the consolidator must handle it specially: items >= pivot belong in the right sibling, not in the consolidated base.

A worked example¶

Start state: ID=42 -> [Base { items: [10, 20, 30], hk: 100 }]

Insert 15: - Allocate Delta(insert, 15). - Delta.Next = Base - CAS mapping[42] from Base to Delta - mapping[42] -> [Delta(insert, 15) -> Base]

Insert 25: - Allocate Delta(insert, 25). - Delta.Next = current head = Delta(insert, 15) - CAS - mapping[42] -> [Delta(insert, 25) -> Delta(insert, 15) -> Base]

After threshold inserts, consolidate: - Walk chain: collect [Delta(insert, 25), Delta(insert, 15), ..., Base] - Apply in reverse: start with Base.items [10, 20, 30], then insert 15 (yielding [10, 15, 20, 30]), then insert 25 (yielding [10, 15, 20, 25, 30]). - New base: items=[10, 15, 20, 25, 30], hk=100. - CAS mapping[42] from current head to new base. - Old chain is retired.

Reads after consolidation see the new base; reads in progress before consolidation see the old chain (their pointer to the old head is still valid until epoch advances).

Appendix B: Bw-tree split protocol¶

Splits in a Bw-tree are also delta records. Let's walk through a leaf split.

Initial state: leaf ID=42 is full with items [10, 20, 30, 40, 50, 60, 70, 80].

To split: 1. Allocate new leaf ID=43 with items [50, 60, 70, 80]. Install in mapping table. 2. Post a SplitDelta to ID=42: { Kind: DKSplit, Pivot: 50, SiblingID: 43, Next: current state of 42 }. 3. CAS mapping[42] to point to the SplitDelta.

After step 3, in-flight readers on ID=42 will see the SplitDelta and route to ID=43 for keys >= 50.

1. Update the parent: post a delta to the parent telling it about ID=43.
2. Eventually consolidate both ID=42 (which now has items [10, 20, 30, 40] plus the SplitDelta) and the parent.

The critical insight: between step 3 and step 4, readers can still find any key. If a key is < 50, it is in ID=42's items. If >= 50, the SplitDelta routes to ID=43. The parent has not yet been updated, but readers do not need it to be.

Why this is lock-free¶

No latches. Every state change is a CAS on the mapping table. Concurrent writers can:

• Insert into ID=42 (adds a Delta on top of the SplitDelta). The reader sees the Delta first, then the SplitDelta.
• Insert into ID=43 (adds a Delta to ID=43's chain).
• Split ID=42 again (cascading split).

Each operation is local CAS. No global lock. Lock-free.

Why this is hard¶

Correctness requires careful protocol design. Consider:

• A reader sees a SplitDelta but the parent has not yet been updated. The reader's traversal from the root would route through the parent to ID=42, then via the SplitDelta to ID=43. Fine.
• A reader caches a parent pointer to ID=42 (e.g., during a range scan). The parent gets updated to also know about ID=43. The reader's cached pointer is now stale but not invalid — ID=42 still exists, just smaller. The reader can complete its current operation.
• A consolidator is folding ID=42's chain (Delta -> SplitDelta -> Base). The consolidation must produce a base node with [10, 20, 30, 40] items and a SplitDelta still in the chain (because the SplitDelta affects the parent, not just the leaf).

Production Bw-tree implementations have all sorts of subtle corrections for cases like this. Microsoft's reference code has been refined over years.

Appendix C: Concurrent ART implementation sketches¶

A concurrent ART in Go would have the structure:

package art

import (
    "sync"
    "sync/atomic"
)

type NodeKind uint8

const (
    Node4 NodeKind = iota
    Node16
    Node48
    Node256
    Leaf
)

type Node struct {
    kind        NodeKind
    version     atomic.Uint64
    writeMu     sync.Mutex
    prefix      []byte
    numChildren uint16
    // Type-specific body. In Go we use a discriminated struct.
    body interface{}
}

type Node4Body struct {
    keys     [4]byte
    children [4]*Node
}

// ... and so on

The Get path uses OLFIT-style optimistic concurrency:

func (t *ART) Get(key []byte) ([]byte, bool) {
    for retries := 0; retries < 64; retries++ {
        n := t.root.Load()
        depth := 0
    walk:
        for {
            if n.kind == Leaf {
                leaf := n.body.(*LeafBody)
                if bytes.Equal(leaf.key, key) {
                    return leaf.value, true
                }
                return nil, false
            }
            v1 := n.version.Load()
            if v1&1 == 1 {
                runtime.Gosched()
                break walk
            }
            // Match prefix.
            if !matchPrefix(n.prefix, key, depth) {
                if n.version.Load() != v1 {
                    break walk
                }
                return nil, false
            }
            depth += len(n.prefix)
            if depth >= len(key) {
                if n.version.Load() != v1 {
                    break walk
                }
                return nil, false
            }
            child := findChild(n, key[depth])
            if child == nil {
                if n.version.Load() != v1 {
                    break walk
                }
                return nil, false
            }
            if n.version.Load() != v1 {
                break walk
            }
            n = child
            depth++
        }
    }
    panic("too many retries")
}

Inserts take the per-node writeMu and increment the version counter twice (odd, mutate, even). Resizing is the tricky part: when a Node4 fills, allocate a Node16, copy the children, then CAS the parent's pointer.

The Go implementation gets to ~2-3M lookups/sec/core. A tuned C++ implementation can do 10-15M. The gap is mostly Go's lack of intrinsics for SIMD comparison.

Appendix D: A walk through Hekaton's optimistic transaction protocol¶

Hekaton (SQL Server's in-memory engine) uses MVCC + OCC. Let's walk through a transaction:

1. Transaction starts. Assign transaction ID T. Take a snapshot of the latest committed transaction ID S.
2. Reads. For each read, find the version with XMin <= S and (XMax == 0 OR XMax > S). Track the version pointer in the read set.
3. Writes. Create a new version with XMin = T. Mark the previous version with XMax = T. Update the index. Track the new version in the write set.
4. Validation phase. Before committing, scan the read set:
   • For each version in the read set, verify it is still the latest visible version.
   • If any read is stale (a newer version was committed by another transaction after S), abort.
5. Commit. Mark T as committed. The versions become permanently visible.
6. Cleanup. Old versions become garbage when no transaction can see them.

If the validation phase fails, the transaction aborts and is retried (possibly by the application).

Optimism vs pessimism¶

In a pessimistic system (most disk-based databases), every read takes a row lock to prevent concurrent writers. In Hekaton, no row locks. Conflicts are detected at commit time.

This works well when conflicts are rare. If two transactions update the same row, only one wins; the loser retries. For workloads with high conflict rates, the abort overhead becomes painful.

Implementing Hekaton in Go¶

A skeleton:

package hekaton

import (
    "sync"
    "sync/atomic"
)

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

type Row struct {
    Key    string
    mu     sync.Mutex
    Newest *Version
}

type Tx struct {
    ID      int64
    Snapshot int64
    Reads   map[string]*Version
    Writes  map[string]*Version
}

type Engine struct {
    mu         sync.Mutex
    rows       *btree.BTreeG[*Row]
    txCounter  atomic.Int64
    commitLog  map[int64]bool // committed transactions
    commitMu   sync.RWMutex
}

func (e *Engine) Begin() *Tx {
    return &Tx{
        ID:       e.txCounter.Add(1),
        Snapshot: e.lastCommitted(),
        Reads:    make(map[string]*Version),
        Writes:   make(map[string]*Version),
    }
}

func (e *Engine) Read(tx *Tx, key string) ([]byte, bool) {
    row, ok := e.findRow(key)
    if !ok {
        return nil, false
    }
    row.mu.Lock()
    defer row.mu.Unlock()
    for v := row.Newest; v != nil; v = v.Next {
        if v.XMin <= tx.Snapshot && e.isCommitted(v.XMin) &&
            (v.XMax == 0 || v.XMax > tx.Snapshot || !e.isCommitted(v.XMax)) {
            tx.Reads[key] = v
            return v.Value, true
        }
    }
    return nil, false
}

func (e *Engine) Write(tx *Tx, key string, value []byte) {
    row, ok := e.findRow(key)
    if !ok {
        row = &Row{Key: key}
        e.insertRow(row)
    }
    row.mu.Lock()
    defer row.mu.Unlock()
    if row.Newest != nil {
        row.Newest.XMax = tx.ID
    }
    v := &Version{Value: value, XMin: tx.ID, Next: row.Newest}
    row.Newest = v
    tx.Writes[key] = v
}

func (e *Engine) Commit(tx *Tx) bool {
    e.mu.Lock()
    defer e.mu.Unlock()
    // Validation phase.
    for key, oldV := range tx.Reads {
        row, _ := e.findRow(key)
        row.mu.Lock()
        // Is oldV still the visible version?
        visible := false
        for v := row.Newest; v != nil; v = v.Next {
            if v == oldV {
                if v.XMax == 0 || v.XMax == tx.ID {
                    visible = true
                }
                break
            }
        }
        row.mu.Unlock()
        if !visible {
            e.abort(tx)
            return false
        }
    }
    // Commit.
    e.commitMu.Lock()
    e.commitLog[tx.ID] = true
    e.commitMu.Unlock()
    return true
}

func (e *Engine) abort(tx *Tx) {
    // Roll back all writes.
    for key, v := range tx.Writes {
        row, _ := e.findRow(key)
        row.mu.Lock()
        if row.Newest == v {
            row.Newest = v.Next
            if v.Next != nil {
                v.Next.XMax = 0
            }
        }
        row.mu.Unlock()
    }
}

This is ~150 lines of skeleton code. Production Hekaton is ~50000 lines. But the architectural shape is the same: MVCC versions, optimistic validation, commit log.

Appendix E: A deep dive on NUMA-aware tree design¶

On a multi-socket server, a memory access to a remote socket can cost 2-3x more than a local access. For an in-memory tree:

• Each socket has ~hundreds of GB of local memory.
• Cross-socket traffic goes through QPI (Intel) or AMD's Infinity Fabric.
• Allocations from a goroutine running on socket 0 should ideally live in socket 0's memory.

In Go, no built-in NUMA awareness. Options:

1. Pin goroutines to sockets via runtime.LockOSThread plus syscalls for CPU affinity.
2. Shard the tree by socket. Each socket has its own tree shard; queries are routed to the right shard.
3. Use cgo to call numa_alloc_onnode for explicit NUMA-local allocation.

For Go services on a single socket (which is most), NUMA does not matter. For very large servers (32+ cores spanning multiple sockets), NUMA-aware sharding can yield 2x throughput.

A NUMA-aware sharded store¶

type NUMAStore struct {
    perSocket [numSockets]*Store
}

func (s *NUMAStore) Get(key string) (Item, bool) {
    socket := currentSocket() // syscall to find which CPU we're on
    return s.perSocket[socket].Get(key)
}

The catch: if the goroutine migrates between sockets, the routing is wrong. Pin with runtime.LockOSThread to prevent migration.

NUMA awareness is rare in pure Go. Most Go services that need it call out to C (CGo, eBPF) or use a different language for the inner loop.

Appendix F: Persistent memory and crash consistency¶

Intel Optane DCPMM (now discontinued) offered byte-addressable persistent memory. Trees on persistent memory required:

• Atomic 8-byte writes (the natural unit of persistence).
• clflushopt / clwb / sfence instructions to ensure cache lines reach persistence before subsequent dependent writes.
• Crash recovery protocols to handle partial writes.

Most database engines do not use persistent memory directly; they write to a WAL on SSD. But research engines (SAP HANA's NVM-aware mode, Microsoft's PMDK-based work) explore direct persistent-memory storage.

For Go, persistent memory is essentially unavailable. The hardware was discontinued; the libraries (PMDK) are C-only.

The interesting algorithmic content remains relevant: techniques like epoch-based persistent atomic updates are applicable to any storage with similar characteristics (e.g., journaled filesystems with append-only semantics).

Appendix G: Profiling with hardware counters¶

For nanosecond-scale tuning, hardware counters are essential. On Linux:

perf stat -e cache-misses,cache-references,branch-misses,branches,instructions,cycles ./bench

Output:

   12,345,678 cache-misses          # 5.43% of cache references
  227,123,456 cache-references
      567,890 branch-misses         # 0.34% of branches
  166,789,012 branches
1,234,567,890 instructions          # 1.87 insn per cycle
  660,123,456 cycles

For tuned tree code, you want:

• IPC > 2 (modern CPUs can issue 4+ instructions per cycle with ILP).
• Cache miss rate < 1% per cache reference.
• Branch miss rate < 1% per branch.

If IPC is low, look for instruction-level parallelism opportunities or dependency chains. If cache misses are high, improve data layout or prefetching. If branch misses are high, restructure conditionals or use branchless code.

For Go, the relevant flags are -gcflags=-S to see assembly, pprof for high-level profiling, and perf for hardware counters.

Appendix H: A long worked example — implementing OLFIT in Go¶

Let's build a complete OLFIT B+-tree in Go for int64 keys to string values. About 600 lines. This is at the limit of what is reasonable to attempt in Go.

package olfit

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

const fanout = 32

type Node struct {
    version  atomic.Uint64
    writeMu  sync.Mutex
    isLeaf   bool
    items    []item
    children []*Node
    highKey  int64
    rightSib *Node
}

type item struct {
    Key int64
    Val string
}

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

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

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

func (n *Node) beginWrite() {
    n.writeMu.Lock()
    n.version.Add(1) // now odd
}

func (n *Node) endWrite() {
    n.version.Add(1) // now even
    n.writeMu.Unlock()
}

func (t *Tree) Get(key int64) (string, bool) {
restart:
    for retries := 0; retries < 64; retries++ {
        n := t.root.Load()
        for {
            v1 := n.version.Load()
            if v1&1 == 1 {
                runtime.Gosched()
                continue restart
            }
            // Read all fields.
            isLeaf := n.isLeaf
            items := n.items
            children := n.children
            highKey := n.highKey
            rightSib := n.rightSib
            // Re-validate.
            v2 := n.version.Load()
            if v2 != v1 {
                continue restart
            }
            // Right-walk if key > highKey.
            if key > highKey && rightSib != nil {
                n = rightSib
                continue
            }
            if isLeaf {
                i, found := findItem(items, key)
                if found {
                    return items[i].Val, true
                }
                return "", false
            }
            i := childIndex(items, key)
            n = children[i]
        }
    }
    panic("too many retries")
}

func findItem(items []item, key int64) (int, bool) {
    i := sort.Search(len(items), func(i int) bool { return items[i].Key >= key })
    if i < len(items) && items[i].Key == key {
        return i, true
    }
    return i, false
}

func childIndex(items []item, key int64) int {
    return sort.Search(len(items), func(i int) bool { return items[i].Key >= key })
}

func (t *Tree) Set(key int64, val string) {
    t.rootMu.Lock()
    n := t.root.Load()
    n.beginWrite()
    if len(n.items) == fanout {
        // Grow root.
        newRoot := &Node{
            isLeaf:   false,
            highKey:  maxKey,
            children: []*Node{n},
        }
        newRoot.beginWrite()
        t.root.Store(newRoot)
        splitChild(newRoot, 0)
        n.endWrite()
        n = newRoot
    }
    t.rootMu.Unlock()
    insertNonFull(n, key, val)
}

func splitChild(parent *Node, i int) {
    child := parent.children[i]
    // child must already be write-latched
    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.
    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 insertNonFull(n *Node, key int64, val string) {
    i, found := findItem(n.items, key)
    if found {
        n.items[i].Val = val
        n.endWrite()
        return
    }
    if n.isLeaf {
        n.items = append(n.items, item{})
        copy(n.items[i+1:], n.items[i:])
        n.items[i] = item{Key: key, Val: val}
        n.endWrite()
        return
    }
    child := n.children[i]
    child.beginWrite()
    if len(child.items) == fanout {
        splitChild(n, i)
        if key > n.items[i].Key {
            child.endWrite()
            child = n.children[i+1]
            child.beginWrite()
        }
    }
    n.endWrite()
    insertNonFull(child, key, val)
}