Implementing a B+ Tree in Go: What Databases Actually Use

Posted Mar 10, 2026 Updated Aug 21, 2026

By Amr Mubarak

28 min read

Why B+ Trees Exist

Your database has 50 million rows. You query by user ID. Without an index, the database reads every row until it finds yours. That’s a full table scan. It gets slower with every row you add.

So you build an index. The question is: what data structure?

Not a hash map. Hash maps are fast for exact lookups but useless for range queries. WHERE age BETWEEN 20 AND 30 needs something sorted.

Not a binary search tree. BSTs fall apart at scale. A BST with a million nodes can be 20 levels deep. Each level is a disk read. 20 disk reads per query. Disks are slow.

B-Trees solve the depth problem — they stay 3-4 levels deep even with millions of nodes. But the variant every real database actually uses is the B+ Tree. PostgreSQL, MySQL, SQLite, Oracle — they all use B+ Trees for indexes.

The difference matters. Let’s build one in Go.

B-Tree vs B+ Tree: The Key Difference

A standard B-Tree stores data in every node — internal nodes and leaves both hold (key, value) pairs. A B+ Tree changes two things:

1. Data lives only in leaf nodes. Internal nodes store only keys — they act as a routing layer. Every (key, value) pair is at a leaf.

2. Leaf nodes are linked together. Every leaf has a pointer to the next leaf, forming a sorted linked list across the entire bottom level of the tree.

B-Tree (data everywhere):
         [10:alice | 20:bob]
        /          |         \
 [5:carol|6:dave] [12:eve] [30:frank]

B+ Tree (data only in leaves, leaves linked):
         [10 | 20]              ← internal: keys only, no values
        /    |     \
 [5:carol]→[10:alice]→[20:bob]→[30:frank]→nil
  6:dave     12:eve

Why does this matter?

Range queries become a single linked-list traversal. Find the start of the range with a normal tree search, then walk the leaf linked list until the range ends. No backtracking. No re-entering the tree. PostgreSQL’s index range scans work exactly this way.

Internal nodes fit more keys. Without values, internal nodes are smaller. A smaller internal node means a higher branching factor — more children per node — which means a shallower tree. A shallower tree means fewer disk reads per lookup.

Full scans are efficient. Walk the leaf linked list from start to finish. No tree traversal needed.

Takeaway: B+ Trees store data only in leaves and link leaves together. Internal nodes are pure routing. Range queries become linked-list walks. This is why every database index is a B+ Tree, not a plain B-Tree.

What a B+ Tree Actually Is

Like a B-Tree, a B+ Tree has a minimum degree t:

Every non-root node has at least t-1 keys and at most 2t-1 keys.
Every internal node with n keys has exactly n+1 children.
All leaves are at the same depth.

The difference: internal nodes hold only keys (no values). Leaves hold (key, value) entries and a pointer to the next leaf.

The Node

In Go, internal nodes and leaf nodes have different responsibilities, but we represent both with one struct and use isLeaf to distinguish them:

  
type Entry[K any, V any] struct {
    Key   K
    Value V
}

type Node[K any, V any] struct {
    keys     []K           // routing keys (internal) or entry keys (leaf)
    values   []V           // only used in leaf nodes
    children []*Node[K, V] // only used in internal nodes
    next     *Node[K, V]   // only used in leaf nodes — points to next leaf
    isLeaf   bool
}

func newNode[K any, V any](isLeaf bool) *Node[K, V] {
    return &Node[K, V]{isLeaf: isLeaf}
}

Internal nodes: keys holds routing keys, children holds child pointers. values and next are unused.

Leaf nodes: keys and values hold (key, value) pairs in parallel slices. next points to the next leaf. children is unused.

This parallel-slice layout for leaves (keys[i] matches values[i]) keeps the leaf structure cache-friendly and easy to work with.

The Tree

  
type Comparator[K any] func(a, b K) int

type BPlusTree[K any, V any] struct {
    root       *Node[K, V]
    t          int // minimum degree
    comparator Comparator[K]
}

func NewBPlusTree[K any, V any](t int, cmp Comparator[K]) *BPlusTree[K, V] {
    return &BPlusTree[K, V]{
        root:       newNode[K, V](true), // start as empty leaf
        t:          t,
        comparator: cmp,
    }
}

