Buffer Pool and B+Tree

The other engine design

LSM trees write sequentially and merge later. The other dominant design — PostgreSQL, MySQL InnoDB, SQLite, BoltDB/bbolt, LMDB — keeps data in a B+tree of fixed-size pages updated in place, with a buffer pool caching pages in memory. Reads are cheaper (one path from root to leaf, no merging across files); random writes are more expensive (each one dirties a whole page). Building a small one in Go makes the trade-offs in B-tree Index and Storage Engines concrete. The code below (about 410 lines) stores uint64 → uint64, is persistent, and passes a model test of 200,000 random inserts with a 64-frame pool that forces constant eviction.

Pages

The file is an array of 4 KB pages; page n lives at offset n × 4096. Page 0 holds metadata (the root page id). A node is one page:

leaf:      [isLeaf=1][n (2 B)][next leaf id (4 B)] keys[255] values[255]
internal:  [isLeaf=0][n (2 B)][unused (4 B)]       keys[340] children[341]

const (
    PageSize    = 4096
    hdr         = 8
    leafCap     = (PageSize - hdr) / 16     // 255 key/value pairs
    internalCap = (PageSize - hdr - 4) / 12 // 340 keys, 341 children
)

type node struct{ b *[PageSize]byte } // a view over a page's bytes in the buffer pool

func (n node) key(i int) uint64 { return binary.LittleEndian.Uint64(n.b[hdr+8*i:]) }
func (n node) child(i int) PageID {
    return PageID(binary.LittleEndian.Uint32(n.b[n.childOff(i):]))
}

// search returns the first index with key(i) >= k (binary search within the page).
func (n node) search(k uint64) int {
    return sort.Search(n.count(), func(i int) bool { return n.key(i) >= k })
}

The node is a view, not a Go struct: it reads and writes fields directly in the page's bytes, so there is no serialization step when a page is written back, and the in-memory format is the on-disk format. With 341 children per internal node, three levels address 341² × 255 ≈ 30 million keys — the fan-out is why B+trees are shallow.

Fixed-size keys keep the example simple. Real engines use slotted pages: a slot array of offsets at the front, variable-length records packed from the back, so keys and values of any length fit and records can be moved within a page without changing their slot number.

The buffer pool

The buffer pool keeps a fixed number of page frames in memory and maps page ids to frames. Callers pin a page while using it; only unpinned pages can be evicted.

type frame struct {
    id    PageID
    data  [PageSize]byte
    pins  int
    dirty bool
    ref   bool // CLOCK "recently used" bit
}

// Fetch pins page id and returns its frame. Callers must Unpin it.
func (bp *BufferPool) Fetch(id PageID) (*frame, error) {
    bp.mu.Lock()
    defer bp.mu.Unlock()
    if idx, ok := bp.table[id]; ok { // hit
        fr := &bp.frames[idx]
        fr.pins++
        fr.ref = true
        return fr, nil
    }
    idx, err := bp.victim() // miss: find a frame to reuse
    if err != nil {
        return nil, err // every frame is pinned
    }
    fr := &bp.frames[idx]
    if _, err := bp.f.ReadAt(fr.data[:], int64(id)*PageSize); err != nil {
        return nil, err
    }
    fr.id, fr.pins, fr.dirty, fr.ref = id, 1, false, true
    bp.table[id] = idx
    return fr, nil
}

// victim: CLOCK — skip pinned frames, give recently used ones a second chance.
func (bp *BufferPool) victim() (int, error) {
    for i := 0; i < 2*len(bp.frames); i++ {
        idx := bp.hand
        bp.hand = (bp.hand + 1) % len(bp.frames)
        fr := &bp.frames[idx]
        if fr.pins > 0 {
            continue
        }
        if fr.ref {
            fr.ref = false
            continue
        }
        if fr.dirty { // write back before reuse
            if _, err := bp.f.WriteAt(fr.data[:], int64(fr.id)*PageSize); err != nil {
                return 0, err
            }
        }
        delete(bp.table, fr.id)
        return idx, nil
    }
    return 0, ErrNoFreeFrame
}

CLOCK approximates LRU without moving list nodes on every hit — a hit only sets a bit — which matters because the buffer pool is the hottest structure in the engine (Cache Replacement Policies). PostgreSQL uses a CLOCK variant with usage counts; InnoDB uses an LRU split into young and old sublists so a single table scan cannot flush the whole cache.

Why a buffer pool instead of letting the OS page cache do it (or mmap)? The engine knows things the kernel does not: which pages are pinned by an operation in progress, which dirty pages may not be written yet (because their WAL records are not durable — the WAL-before-data rule), and which pages a scan will never touch again. Those constraints are the reason most databases manage their own cache with O_DIRECT I/O, and the reasons mmap-based engines need careful workarounds.

Search and insert

func (t *Tree) Get(k uint64) (uint64, bool, error) {
    t.mu.RLock()
    defer t.mu.RUnlock()
    id := t.root
    for {
        fr, err := t.bp.Fetch(id)
        if err != nil {
            return 0, false, err
        }
        n := node{&fr.data}
        i := n.search(k)
        if n.leaf() {
            ok := i < n.count() && n.key(i) == k
            var v uint64
            if ok {
                v = n.val(i)
            }
            t.bp.Unpin(fr, false)
            return v, ok, nil
        }
        if i < n.count() && n.key(i) == k {
            i++ // a separator equal to k means k lives in the right subtree
        }
        id = n.child(i)
        t.bp.Unpin(fr, false)
    }
}

Insert descends recursively; if a node overflows, it splits and returns a separator key and the new right sibling to its parent:

