B-Trees & B+ Trees

The 10-second versionCopy Anchor Link

Every tree so far assumed its nodes live in memory, where hopping between them is nearly free. B-trees assume the opposite: nodes live on disk, where each hop is a slow, expensive I/O. So instead of trying to touch as few comparisons as possible (which wants thin, binary nodes), a B-tree makes each node enormous — one disk block, holding hundreds of sorted keys and child pointers. A fat node means a huge branching factor, which means a tiny height: a few levels can index billions of records, so a lookup costs just a handful of disk reads. B+ trees tweak the layout — all the data lives in the leaves, and the leaves are linked into a list — which makes range scans fast. Together they run essentially every database index and filesystem on Earth.

Why this existedCopy Anchor Link

Think about the hardware. A single main-memory access is measured in nanoseconds; a disk seek is measured in milliseconds — roughly a hundred-thousand times slower. (Modern SSDs narrow that gap, but not by orders enough to change the story.)

Now take a plain binary search tree over a billion keys. Its height is about log₂(10⁹) ≈ 30, and each level is a separate node, which means a separate random read. Thirty disk seeks at ~10 ms each is a third of a second per lookup — for something a hash map does in a blink. The problem isn't the algorithm; the algorithm is fine. The problem is that a BST is shaped for the wrong cost model: it optimizes the thing that's cheap (comparisons) and ignores the thing that's dear (I/Os).

That mismatch is what started the whole line of work. In 1970, Rudolf Bayer and Edward McCreight, at Boeing's Scientific Research Laboratories, were trying to organize large, growing files of data stored on disk — files too big for memory and constantly being added to. In 1972 they published "Organization and Maintenance of Large Ordered Indices", and the B-tree was born. (The "B" was never officially defined — people offer Boeing, Bayer, or balanced — which is a nice reminder that even canonical names are sometimes just a shrug.)

The structure took over. Douglas Comer's 1979 survey in ACM Computing Surveys was titled "The Ubiquitous B-Tree", and the name was earned: by the 1980s, B-trees and their B+ variants were the default way to index data that didn't fit in RAM, from database systems to filesystems.

Why it mattered: it redefined the whole question. Once you accept that the disk is the bottleneck, "make each node a disk block" isn't a detail — it's the entire design.

Inside the inventor's headCopy Anchor Link

Bayer and McCreight had to change what they were counting. On disk, comparisons are effectively free; the only scarce resource is the number of times you have to read a block. So the goal flips: minimize the number of nodes touched, not the number of keys compared.

That flip breaks the binary tree on purpose. If each node holds exactly one key, then the number of nodes on a root-to-leaf path is the number of disk reads — and a billion keys means ~30 of them. But if each node holds, say, 250 keys, then one node can route among 251 children, and the height drops to log₂₅₁(10⁹) ≈ 4. Four disk reads instead of thirty. Same data, wildly fewer I/Os.

Here's the same contrast in layout. A binary node wastes an entire block on one key; a B-tree node fills the block with keys, and that's the entire trick:

// Naive on disk: one key per node means one random disk read PER LEVEL.// A billion keys → ~30 reads, each ~10 ms. A third of a second per lookup. No.class BstNode { constructor(key) { this.key = key; this.left = null; this.right = null; } }

// Improved: ONE disk block = MANY keys. A single read rules them all out.const ORDER = 256;                         // up to 255 keys per node == one blockclass BTreeNode {  constructor() {    this.keys = [];                        // sorted — binary-search inside the block    this.children = [];                    // keys.length + 1 children  }}

The second half of the insight is how you keep such a tree balanced. You can't "rotate" a giant multi-way node the way AVL does. Instead, when a node overflows, you split it and push the median key up into the parent. The parent gets one fatter; if it overflows, it splits too. Balance is maintained by growth upward, and it works so cleanly that all leaves always end up at the exact same depth.

The final approachCopy Anchor Link

The shapeCopy Anchor Link

A small B-tree — every node holds a few sorted keys, and there are always exactly keys + 1 children, so the leaves line up:

A B+ tree changes one thing: internal nodes become pure signposts (they repeat keys just to route), and all the actual records live in the leaves, which are chained together left-to-right. That chain is what makes for every row where id is between 100 and 200 a fast sequential walk instead of a hundred separate searches:

The invariants that make it correctCopy Anchor Link

Fix a minimum degree t. Then a B-tree is a tree where:

1. Every node holds at most 2t − 1 keys — and at least t − 1 keys, except the root (which may hold as few as one).
2. A node with k keys has exactly k + 1 children. The keys are separators: child i holds only keys between key[i−1] and key[i].
3. Keys inside each node are stored in sorted order, so you binary-search within a block.
4. All leaves are at the same depth. The tree is perfectly height-balanced — no rotations, ever, only splits.
5. (B+ trees) internal nodes store no records; every record is in a leaf, and the leaves are linked in sorted order.

Invariant 4 is the payoff of splitting-on-overflow: the tree only ever grows at the root, and it grows by one level at a time, so no leaf can ever get ahead of the others.