We start with an empty root that is also a leaf. With t = 3, nodes hold 2 to 5 keys. The comparator makes the tree work with any ordered key type — pass func(a, b int) int { return a - b } for integers, strings.Compare for strings.

Search

Search walks down internal nodes using keys as routing guides, then scans the leaf:

  
func (tree *BPlusTree[K, V]) Search(key K) (V, bool) {
    leaf := tree.findLeaf(key)
    for i, k := range leaf.keys {
        cmp := tree.comparator(key, k)
        if cmp == 0 {
            return leaf.values[i], true
        }
        if cmp < 0 {
            break
        }
    }
    var zero V
    return zero, false
}

func (tree *BPlusTree[K, V]) findLeaf(key K) *Node[K, V] {
    node := tree.root
    for !node.isLeaf {
        i := len(node.keys) - 1
        // find the rightmost key <= search key
        // that determines which child to descend into
        idx := 0
        for idx < len(node.keys) && tree.comparator(key, node.keys[idx]) >= 0 {
            idx++
        }
        node = node.children[idx]
    }
    return node
}

findLeaf descends internal nodes: at each node, find the first key strictly greater than the search key — the corresponding child is the subtree that could contain our target. Once we reach a leaf, we scan its keys linearly for an exact match.

The B+ Tree difference is visible here: every search ends at a leaf. Internal nodes only steer. There’s no “found it in an internal node” shortcut like in a plain B-Tree.

Range Queries: Where B+ Trees Shine

This is the operation that justifies the entire B+ Tree design:

  
// RangeSearch returns all (key, value) pairs where start <= key <= end.
func (tree *BPlusTree[K, V]) RangeSearch(start, end K) []Entry[K, V] {
    var results []Entry[K, V]

    // Find the leaf where `start` would live
    leaf := tree.findLeaf(start)

    // Walk the leaf linked list until we pass `end`
    for leaf != nil {
        for i, k := range leaf.keys {
            cmp := tree.comparator(k, start)
            if cmp < 0 {
                continue // before the range start
            }
            if tree.comparator(k, end) > 0 {
                return results // past the range end
            }
            results = append(results, Entry[K, V]{Key: k, Value: leaf.values[i]})
        }
        leaf = leaf.next // follow the linked list
    }
    return results
}

Two phases: find the starting leaf with a normal O(log n) tree search, then walk the linked list until we’ve passed end. No re-entering the tree. No stack unwinding. Just pointer following.

This is exactly what PostgreSQL does for WHERE created_at BETWEEN '2024-01-01' AND '2024-01-31' on a B+ Tree index.

Insertion: The Hard Part

Insertion always targets a leaf. Leaves can fill up. When a node has 2t-1 keys, it’s full and must be split before inserting.

We use the proactive split approach: on the way down to the target leaf, split any full nodes we encounter. This means we never need to walk back up the tree.

Splitting Nodes

Splitting is different for internal nodes and leaf nodes — and this is the most important B+ Tree implementation detail.

Splitting a leaf node: the middle key is copied up to the parent (it stays in the leaf AND appears in the parent as a routing key). Both halves of the split leaf remain valid with their data intact.

Splitting an internal node: the middle key is pushed up to the parent (it leaves the internal node — internal nodes hold no data, so the key has no reason to stay).

  
// splitLeaf splits a full leaf node.
// The middle key is COPIED to the parent — it stays in the right leaf.
func (tree *BPlusTree[K, V]) splitLeaf(parent *Node[K, V], i int) {
    t := tree.t
    full := parent.children[i]
    newLeaf := newNode[K, V](true)

    mid := t - 1 // index of middle key

    // Right half goes to the new leaf
    newLeaf.keys = append(newLeaf.keys, full.keys[mid:]...)
    newLeaf.values = append(newLeaf.values, full.values[mid:]...)

    // Left half stays in the original leaf
    full.keys = full.keys[:mid]
    full.values = full.values[:mid]

    // Wire up the linked list: full → newLeaf → whatever was after full
    newLeaf.next = full.next
    full.next = newLeaf

    // The first key of the new (right) leaf is COPIED up to the parent
    // It stays in newLeaf AND appears in parent as a routing key
    parent.keys = append(parent.keys, *new(K))
    copy(parent.keys[i+1:], parent.keys[i:])
    parent.keys[i] = newLeaf.keys[0]

    // Insert newLeaf as child i+1 of parent
    parent.children = append(parent.children, nil)
    copy(parent.children[i+2:], parent.children[i+1:])
    parent.children[i+1] = newLeaf
}