func (t *Tree) splitLeaf(n node) (sep uint64, right PageID, split bool, err error) {
    fr, err := t.bp.New()
    if err != nil {
        return 0, 0, false, err
    }
    defer t.bp.Unpin(fr, true)
    r := node{&fr.data}
    r.b[0] = 1 // leaf
    c, mid := n.count(), n.count()/2
    for i := mid; i < c; i++ { // move the upper half
        r.setKey(i-mid, n.key(i))
        r.setVal(i-mid, n.val(i))
    }
    r.setCount(c - mid)
    n.setCount(mid)
    r.setNext(n.next()) // keep the leaf chain intact for range scans
    n.setNext(fr.id)
    return r.key(0), fr.id, true, nil // leaf split: separator is COPIED up
}

Leaf splits copy the separator up (the key stays in the leaf, because leaves hold all data); internal splits move the middle key up. When the root splits, a new root with two children is created and page 0 is updated — the only way the tree grows taller, which keeps every leaf at the same depth. Leaves are linked, so a range scan finds its first key with one descent and then follows next pointers.

Measured

1 M random uint64 keys inserted, then random lookups (Apple M1 Pro):

Buffer pool Lookup Page reads from the file per lookup
16 frames (64 KB) 1,412 ns 1.77
256 frames (1 MB) 949 ns 0.96
8,192 frames (32 MB; the whole 22 MB tree fits) 341 ns 0.001

The tree is 5,657 pages and 3 levels deep. With 256 frames the root and all ~25 internal pages stay cached (CLOCK keeps them because every lookup touches them), so a lookup misses only on the leaf: about one pread per lookup. The page reads here hit the OS page cache, which is why a miss costs ~0.6 µs rather than an SSD's ~50–100 µs; on a cold disk the gap between the rows would be two orders of magnitude.

Space efficiency depends on the insert order:

Inserts Bytes on disk per 16-byte entry Average leaf fill
Random keys 22.9 ~70%
Sequential keys 32.5 ~50%

Random inserts land in random leaves, and after a split both halves keep filling: the textbook steady state is ln 2 ≈ 69% full. Sequential inserts always go to the rightmost leaf; each split leaves a half-full left page that will never receive another key. Real engines special- case this: PostgreSQL splits the rightmost leaf unevenly (leaving the left page ~90% full per fillfactor), and SQLite has a fast path for appending at the end. Auto-increment primary keys are exactly this pattern — which is also why random UUIDv4 primary keys cause scattered page writes, while time-ordered keys (UUIDv7) keep inserts on one hot page.

What a real engine adds

Concern This tree Real engines
Durability Pages written back on eviction/close; a crash mid-split corrupts the tree WAL with page LSNs; redo on recovery (WAL); or copy-on-write pages (bbolt, LMDB) so the old tree stays valid until the meta page flips
Torn pages None Page checksums; PostgreSQL full-page writes, InnoDB doublewrite buffer
Concurrency One RWMutex for the whole tree Latch crabbing: hold a node's latch until the child is latched and known not to split; optimistic descent; B-link trees with right-sibling links (Lehman–Yao)
Deletes Not implemented Merge or redistribute underfull nodes, or leave them and rebuild (many engines never merge)
Variable-length keys No Slotted pages, prefix truncation, overflow pages

Latch crabbing, briefly: to insert, latch the root exclusively, latch the child, and if the child has room for one more entry (so it cannot split), release all latches above it. Most inserts hold only one or two latches at a time, so writers on different leaves proceed in parallel. Readers do the same with shared latches. This is what turns the single RWMutex here into a concurrent B+tree (see also Locking and Concurrency).

B+tree vs. LSM, from both implementations

B+tree (this page) LSM (the rest of this series)
Point read One root-to-leaf path; ~1 page read when internal nodes are cached Memtable + several tables; bloom filters keep it near one block read
Range scan Excellent: walk linked leaves Merge across all sources
Random write Read-modify-write a page (+ WAL) Append to WAL + memtable; pay later in compaction
Write amplification Page size / entry size per update (4 KB page for a 16-byte change), plus WAL Measured 2.2–6.6x here; 10–30x in leveled engines
Space ~50–70% page fill Near 100% after compaction, plus obsolete versions until compacted
Predictability Stable latency Background compaction causes stalls and latency spikes

Neither wins in general. B+trees suit read-heavy, latency-sensitive OLTP; LSMs suit write-heavy workloads and SSD lifetime (fewer random writes). The deciding factors are the workload's read/write mix, its access pattern, and which amplification (read, write, or space) it can least afford.

Common pitfall

Forgetting to unpin. A code path in the tree returns early on an error (or after finding a key) without calling Unpin. Each leak permanently pins one frame. Under normal load nothing happens for a while — the pool has spare frames — then Fetch starts failing with ErrNoFreeFrame, or in pools that wait for a free frame, every operation blocks forever. The failure appears far from the bug, after the pool runs out. Defenses: defer the unpin immediately after a successful Fetch (as insert does), count pins in tests and assert that every frame is unpinned when the tree is idle, and make the pool small in tests (this tree's model test uses 64 frames) so a leak fails quickly.

Review questions

  1. Why is a node implemented as a view over the page's bytes instead of a Go struct that is serialized?
  2. What does pinning protect against, and what happens if a code path forgets to unpin?
  3. Why does CLOCK approximate LRU at lower cost, and why did 256 frames already reduce lookups to about one page read?
  4. Why do sequential inserts leave leaves half full, and how do real engines avoid it?
  5. Explain latch crabbing. When can a writer release the latches above the current node?