The algorithm, as a flowCopy Anchor Link

Insertion is a single descent from the root to a leaf, splitting any full node on the way down so the recursion never has to back up:

That "split before descending" is the elegant part of the classic algorithm: by the time you reach a leaf, every node on the path has room, so an insert never has to cascade back up.

A worked traceCopy Anchor Link

Build a small B-tree with room for 3 keys per node (t = 2), inserting 10, 20, 30, 40:

• Insert 10, then 20, then 30. They all land in the root, which is now [10 20 30] — full.
• Insert 40. On the way down, the root is full, so we split it around its median 20, which rises to become a brand-new root. The old keys split into a left child [10] and a right child [30]. The tree just got one level taller, and it did it from the top.
• 40 is greater than the separator 20, so we descend into the right child and place it: [30 40].

The height grew from 1 to 2, uniformly — both leaves are still at the same depth.

It in codeCopy Anchor Link

A working B-tree with search and insert, including the node split. This is the real algorithm — the one inside your database.

const T = 3;                              // minimum degree: at most 2T-1 = 5 keys/nodeclass Node {  constructor(leaf) { this.leaf = leaf; this.keys = []; this.children = []; }}function search(x, k) {  let i = 0;  while (i < x.keys.length && k > x.keys[i]) i++;  if (i < x.keys.length && x.keys[i] === k) return x;   // found in this block  if (x.leaf) return null;                              // not present  return search(x.children[i], k);}function splitChild(x, i) {                // split the FULL child x.children[i]  const y = x.children[i];  const z = new Node(y.leaf);  const moved = y.keys.splice(T - 1);      // y keeps its first T-1 keys  const median = moved.shift();            // the middle key rides up  z.keys = moved;                          // z gets the right T-1 keys  if (!y.leaf) z.children = y.children.splice(T);  x.keys.splice(i, 0, median);             // median goes UP into the parent  x.children.splice(i + 1, 0, z);}function insertNonFull(x, k) {  let i = x.keys.length - 1;  if (x.leaf) {    while (i >= 0 && k < x.keys[i]) i--;    x.keys.splice(i + 1, 0, k);  } else {    while (i >= 0 && k < x.keys[i]) i--;    i++;    if (x.children[i].keys.length === 2 * T - 1) {   // full child → split first      splitChild(x, i);      if (k > x.keys[i]) i++;    }    insertNonFull(x.children[i], k);  }}function insert(root, k) {  if (root.keys.length === 2 * T - 1) {              // root full → grow a new root    const s = new Node(false);    s.children[0] = root;    splitChild(s, 0);    insertNonFull(s, k);    return s;  }  insertNonFull(root, k);  return root;}

Cost tableCopy Anchor Link

With branching factor b (up to 2t), the height is log_b n — and because b is large, that number is tiny.

The headline isn't the comparison count — that has never been the point. It's the disk reads, which are logarithmic in a base of hundreds. That's the difference between "a fraction of a second" and "microseconds."

Where you meet it todayCopy Anchor Link

• Every relational database index. PostgreSQL, MySQL's InnoDB, and SQLite all store indexes as B-trees or B+ trees — which is exactly why CREATE INDEX can turn an O(n) table scan into an O(log n) lookup with a handful of page reads.
• Your filesystem. NTFS, ext4, XFS, HFS+, and APFS all keep directory entries and file-extent maps in B-trees, so "which block holds byte 5,000,000 of this file?" is a few reads, not a scan.
• Embedded and key-value stores. LMDB uses a copy-on-write B+ tree; many embedded databases do the same, precisely because B+ trees are so range-scan friendly.
• The reason your ORDER BY ... LIMIT is fast. That query leans on the sorted leaf chain: the engine jumps to the first leaf and streams, instead of sorting the whole table.

// Find the left leaf once, then follow the leaf links — no re-descending per row.function scan(root, lo, hi) {  let leaf = findLeaf(root, lo);            // one O(log n) descent  const out = [];  while (leaf && leaf.keys[0] <= hi) {      // then a sequential left-to-right walk    for (const k of leaf.keys) if (k >= lo && k <= hi) out.push(k);    leaf = leaf.next;                        // the leaf link that makes B+ special  }  return out;}

RecapCopy Anchor Link

• A B-tree is a balanced search tree designed around disk I/O, not comparisons: each node is one disk block holding hundreds of keys.
• Fat nodes give a huge branching factor, so the height stays tiny — a few levels index billions of records.
• Balance is kept by splitting full nodes and pushing the median up; the tree only ever grows at the root, so all leaves stay at the same depth.
• The invariant set is a minimum degree t: t − 1 to 2t − 1 keys per node, keys + 1 children, sorted keys, equal leaf depth.
• A B+ tree keeps all records in linked leaves, so a range scan is one descent plus a sequential walk — and with a branching factor of hundreds the height log_t n is basically the number 3 or 4.

Next up: Tries — a tree that keys not by comparisons, but by the characters of a string as you walk it.