// splitInternal splits a full internal node.
// The middle key is PUSHED up to the parent — it does NOT stay in either child.
func (tree *BPlusTree[K, V]) splitInternal(parent *Node[K, V], i int) {
    t := tree.t
    full := parent.children[i]
    newInternal := newNode[K, V](false)

    mid := t - 1 // index of middle key

    // Middle key moves UP to parent (pushed, not copied)
    midKey := full.keys[mid]

    // Right half of keys goes to new internal node (excluding the middle key)
    newInternal.keys = append(newInternal.keys, full.keys[mid+1:]...)
    newInternal.children = append(newInternal.children, full.children[mid+1:]...)

    // Left half stays in original internal node
    full.keys = full.keys[:mid]
    full.children = full.children[:mid+1]

    // Middle key is PUSHED up to parent
    parent.keys = append(parent.keys, *new(K))
    copy(parent.keys[i+1:], parent.keys[i:])
    parent.keys[i] = midKey

    // Insert newInternal as child i+1 of parent
    parent.children = append(parent.children, nil)
    copy(parent.children[i+2:], parent.children[i+1:])
    parent.children[i+1] = newInternal
}

The copy-vs-push distinction is the B+ Tree’s defining split behavior. In a plain B-Tree, every split pushes the middle key up. In a B+ Tree, leaf splits copy the middle key (because leaf data must stay complete) while internal splits push the middle key (because internal nodes carry no data anyway).

Inserting Into a Non-Full Node

  
func (tree *BPlusTree[K, V]) insertNonFull(node *Node[K, V], key K, value V) {
    if node.isLeaf {
        // Insert into the leaf in sorted order
        i := len(node.keys)
        node.keys = append(node.keys, *new(K))
        node.values = append(node.values, *new(V))
        for i > 0 && tree.comparator(key, node.keys[i-1]) < 0 {
            node.keys[i] = node.keys[i-1]
            node.values[i] = node.values[i-1]
            i--
        }
        // If key already exists, update value in place (upsert)
        if i > 0 && tree.comparator(key, node.keys[i-1]) == 0 {
            node.keys = node.keys[:len(node.keys)-1]
            node.values = node.values[:len(node.values)-1]
            node.values[i-1] = value
            return
        }
        node.keys[i] = key
        node.values[i] = value
        return
    }

    // Find which child to descend into
    i := 0
    for i < len(node.keys) && tree.comparator(key, node.keys[i]) >= 0 {
        i++
    }

    // Proactively split the child if it's full
    if len(node.children[i].keys) == 2*tree.t-1 {
        if node.children[i].isLeaf {
            tree.splitLeaf(node, i)
        } else {
            tree.splitInternal(node, i)
        }
        // After the split, the middle key moved up to node.keys[i].
        // Determine which child to descend into.
        if tree.comparator(key, node.keys[i]) >= 0 {
            i++
        }
    }

    tree.insertNonFull(node.children[i], key, value)
}

The Public Insert

  
func (tree *BPlusTree[K, V]) Insert(key K, value V) {
    root := tree.root

    // Special case: root is full
    if len(root.keys) == 2*tree.t-1 {
        newRoot := newNode[K, V](false)
        newRoot.children = append(newRoot.children, tree.root)
        tree.root = newRoot

        // Split the old root — use the correct split for its type
        if root.isLeaf {
            tree.splitLeaf(newRoot, 0)
        } else {
            tree.splitInternal(newRoot, 0)
        }
        tree.insertNonFull(newRoot, key, value)
    } else {
        tree.insertNonFull(root, key, value)
    }
}

If the root is full, we create a new empty root with the old root as its only child, then split the old root. Now the new root has one routing key and two children. The tree grows by one level, uniformly. This is the only way a B+ Tree grows taller.

Deletion: The Annoying Part

Deletion in a B+ Tree is slightly different from a plain B-Tree because:

Data only exists in leaves — we always delete from a leaf, never from an internal node.
Internal nodes may hold copies of deleted keys — if we delete the smallest key of a leaf, the parent routing key that points to it becomes stale. We may need to update it.
Underflow handling — after deletion, if a leaf has fewer than t-1 keys, borrow from a sibling or merge.

