Implementing a B+ Tree in Go: What Databases Actually Use
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-1keys and at most2t-1keys. - Every internal node with
nkeys has exactlyn+1children. - 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-1keys, 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, thenO(k)linked-list traversal forkresults. 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-1and2t-1keys. No node is too empty or too full. - Every internal node with
nkeys has exactlyn+1children. - 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.