You put an index of user IDs in a binary search tree because the slide said search is O(log n). In RAM, twenty comparisons are noise. You then persist each node as its own disk page. Twenty random reads for one lookup. The database did not invent a faster comparison. It packed a hundred keys into one page so one read throws away most of the remaining tree.
A B-tree is a search tree with fat nodes — many keys, many children — sized so one disk page is one hop. Height stays tiny because fanout is huge, not because the code is cleverer than a BST. All leaves sit at the same depth: the tree grows by splitting the root, not by dangling a spine.
This post is the layout: order, search, split, merge, why a BST is the wrong shape for disk, and a B+ variant that keeps values in linked leaves. Height, worst-case vs amortized, and “what operation is hot” live on the Data Structures Roadmap. We will not re-lecture them here.
The bill is a disk hop, not a comparison
A BST comparison is a few CPU cycles. A disk page read is milliseconds — or a network round-trip if the page is not in cache. Once the expensive unit is a page, a node that holds one key is a wasted hop: you paid for 4 KiB and used eight bytes.
A B-tree node is that page. Fill it with keys and child pointers. One I/O decides among dozens or hundreds of branches instead of two.
n ≈ 1_000_000 keys
BST, one key per node (and one node per page):
height ≈ log2(n) ≈ 20 — up to 20 page reads, root to leaf
B-tree, ~100 children per node:
height ≈ log100(n) ≈ 3 — 3 page reads, root to leafSame n. Same “log height.” Different base. That is the whole argument. Filesystems (directory indexes, extent maps) make the same bet: the expensive move is a block read, so the node should be a block.
Note: Real engines add a buffer pool so hot pages stay in RAM. The shape is still a B-tree. This post does not teach caching, WAL, or latch coupling.
Order: how wide is a node
Two textbooks, two names. This post uses Knuth’s order m: a node has at most m children and at most m − 1 keys. CLRS talks about a minimum degree t instead (max 2t children). Same machine. Pick one sentence and keep it.
A B-tree of order m also keeps nodes dense:
- Every node except the root is at least about half full (
ceil(m / 2)children on internal nodes). - The root has at least two children unless the tree is a single leaf.
- All leaves are at the same depth.
A teaching node is an array of keys, an array of children, and a leaf flag. Values can ride next to keys in a classic B-tree; they do not change the walk:
final class BTreeNode {
final int[] keys;
final BTreeNode[] children;
int keyCount;
boolean leaf;
BTreeNode(int order, boolean leaf) {
this.keys = new int[order - 1];
this.children = new BTreeNode[order];
this.leaf = leaf;
}
}order is usually chosen so one node fills a page: 4 KiB of keys and pointers, not “5 because the diagram fits on a slide.” Order 5 is for pictures. Production fanout is tens to hundreds.
Search walks keys inside a node, then one child
Inside a node the keys are sorted. Find the first key that is not smaller than the target. Equal — found. Otherwise take the child in that gap. A leaf with no match means the key is absent.
boolean contains(BTreeNode node, int key) {
while (true) {
int i = 0;
while (i < node.keyCount && key > node.keys[i]) {
i++;
}
if (i < node.keyCount && key == node.keys[i]) {
return true;
}
if (node.leaf) {
return false;
}
node = node.children[i];
}
}Each iteration is one node — on disk, one page. The inner while is a scan of a handful of integers already in that page (or a binary search of those integers). You do not follow a pointer per comparison the way a BST does.
Walk this order-5 tree (max 4 keys per node):
[ 20 | 50 ]
/ | \
[10|15] [25|30] [60|80]contains(30): 30 is between 20 and 50, so take the middle child. That leaf holds 25, 30. Found. Two nodes. A BST of the same keys would have been taller and would have jumped to a new node on almost every comparison.
Insert splits; the tree grows at the root
Insert searches to a leaf and writes the key in sorted order. If the leaf still has a free slot, you are done. If it is full, split.
Take the sorted keys (including the new one), pick the median, keep the left half in the old node, put the right half in a new sibling, and promote the median into the parent. The parent may now be full. Split it the same way. If the root splits, allocate a new root with one key and two children. Height grows by one — at the top. Leaves stay aligned.
A full order-5 node has four keys. Insert 25:
Before: [10 | 20 | 30 | 40] (full)
Insert 25 → 10, 20, 25, 30, 40
Median 25 goes up.
Left: [10 | 20] Right: [30 | 40]
Parent gains the key 25 and a pointer to the new right node.The split of the key array is the whole idea:
record Split(int[] left, int promoted, int[] right) {}
Split splitKeys(int[] sortedIncludingNew) {
int mid = sortedIncludingNew.length / 2;
return new Split(
Arrays.copyOfRange(sortedIncludingNew, 0, mid),
sortedIncludingNew[mid],
Arrays.copyOfRange(sortedIncludingNew, mid + 1, sortedIncludingNew.length));
}left stays in the old node. right is the new sibling. promoted is the separator the parent stores. No rotations. No “unbalanced because the inserts were sorted.” Sorted inserts fill a leaf, then split it, then fill the next leaf. The tree stays short because nodes stay wide and splits propagate upward.
Height increases only when the root splits. That is why a B-tree does not degenerate into a linked list under sequential IDs. The BST failure mode does not apply here.
Delete merges, or borrows first
Delete is search, then remove the key. If the key lives in an internal node, replace it with a neighbor from a leaf (the same successor idea as a BST), then delete that leaf copy. The interesting part is occupancy.
If a node drops below the minimum number of keys, try to borrow from a sibling: rotate a key through the parent so both nodes stay legal. If the sibling is already at minimum, merge: glue the two nodes and pull the separator down from the parent. The parent may now underflow. Repeat. If the root loses its last key, the remaining child becomes the new root and height shrinks by one.
Underflow after deleting 15 (order 5, min 2 keys):
Parent: [ 20 | 50 ]
Left leaf: [10] — too empty
Right leaf: [25 | 30]
Borrow: parent 20 moves down, 25 moves up.
Parent: [ 25 | 50 ]
Left leaf: [10 | 20]
Right leaf: [30]If the right leaf had been [25] only, borrow would fail and you would merge 10, the separator 20, and 25 into one leaf, then drop 20 from the parent.
You do not need a production delete in Java to see the bill: delete is still one root-to-leaf walk plus a local fix that may walk back toward the root. Cost is O(height) page writes, and height is small.
Do not leave tombstones in a teaching B-tree unless you also compact. Occupancy is the invariant that keeps nodes page-sized and the height honest.
Why a BST is the wrong shape for disk
A BST node is two child pointers and a key. On disk that is a page that is almost empty, plus a next hop that is almost certainly a different page. Sequential keys become a right spine: height n, n I/Os. Even a perfectly balanced BST is still ~20 hops for a million keys.
A B-tree node is a packed, sorted array. Sequential inserts fill a page, then split. Range-adjacent keys sit in the same node or in neighboring nodes after a split. The hot operation — “find this key” or “find this key, then the next fifty” — is a handful of page reads, not a pointer chase across the disk.
Same million keys
BST on disk: 1 key / page × ~20 pages per lookup
B-tree on disk: ~100 keys / page × ~3 pages per lookupWide nodes are not a style. They match the size of the expensive I/O. That is why indexes in databases and many filesystems are B-trees (or the B+ variant below), not binary search trees.
B+ trees: values in the leaves, leaves linked
A classic B-tree may store a payload next to a key in any node. A B+ tree splits that job:
- Internal nodes hold separator keys only. They route. They do not store row data.
- Leaves hold every key and its value (or a pointer to the row).
- Leaves are linked left to right (often a doubly linked list of pages).
Internal (routing only): [ 20 | 50 ]
/ | \
Leaves (keys + values): [10|15]→[20|25|30]→[50|60|80]
next nextPoint lookup still walks root to leaf. The extra copy of 20 and 50 in the parent is a separator, not a second row. Range scan is the payoff: find the leaf for lo, then follow next until you pass hi. You do not climb the tree again for each successor, and you do not inorder-walk internal nodes that never held values.
A leaf is keys, payloads, and a sibling pointer — the payload never lives in an internal node:
final class BPlusLeaf {
int[] keys;
int[] values; // or record ids — the payload lives here
int keyCount;
BPlusLeaf next;
}Search lands you on the first leaf that might contain lo. Walk next and keep keys in [lo, hi]:
void scanLeaves(BPlusLeaf start, int lo, int hi, List<Integer> out) {
for (BPlusLeaf leaf = start; leaf != null; leaf = leaf.next) {
for (int i = 0; i < leaf.keyCount; i++) {
int key = leaf.keys[i];
if (key < lo) {
continue;
}
if (key > hi) {
return;
}
out.add(key);
}
}
}Splits still promote a separator, but in a B+ tree that key is usually a copy: it also stays in the leaf, because the leaf is the only place values live. Merge and borrow follow the same occupancy rules. Linked leaves are why an index range can scan pages in order instead of hopping through a BST inorder.
Most “the database uses a B-tree” sentences mean this shape. Fill factor and clustered vs secondary indexes are storage-engine topics, not a new node type.
Java has no java.util.BTree
There is no B-tree in java.util. TreeMap and TreeSet are red-black trees: binary, pointer-rich, fine in RAM, still the wrong width for a disk page. ConcurrentSkipListMap is a skip list. None of them is a page-sized index.
NavigableMap<Integer, String> inMemory = new TreeMap<>();
inMemory.put(20, "paid");
inMemory.put(50, "packed");
// sorted keys, log n in RAM — not a database indexIf the data already fits in a heap and you need ordered keys, TreeMap is the JDK type. If you need unordered lookup, HashMap is the type. If you need a disk-backed index, you are talking to a database, Lucene, or an embedded engine — not implementing BTreeNode in the service layer.
Note: Rolling a B-tree is a good way to learn splits. Shipping one under production writes is a storage engine: recovery, concurrency, and pages. The Collections API will not grow a BTreeMap to spare you that.
When not to use a B-tree
Skip a B-tree when the data is not paying a disk (or remote page) bill:
- In-memory lookup with no range —
HashMap/HashSet. Hashing answers “is this key here?” without a tree and without order. A B-tree’s occupancy rules and page-shaped nodes are a tax you are not spending. - In-memory ordered keys.
TreeMap/TreeSetalready keep a balanced binary tree in RAM. You do not need page-sized nodes when a node is an object the GC already allocated. nis tiny. A sortedArrayListand a binary search will beat a tree of twenty keys. Log of a page fanout is not a reason to celebrate.- You wanted a queue, a heap, or a cache. Next-best element, eviction, FIFO — different layouts. A B-tree is an ordered, disk-friendly index, not a universal slow map.
Use a B-tree (usually a B+ tree inside a database or filesystem) when the hot path is keyed lookup or a range over data that lives in pages. If the sentence is “the map is already in this JVM and I just need get,” you wanted a hash table.
How to read the bill
Same shopping-list reading as the roadmap: pick the structure for the operation on the hot path. Height here is O(log_m n) with a large m.
Structure: B-tree (order m; max m−1 keys per node)
search O(h) — h ≈ log_m n; each step is one node / page
insert O(h) — leaf write; splits may walk back to the root
delete O(h) — borrow or merge; height shrinks only at the root
range O(h + k) — B+: h to the first leaf, then k items along next
space O(n) — nodes stay ≥ ~half full (except the root)Write O(h) if you like. Then remember h is 3 or 4 in a database index, not 20, because m is the page.
Cheat sheet
Shape: many keys per node; all leaves at the same depth
Order m: at most m children, m−1 keys (Knuth); page-sized in practice
Search: scan (or binary-search) keys in the node, then one child
Insert: write in the leaf; if full, split and promote the median
Delete: borrow from a sibling, else merge; height drops at the root
BST vs B: one key per hop vs one page per hop — disk cares about hops
B+: values only in leaves; leaves linked for range scans
JDK: no java.util.BTree; TreeMap is red-black; HashMap if no order
Skip: in-memory HashMap is enough; tiny n; not a disk page billDo:
- Size the node to the expensive I/O (a page), not to a binary-tree diagram.
- Treat split/merge as occupancy repair, not as BST rotations.
- Use a B+ leaf chain when the hot path is a range, not only a point
get. - Reach for
HashMapin the JVM when you do not need order or pages.
Don’t:
- Store one BST node per disk page and call it an index.
- Quote O(log n) without saying the fanout is the page.
- Implement a B-tree in application code because the table “felt like it should be a tree.”
- Confuse a B+ internal key (a separator) with a second copy of the row.
Wrap-up
A B-tree is a search tree whose nodes are wide on purpose. Search is a short stack of page-sized hops. Insert splits a full node and may grow a new root; delete borrows or merges and may drop the root. That is how the tree stays balanced without binary rotations, and why sequential IDs do not turn it into a linked list.
A B+ tree keeps every value in the leaves and links those leaves so a range is a walk along pages. Databases and filesystems use that family because the expensive operation is a block read, not a CPU comparison. In Java, the in-memory defaults stay HashMap and TreeMap. There is no JDK B-tree — and you do not need one until the data lives on disk.
For the glossary behind height, worst-case, and “what operation is hot,” stay on the Data Structures Roadmap.