Finding Predecessor and Successor in Leaves

  
// getLeafPredecessor returns the largest key in the left subtree of children[i].
func (tree *BPlusTree[K, V]) getLeafPredecessor(node *Node[K, V], i int) K {
    curr := node.children[i]
    for !curr.isLeaf {
        curr = curr.children[len(curr.children)-1]
    }
    return curr.keys[len(curr.keys)-1]
}

// getLeafSuccessor returns the smallest key in the right subtree of children[i+1].
func (tree *BPlusTree[K, V]) getLeafSuccessor(node *Node[K, V], i int) K {
    curr := node.children[i+1]
    for !curr.isLeaf {
        curr = curr.children[0]
    }
    return curr.keys[0]
}

Borrowing from Siblings

  
func (tree *BPlusTree[K, V]) borrowFromPrevLeaf(parent *Node[K, V], i int) {
    child := parent.children[i]
    sibling := parent.children[i-1]

    // Move last entry of sibling to front of child
    child.keys = append([]K{sibling.keys[len(sibling.keys)-1]}, child.keys...)
    child.values = append([]V{sibling.values[len(sibling.values)-1]}, child.values...)

    sibling.keys = sibling.keys[:len(sibling.keys)-1]
    sibling.values = sibling.values[:len(sibling.values)-1]

    // Update parent routing key — now points to child's new first key
    parent.keys[i-1] = child.keys[0]
}

func (tree *BPlusTree[K, V]) borrowFromNextLeaf(parent *Node[K, V], i int) {
    child := parent.children[i]
    sibling := parent.children[i+1]

    // Move first entry of sibling to end of child
    child.keys = append(child.keys, sibling.keys[0])
    child.values = append(child.values, sibling.values[0])

    sibling.keys = sibling.keys[1:]
    sibling.values = sibling.values[1:]

    // Update parent routing key — sibling's new first key
    parent.keys[i] = sibling.keys[0]
}

func (tree *BPlusTree[K, V]) borrowFromPrevInternal(parent *Node[K, V], i int) {
    child := parent.children[i]
    sibling := parent.children[i-1]

    // Parent key drops into child, sibling's last key rises to parent
    child.keys = append([]K{parent.keys[i-1]}, child.keys...)
    child.children = append([]*Node[K, V]{sibling.children[len(sibling.children)-1]}, child.children...)

    parent.keys[i-1] = sibling.keys[len(sibling.keys)-1]

    sibling.keys = sibling.keys[:len(sibling.keys)-1]
    sibling.children = sibling.children[:len(sibling.children)-1]
}

func (tree *BPlusTree[K, V]) borrowFromNextInternal(parent *Node[K, V], i int) {
    child := parent.children[i]
    sibling := parent.children[i+1]

    // Parent key drops into child, sibling's first key rises to parent
    child.keys = append(child.keys, parent.keys[i])
    child.children = append(child.children, sibling.children[0])

    parent.keys[i] = sibling.keys[0]

    sibling.keys = sibling.keys[1:]
    sibling.children = sibling.children[1:]
}

Merging Nodes

  
// mergeLeaves merges children[i] and children[i+1] into children[i].
func (tree *BPlusTree[K, V]) mergeLeaves(parent *Node[K, V], i int) {
    left := parent.children[i]
    right := parent.children[i+1]

    // Merge right into left
    left.keys = append(left.keys, right.keys...)
    left.values = append(left.values, right.values...)

    // Fix linked list: skip over right
    left.next = right.next

    // Remove routing key and right child from parent
    parent.keys = append(parent.keys[:i], parent.keys[i+1:]...)
    parent.children = append(parent.children[:i+1], parent.children[i+2:]...)
}

// mergeInternals merges children[i] and children[i+1] into children[i].
// The separator key from parent drops down into the merged node.
func (tree *BPlusTree[K, V]) mergeInternals(parent *Node[K, V], i int) {
    left := parent.children[i]
    right := parent.children[i+1]

    // Separator key drops from parent into left
    left.keys = append(left.keys, parent.keys[i])
    left.keys = append(left.keys, right.keys...)
    left.children = append(left.children, right.children...)

    // Remove separator key and right child from parent
    parent.keys = append(parent.keys[:i], parent.keys[i+1:]...)
    parent.children = append(parent.children[:i+1], parent.children[i+2:]...)
}

