B+ Tree
A high-fanout balanced tree that stores all data in the leaves and links them for range scans, standard in databases and filesystems.
Built for block storage
A B+ tree is a generalization of a binary search tree in which each node holds many keys and has many children, chosen so that a node fills one disk block or memory page. High fanout means the tree is very shallow, so a lookup touches only a handful of blocks, minimizing the expensive disk or SSD reads that dominate database and filesystem performance.
Leaves hold the data
In a B+ tree (unlike a plain B-tree) internal nodes store only keys for routing, while all records live in the leaves. The leaves are chained in a linked list, so a range query finds the start key by descending once and then walks the leaf chain sequentially, which is ideal for ordered scans and range predicates.
Balance rules
- Every node except the root holds between ceil(m/2)-1 and m-1 keys, where m is the order.
- All leaves are at the same depth, keeping height O(log_m n).
- Insertion splits a full node and pushes a separator up; deletion merges or borrows from siblings.
- Splits and merges propagate toward the root only when a node overflows or underflows.
Why high fanout matters
With order m around a few hundred, a tree of billions of keys is only three or four levels deep, so a point lookup is three or four block reads. The same shallow shape makes B+ trees cache-friendly and keeps the amortized cost of updates low even under heavy churn.
Where it appears
B+ trees are the default index structure in relational databases (the classic clustered index), in filesystems such as NTFS and many others, and in key-value stores. Log-structured merge trees are an alternative optimized for write-heavy workloads, trading read amplification for sequential writes.