B-Tree (ordered map) — Go
Topics: B-tree, balanced search tree, ordered map, range scan
Problem
Implement a B-tree ordered map of minimum degree t — the balanced, high-fanout tree behind
database indexes and filesystems. Every node holds between t-1 and 2t-1 keys; the tree stays
balanced by splitting full nodes rather than rotating.
func New(t int) *BTree
func (b *BTree) Get(key int) (int, bool)
func (b *BTree) Insert(key, val int)
func (b *BTree) Range(lo, hi int) []Pair // ascending, lo <= key <= hi
Insert adds or updates a key. The classic trick (CLRS): as you descend, split any full
child (2t-1 keys) before entering it — that guarantees there's always room — and split a full
root to grow the tree's height.Get walks down comparing within each node.Range returns the in-range pairs in ascending order (an in-order traversal).
New(2); Insert 50,10,30,70,20,60,40 ; Range(20,60) → keys [20,30,40,50,60]
Key concepts
- Split, don't rotate: a full node splits into two
t-1-key nodes with its median pushed up
into the parent — this keeps every leaf at the same depth.
- Split-on-descend: splitting full children on the way down means insertion never has to walk
back up.
- Why a B-tree: high fanout = shallow trees and cache/disk-friendly nodes, with ordered
iteration for free (unlike a hash map).
The node types, Pair, and New are provided; you implement Get, Insert, and Range.
Run
go test -v ./challenges/btree/go/
Sign in to submit your solution.