Fill: Ensuring a Child Has Enough Keys Before Descending

  
func (tree *BPlusTree[K, V]) fill(parent *Node[K, V], i int) {
    t := tree.t
    child := parent.children[i]

    if i > 0 && len(parent.children[i-1].keys) >= t {
        if child.isLeaf {
            tree.borrowFromPrevLeaf(parent, i)
        } else {
            tree.borrowFromPrevInternal(parent, i)
        }
    } else if i < len(parent.keys) && len(parent.children[i+1].keys) >= t {
        if child.isLeaf {
            tree.borrowFromNextLeaf(parent, i)
        } else {
            tree.borrowFromNextInternal(parent, i)
        }
    } else {
        // Neither sibling can lend — merge
        if i < len(parent.keys) {
            if child.isLeaf {
                tree.mergeLeaves(parent, i)
            } else {
                tree.mergeInternals(parent, i)
            }
        } else {
            if parent.children[i-1].isLeaf {
                tree.mergeLeaves(parent, i-1)
            } else {
                tree.mergeInternals(parent, i-1)
            }
        }
    }
}

The Delete Method

  
func (tree *BPlusTree[K, V]) Delete(key K) {
    if len(tree.root.keys) == 0 {
        return
    }
    tree.delete(tree.root, key)

    // If root is now empty and has children, shrink the tree
    if len(tree.root.keys) == 0 && !tree.root.isLeaf {
        tree.root = tree.root.children[0]
    }
}

func (tree *BPlusTree[K, V]) delete(node *Node[K, V], key K) {
    t := tree.t

    if node.isLeaf {
        // Find and remove the key from the leaf
        for i, k := range node.keys {
            if tree.comparator(key, k) == 0 {
                node.keys = append(node.keys[:i], node.keys[i+1:]...)
                node.values = append(node.values[:i], node.values[i+1:]...)
                return
            }
        }
        return // key not found
    }

    // Find which child subtree might contain the key
    i := 0
    for i < len(node.keys) && tree.comparator(key, node.keys[i]) >= 0 {
        i++
    }

    isLastChild := i == len(node.keys)

    // Ensure the child we're descending into has enough keys
    if len(node.children[i].keys) < t {
        tree.fill(node, i)
        // After fill, indices may have shifted due to merge
        if isLastChild && i > len(node.keys) {
            i--
        }
    }

    tree.delete(node.children[i], key)

    // After deletion, update stale routing keys in internal nodes.
    // If we deleted the minimum key of a subtree, the routing key
    // pointing to that subtree may now be stale.
    if !node.isLeaf && i < len(node.keys) {
        node.keys[i] = tree.getLeafSuccessor(node, i)
    }
}

The routing key update at the end is the B+ Tree detail that plain B-Tree implementations don’t need. Because internal keys in a B+ Tree are copies of leaf keys (not the actual data), deleting from a leaf can leave a stale routing key in a parent. We refresh it after every descent.

Putting It All Together

Here is the complete implementation:

  
package bplustree

import "strings"

// Comparator defines key ordering. Return negative if a < b, zero if a == b, positive if a > b.
type Comparator[K any] func(a, b K) int

type Entry[K any, V any] struct {
    Key   K
    Value V
}

type Node[K any, V any] struct {
    keys     []K
    values   []V
    children []*Node[K, V]
    next     *Node[K, V]
    isLeaf   bool
}

func newNode[K any, V any](isLeaf bool) *Node[K, V] {
    return &Node[K, V]{isLeaf: isLeaf}
}

type BPlusTree[K any, V any] struct {
    root       *Node[K, V]
    t          int
    comparator Comparator[K]
}

func NewBPlusTree[K any, V any](t int, cmp Comparator[K]) *BPlusTree[K, V] {
    return &BPlusTree[K, V]{
        root:       newNode[K, V](true),
        t:          t,
        comparator: cmp,
    }
}

func (tree *BPlusTree[K, V]) findLeaf(key K) *Node[K, V] {
    node := tree.root
    for !node.isLeaf {
        i := 0
        for i < len(node.keys) && tree.comparator(key, node.keys[i]) >= 0 {
            i++
        }
        node = node.children[i]
    }
    return node
}

func (tree *BPlusTree[K, V]) Search(key K) (V, bool) {
    leaf := tree.findLeaf(key)
    for i, k := range leaf.keys {
        cmp := tree.comparator(key, k)
        if cmp == 0 {
            return leaf.values[i], true
        }
        if cmp < 0 {
            break
        }
    }
    var zero V
    return zero, false
}

func (tree *BPlusTree[K, V]) RangeSearch(start, end K) []Entry[K, V] {
    var results []Entry[K, V]
    leaf := tree.findLeaf(start)
    for leaf != nil {
        for i, k := range leaf.keys {
            if tree.comparator(k, start) < 0 {
                continue
            }
            if tree.comparator(k, end) > 0 {
                return results
            }
            results = append(results, Entry[K, V]{Key: k, Value: leaf.values[i]})
        }
        leaf = leaf.next
    }
    return results
}

func (tree *BPlusTree[K, V]) splitLeaf(parent *Node[K, V], i int) {
    t := tree.t
    full := parent.children[i]
    newLeaf := newNode[K, V](true)
    mid := t - 1

    newLeaf.keys = append(newLeaf.keys, full.keys[mid:]...)
    newLeaf.values = append(newLeaf.values, full.values[mid:]...)
    full.keys = full.keys[:mid]
    full.values = full.values[:mid]

    newLeaf.next = full.next
    full.next = newLeaf

    parent.keys = append(parent.keys, *new(K))
    copy(parent.keys[i+1:], parent.keys[i:])
    parent.keys[i] = newLeaf.keys[0]

    parent.children = append(parent.children, nil)
    copy(parent.children[i+2:], parent.children[i+1:])
    parent.children[i+1] = newLeaf
}

func (tree *BPlusTree[K, V]) splitInternal(parent *Node[K, V], i int) {
    t := tree.t
    full := parent.children[i]
    newInternal := newNode[K, V](false)
    mid := t - 1

    midKey := full.keys[mid]
    newInternal.keys = append(newInternal.keys, full.keys[mid+1:]...)
    newInternal.children = append(newInternal.children, full.children[mid+1:]...)
    full.keys = full.keys[:mid]
    full.children = full.children[:mid+1]

    parent.keys = append(parent.keys, *new(K))
    copy(parent.keys[i+1:], parent.keys[i:])
    parent.keys[i] = midKey

    parent.children = append(parent.children, nil)
    copy(parent.children[i+2:], parent.children[i+1:])
    parent.children[i+1] = newInternal
}

func (tree *BPlusTree[K, V]) insertNonFull(node *Node[K, V], key K, value V) {
    if node.isLeaf {
        i := len(node.keys)
        node.keys = append(node.keys, *new(K))
        node.values = append(node.values, *new(V))
        for i > 0 && tree.comparator(key, node.keys[i-1]) < 0 {
            node.keys[i] = node.keys[i-1]
            node.values[i] = node.values[i-1]
            i--
        }
        if i > 0 && tree.comparator(key, node.keys[i-1]) == 0 {
            node.keys = node.keys[:len(node.keys)-1]
            node.values = node.values[:len(node.values)-1]
            node.values[i-1] = value
            return
        }
        node.keys[i] = key
        node.values[i] = value
        return
    }

    i := 0
    for i < len(node.keys) && tree.comparator(key, node.keys[i]) >= 0 {
        i++
    }

    if len(node.children[i].keys) == 2*tree.t-1 {
        if node.children[i].isLeaf {
            tree.splitLeaf(node, i)
        } else {
            tree.splitInternal(node, i)
        }
        if tree.comparator(key, node.keys[i]) >= 0 {
            i++
        }
    }

    tree.insertNonFull(node.children[i], key, value)
}

func (tree *BPlusTree[K, V]) Insert(key K, value V) {
    root := tree.root
    if len(root.keys) == 2*tree.t-1 {
        newRoot := newNode[K, V](false)
        newRoot.children = append(newRoot.children, tree.root)
        tree.root = newRoot
        if root.isLeaf {
            tree.splitLeaf(newRoot, 0)
        } else {
            tree.splitInternal(newRoot, 0)
        }
        tree.insertNonFull(newRoot, key, value)
    } else {
        tree.insertNonFull(root, key, value)
    }
}

func (tree *BPlusTree[K, V]) getLeafSuccessor(node *Node[K, V], i int) K {
    curr := node.children[i+1]
    for !curr.isLeaf {
        curr = curr.children[0]
    }
    return curr.keys[0]
}

func (tree *BPlusTree[K, V]) borrowFromPrevLeaf(parent *Node[K, V], i int) {
    child := parent.children[i]
    sibling := parent.children[i-1]
    child.keys = append([]K{sibling.keys[len(sibling.keys)-1]}, child.keys...)
    child.values = append([]V{sibling.values[len(sibling.values)-1]}, child.values...)
    sibling.keys = sibling.keys[:len(sibling.keys)-1]
    sibling.values = sibling.values[:len(sibling.values)-1]
    parent.keys[i-1] = child.keys[0]
}

func (tree *BPlusTree[K, V]) borrowFromNextLeaf(parent *Node[K, V], i int) {
    child := parent.children[i]
    sibling := parent.children[i+1]
    child.keys = append(child.keys, sibling.keys[0])
    child.values = append(child.values, sibling.values[0])
    sibling.keys = sibling.keys[1:]
    sibling.values = sibling.values[1:]
    parent.keys[i] = sibling.keys[0]
}

func (tree *BPlusTree[K, V]) borrowFromPrevInternal(parent *Node[K, V], i int) {
    child := parent.children[i]
    sibling := parent.children[i-1]
    child.keys = append([]K{parent.keys[i-1]}, child.keys...)
    child.children = append([]*Node[K, V]{sibling.children[len(sibling.children)-1]}, child.children...)
    parent.keys[i-1] = sibling.keys[len(sibling.keys)-1]
    sibling.keys = sibling.keys[:len(sibling.keys)-1]
    sibling.children = sibling.children[:len(sibling.children)-1]
}

func (tree *BPlusTree[K, V]) borrowFromNextInternal(parent *Node[K, V], i int) {
    child := parent.children[i]
    sibling := parent.children[i+1]
    child.keys = append(child.keys, parent.keys[i])
    child.children = append(child.children, sibling.children[0])
    parent.keys[i] = sibling.keys[0]
    sibling.keys = sibling.keys[1:]
    sibling.children = sibling.children[1:]
}

func (tree *BPlusTree[K, V]) mergeLeaves(parent *Node[K, V], i int) {
    left := parent.children[i]
    right := parent.children[i+1]
    left.keys = append(left.keys, right.keys...)
    left.values = append(left.values, right.values...)
    left.next = right.next
    parent.keys = append(parent.keys[:i], parent.keys[i+1:]...)
    parent.children = append(parent.children[:i+1], parent.children[i+2:]...)
}

func (tree *BPlusTree[K, V]) mergeInternals(parent *Node[K, V], i int) {
    left := parent.children[i]
    right := parent.children[i+1]
    left.keys = append(left.keys, parent.keys[i])
    left.keys = append(left.keys, right.keys...)
    left.children = append(left.children, right.children...)
    parent.keys = append(parent.keys[:i], parent.keys[i+1:]...)
    parent.children = append(parent.children[:i+1], parent.children[i+2:]...)
}

func (tree *BPlusTree[K, V]) fill(parent *Node[K, V], i int) {
    t := tree.t
    child := parent.children[i]
    if i > 0 && len(parent.children[i-1].keys) >= t {
        if child.isLeaf {
            tree.borrowFromPrevLeaf(parent, i)
        } else {
            tree.borrowFromPrevInternal(parent, i)
        }
    } else if i < len(parent.keys) && len(parent.children[i+1].keys) >= t {
        if child.isLeaf {
            tree.borrowFromNextLeaf(parent, i)
        } else {
            tree.borrowFromNextInternal(parent, i)
        }
    } else {
        if i < len(parent.keys) {
            if child.isLeaf {
                tree.mergeLeaves(parent, i)
            } else {
                tree.mergeInternals(parent, i)
            }
        } else {
            if parent.children[i-1].isLeaf {
                tree.mergeLeaves(parent, i-1)
            } else {
                tree.mergeInternals(parent, i-1)
            }
        }
    }
}

func (tree *BPlusTree[K, V]) delete(node *Node[K, V], key K) {
    t := tree.t
    if node.isLeaf {
        for i, k := range node.keys {
            if tree.comparator(key, k) == 0 {
                node.keys = append(node.keys[:i], node.keys[i+1:]...)
                node.values = append(node.values[:i], node.values[i+1:]...)
                return
            }
        }
        return
    }

    i := 0
    for i < len(node.keys) && tree.comparator(key, node.keys[i]) >= 0 {
        i++
    }

    isLastChild := i == len(node.keys)
    if len(node.children[i].keys) < t {
        tree.fill(node, i)
        if isLastChild && i > len(node.keys) {
            i--
        }
    }

    tree.delete(node.children[i], key)

    if !node.isLeaf && i < len(node.keys) {
        node.keys[i] = tree.getLeafSuccessor(node, i)
    }
}

func (tree *BPlusTree[K, V]) Delete(key K) {
    if len(tree.root.keys) == 0 {
        return
    }
    tree.delete(tree.root, key)
    if len(tree.root.keys) == 0 && !tree.root.isLeaf {
        tree.root = tree.root.children[0]
    }
}

// Traverse prints the tree level by level for debugging.
func (tree *BPlusTree[K, V]) Traverse() {
    if tree.root == nil {
        return
    }
    queue := []*Node[K, V]{tree.root}
    for len(queue) > 0 {
        next := []*Node[K, V]{}
        for _, node := range queue {
            if node.isLeaf {
                print("[leaf:")
                for i, k := range node.keys {
                    if i > 0 {
                        print(" ")
                    }
                    print(k, ":", node.values[i])
                }
                print("] ")
            } else {
                print("[internal:")
                for i, k := range node.keys {
                    if i > 0 {
                        print(" ")
                    }
                    print(k)
                }
                print("] ")
                next = append(next, node.children...)
            }
        }
        println()
        queue = next
    }
}

Run it:

  
func main() {
    // Integer keys, string values — like a user ID → username index
    tree := NewBPlusTree[int, string](3, func(a, b int) int { return a - b })

    tree.Insert(10, "alice")
    tree.Insert(20, "bob")
    tree.Insert(5,  "carol")
    tree.Insert(6,  "dave")
    tree.Insert(12, "eve")
    tree.Insert(30, "frank")
    tree.Insert(7,  "grace")
    tree.Insert(17, "heidi")

    tree.Traverse()
    // [internal:7 17]
    //   [leaf:5:carol 6:dave] [leaf:7:grace 10:alice 12:eve] [leaf:17:heidi 20:bob 30:frank]
    //   (leaves are linked: 5,6 → 7,10,12 → 17,20,30 → nil)

    v, ok := tree.Search(17)
    fmt.Println(v, ok) // heidi true

    v, ok = tree.Search(99)
    fmt.Println(v, ok) // "" false

    // Range query — the B+ Tree's killer feature
    results := tree.RangeSearch(6, 17)
    for _, e := range results {
        fmt.Printf("%d:%s ", e.Key, e.Value)
    }
    // 6:dave 7:grace 10:alice 12:eve 17:heidi

    // Upsert — update an existing key
    tree.Insert(17, "hannah")
    v, _ = tree.Search(17)
    fmt.Println(v) // hannah

    tree.Delete(6)
    tree.Delete(20)
    tree.Traverse()

    // String keys — just change the comparator
    strTree := NewBPlusTree[string, int](3, strings.Compare)
    strTree.Insert("apple", 1)
    strTree.Insert("banana", 2)
    strTree.Insert("cherry", 3)
    v2, _ := strTree.Search("banana")
    fmt.Println(v2) // 2
}

What You Actually Have

A generic BPlusTree[K, V] in Go with any comparable key type, map semantics (upserts), and the linked leaf list that makes range queries efficient.

The key differences from a plain B-Tree:

Splits behave differently for leaves vs internal nodes. Leaf splits copy the middle key up. Internal splits push it up. Getting this wrong produces a tree that loses data.
Range queries use the leaf linked list. One O(log n) search to find the start, then O(k) linked-list traversal for k results. No tree re-entry.
Routing key updates on deletion. After deleting from a leaf, stale routing keys in parent internal nodes need refreshing. A plain B-Tree doesn’t need this because internal nodes carry the actual data.

The invariants that keep the tree correct:

Every non-root node has between t-1 and 2t-1 keys. No node is too empty or too full.
Every internal node with n keys has exactly n+1 children.
All leaves are at the same depth. Every search takes the same number of steps.
Every leaf is reachable via the linked list. Range queries are complete.

That’s it. It’s not magic. It’s just a sorted tree that stores its data at the bottom and threads its leaves together — which happens to be exactly what every database index does.

Database Internals

This post is licensed under CC BY 4.0 by the author.