B-Trees

Imagine a database index holding two billion records. It sits on a solid-state drive, where every read costs real time. A binary search tree on this data needs roughly 31 levels, even when perfectly balanced. That means 31 slow disk or SSD accesses just to find one record. This is unacceptable when each access might cost milliseconds instead of nanoseconds. The problem is not the asymptotic bound of $O(\log n)$ . It is the base of the logarithm. It also reflects a mismatch between how binary trees are shaped and how storage devices move data. Disks and SSDs transfer data in blocks — typically 4KB, 8KB, or larger. Reading one byte from a block costs almost the same as reading the whole block. A binary tree pays a full block-read for a single pointer-chase. This wastes nearly all of that transferred data. The natural fix is to make each node wide. Pack hundreds of keys and child pointers into a single block. Then one disk access does the work of many BST levels at once. This is the idea behind the B-tree. It was invented by Rudolf Bayer and Edward McCreight in 1970 for exactly this reason. A B-tree is a self-balancing multiway search tree. Every node holds many keys and many children. All internal nodes are constrained to stay between half-full and completely full. Every leaf sits at the identical depth. The "many children" property collapses the tree's height to $O(\log_t n)$ for branching factor $t$ . This factor can potentially reach the hundreds. That turns a 31-level BST into a 3- or 4-level B-tree over the same two billion keys. The "always at least half full" property is maintained through node splitting and merging. It guarantees this shallow height never degrades. This holds no matter what sequence of insertions and deletions arrives. This article gives the precise definition of a B-tree of minimum degree $t$ . It walks through search, insertion (with node splitting), and deletion (with node merging and key redistribution) in careful pseudocode. It proves the height bound and per-operation complexity. It also works a full insertion-and-split trace by hand. It builds on the balancing intuition from Red-Black Trees. But it generalizes that intuition to nodes of arbitrary fan-out. This generalization is exactly what makes B-trees the structure of choice for filesystems and database indexes.

Key takeaways

A B-tree is a balanced multiway search tree tuned for block-based storage: wide nodes, shallow height.
Minimum degree $t$ fixes node capacity: every internal node (except the root) has between $t-1$ and $2t-1$ keys.
Height is $O(\log_t n)$ , so with $t$ in the hundreds a billion-key tree has height 3–4, not 30+.
Insertion splits full nodes on the way down; deletion merges or borrows keys to keep nodes at least half full.
All leaves live at the same depth — the tree is always perfectly height-balanced, never just "roughly" balanced.
Every operation costs $O(t \log_t n)$ time and touches $O(\log_t n)$ disk blocks, which is the metric that matters in practice.

The core insight

A B-tree trades the binary tree's narrow-but-deep shape for a wide-but-shallow one, matching node size to disk block size so that each disk access does maximal useful search work.

The idea

A B-tree of minimum degree $t \geq 2$ is a search tree in which every node (except possibly the root) stores between $t-1$ and $2t-1$ keys, and correspondingly between $t$ and $2t$ children if it is internal. The root is allowed to have as few as $1$ key (or be a leaf with $0$ keys, for an empty tree). Keys inside a node are stored in sorted order, and for an internal node with keys $k_1 < k_2 < \dots < k_m$ and children $c_0, c_1, \dots, c_m$ , every key in the subtree rooted at $c_i$ lies between $k_i$ and $k_{i+1}$ (with $c_0$ 's keys below $k_1$ and $c_m$ 's keys above $k_m$ ). This is the direct multiway generalization of the BST ordering invariant. Two structural invariants make the tree efficient. Balance: every leaf appears at exactly the same depth, so there is no notion of a "deep branch" the way an unbalanced BST can develop one. Occupancy: every node except the root is at least half full, holding at least $t-1$ keys. This lower bound is what prevents pathological thin trees — it forces branching factor to stay large everywhere, which is precisely what keeps the height small. The number $2t-1$ is chosen as the maximum key count so that a node's size, in bytes, matches one disk block; $t$ is tuned per system to make this true. The key operations — search, insertion, deletion — all work by walking down from the root using the same sorted-order comparisons a BST uses, but at each node performing an $O(\log t)$ or $O(t)$ scan across the node's keys instead of a single comparison. Insertion may cause a node to overflow past $2t-1$ keys, which is repaired by splitting the node into two half-full nodes and promoting the median key upward. Deletion may cause a node to underflow below $t-1$ keys, repaired by borrowing a key from an adjacent sibling or, if no sibling has a spare, merging two nodes into one. Both repairs are local and propagate upward only when necessary, which is what keeps every operation logarithmic.

How it works

Search descends from the root exactly as in a BST, except each node requires a scan (or binary search within the node) across up to $2t-1$ keys to decide which child to follow. ``` SEARCH(node x, key k): i = 1 while i <= x.n and k > x.key[i]: i = i + 1 if i <= x.n and k == x.key[i]: return (x, i) // found if x.is_leaf: return NOT-FOUND DISK-READ(x.child[i]) // fetch the next block return SEARCH(x.child[i], k) ```

Insertion always inserts into a leaf, exactly like a BST, but a full node (one already holding $2t-1$ keys) cannot accept another key. So the algorithm proactively splits any full node it encounters while descending, guaranteeing that whenever it reaches a leaf, that leaf still has room. This "split on the way down" trick avoids ever having to propagate a split back up after the fact. ``` SPLIT-CHILD(node x, index i): // x.child[i] is a full node y with 2t-1 keys; split it in two. y = x.child[i] z = NEW-NODE() z.is_leaf = y.is_leaf z.n = t - 1 // z takes the largest t-1 keys of y copy y.key[t+1 .. 2t-1] into z.key[1 .. t-1] if not y.is_leaf: copy y.child[t+1 .. 2t] into z.child[1 .. t] median = y.key[t] y.n = t - 1 // y keeps the smallest t-1 keys // insert z as a new child of x, and median as a new key of x shift x.child[i+1 .. x.n+1] right by one; x.child[i+1] = z shift x.key[i .. x.n] right by one; x.key[i] = median x.n = x.n + 1 DISK-WRITE(y); DISK-WRITE(z); DISK-WRITE(x) INSERT(tree T, key k): r = T.root if r.n == 2t - 1: s = NEW-NODE() T.root = s s.is_leaf = false s.n = 0 s.child[1] = r SPLIT-CHILD(s, 1) INSERT-NONFULL(s, k) else: INSERT-NONFULL(r, k) INSERT-NONFULL(node x, key k): i = x.n if x.is_leaf: while i >= 1 and k < x.key[i]: x.key[i+1] = x.key[i] i = i - 1 x.key[i+1] = k x.n = x.n + 1 DISK-WRITE(x) else: while i >= 1 and k < x.key[i]: i = i - 1 i = i + 1 DISK-READ(x.child[i]) if x.child[i].n == 2t - 1: SPLIT-CHILD(x, i) if k > x.key[i]: i = i + 1 INSERT-NONFULL(x.child[i], k) ```

Deletion is the trickiest operation because removing a key can leave a node under the minimum of $t-1$ keys. The standard scheme (following Cormen–Leiserson–Rivest–Stein's formulation) guarantees, before recursing into any child, that the child has at least $t$ keys — one more than the bare minimum — so that even if a key is removed from it, it never drops below $t-1$ . This is the deletion analogue of "split on the way down." ``` DELETE(node x, key k): i = find index such that k <= x.key[i], or i = x.n+1 if none if i <= x.n and x.key[i] == k: // k found in x if x.is_leaf: remove x.key[i] else: y = x.child[i] // predecessor's subtree z = x.child[i+1] // successor's subtree if y.n >= t: k' = PREDECESSOR-KEY(y) x.key[i] = k' DELETE(y, k') elif z.n >= t: k' = SUCCESSOR-KEY(z) x.key[i] = k' DELETE(z, k') else: MERGE(x, i) // merge y, k, z into one node of 2t-1 keys DELETE(x.child[i], k) else: if x.is_leaf: return // key not present c = x.child[i] if c.n == t - 1: // ensure c has >= t keys before descending left = x.child[i-1] if i > 1 else NIL right = x.child[i+1] if i <= x.n else NIL if left != NIL and left.n >= t: BORROW-FROM-LEFT(x, i) elif right != NIL and right.n >= t: BORROW-FROM-RIGHT(x, i) elif left != NIL: MERGE(x, i-1); c = x.child[i-1] else: MERGE(x, i) DELETE(c, k) ``` `MERGE(x, i)` combines `x.child[i]`, the key `x.key[i]`, and `x.child[i+1]` into a single node with exactly $(t-1) + 1 + (t-1) = 2t-1$ keys, removes that key and child pointer from `x`, and (if `x` is the root and now empty) makes the merged node the new root — this is the only way the tree's height ever decreases. `BORROW-FROM-LEFT`/`RIGHT` rotate one key from a rich sibling through the parent, mirroring rotations in Red-Black Trees but at the granularity of whole keys rather than tree edges.

Figure

A B-tree of minimum degree t = 2 (each node holds 1–3 keys, 2–4 children)

Complexity & correctness

Height bound. Let $n$ be the number of keys stored and $h$ the height of the tree (root at height $0$ ). Every node other than the root has at least $t-1$ keys, hence at least $t$ children. So at depth $1$ there are at least $2$ nodes (root has $\geq 2$ children), at depth $2$ at least $2t$ nodes, at depth $3$ at least $2t^2$ , and in general at depth $i \geq 1$ at least $2t^{i-1}$ nodes. Each node at depth $h$ contributes at least $t-1$ keys, so

n \geq 1 + \sum_{i=1}^{h} 2t^{i-1}(t-1) = 1 + 2(t^h - 1) = 2t^h - 1.

Solving gives

h \leq \log_t\!\left(\frac{n+1}{2}\right) = O(\log_t n).

This is the entire justification for calling B-trees "disk-friendly": with $t = 500$ (a realistic value when nodes are sized to 4–8 KB blocks), a tree of one billion keys has height at most $\log_{500}(5\times10^8) \approx 3.2$ , i.e. 4 levels. Compare a balanced binary tree on the same data, which needs $\log_2(10^9) \approx 30$ levels.

Time per operation. `SEARCH`, `INSERT`, and `DELETE` all walk a single root-to-leaf path, so each touches $O(h) = O(\log_t n)$ nodes. Within each node, work is $O(\log t)$ if binary search is used on the sorted keys, or $O(t)$ with linear scan; either way the total CPU time is

O(t \log_t n) \quad \text{(linear scan per node)} \qquad \text{or} \qquad O(\log t \cdot \log_t n) \quad \text{(binary search per node)}.

The number of disk accesses — the metric that actually matters for external-memory performance — is exactly $O(\log_t n)$ , since each node read/write is one block I/O regardless of $t$ . This is the key tradeoff: increasing $t$ increases in-memory CPU work per node slightly (more keys to scan) but decreases the number of slow disk transfers, and since disk latency dominates CPU time by many orders of magnitude, larger $t$ is almost always a net win up to the block-size limit.

Space. A tree with $n$ keys uses $O(n)$ space; more precisely between $\lceil n / (2t-1) \rceil$ and $\lceil n/(t-1) \rceil$ nodes, so occupancy never drops below 50% and total wasted space is bounded.

Correctness sketch. The ordering invariant (subtree between $k_i$ and $k_{i+1}$ ) is preserved by every operation:

Search correctness follows from this invariant by the same inductive argument as BST search — at each node the algorithm picks the unique child whose range could contain $k$ .
Insertion correctness rests on the claim that `INSERT-NONFULL(x, k)` is only ever called on a node with fewer than $2t-1$ keys, so it never overflows before we can split. This holds by induction: the root is split before the initial call if full, and inside the recursion any full child is split before recursing into it — so the invariant "the node about to receive a key or split has room" is maintained at every depth.
Splitting preserves the search-tree property because the median key `y.key[t]` is exactly the value separating the low half (which stays in $y$ ) from the high half (moved to $z$ ), so all keys in $y$ are still less than the promoted key, and all keys in $z$ still greater.
Deletion correctness rests on the invariant that `DELETE` is only ever recursively called on a node with at least $t$ keys (except possibly the root). This is enforced by the pre-emptive borrow/merge step performed before every recursive descent, so removing one key never drops a non-root node below $t-1$ . Merging two nodes of $t-1$ keys plus one key from the parent yields exactly $2t-1$ keys — never overfull — so a merge cannot itself trigger a new split.
Because every leaf is created and destroyed only via splits/merges that preserve depth-uniformity (a split keeps both halves at the old depth; a merge removes one level only at the root), the "all leaves at equal depth" invariant is preserved by every operation, which is what keeps the height bound — and hence the whole complexity argument — valid after arbitrary sequences of insertions and deletions.

Honest tradeoffs. B-trees are not free lunches: they have larger constant factors than binary trees for in-memory workloads (extra key-shifting inside nodes on every insert/delete), and correctly implementing deletion with all its case splits is notoriously fiddly. Many production systems (e.g. many database engines) instead use the B+ tree variant — all data lives in the leaves, and internal nodes store only routing keys, which simplifies range scans and increases fan-out further, at the cost of the extra indirection the article does not cover here beyond noting it exists.

Worked example

Trace inserting the sequence `10, 20, 5, 6, 12, 30, 7, 17` into an empty B-tree with minimum degree $t = 2$ (so nodes hold between $1$ and $3$ keys; a node splits once it would hold $4$ ).

Step	Action	Resulting tree structure
Insert 10	Root is leaf `[]`, not full → insert	`[10]`
Insert 20	Root `[10]` not full → insert	`[10, 20]`
Insert 5	Root `[10,20]` not full → insert	`[5, 10, 20]`
Insert 6	Root `[5,10,20]` is full (3 keys, max is $2t-1=3$ ) → split before descending. Median `10` promoted to a new root; leaves become `[5]` and `[20]`. Then insert 6 into leaf `[5]` (6 > 5, goes right side of median but into leaf `[5]` since 6<10)	root `[10]`; children `[5,6]`, `[20]`
Insert 12	Root `[10]` not full. Descend to right child `[20]` (12<20, but 12>10 so goes to right child). Not full → insert	root `[10]`; children `[5,6]`, `[12,20]`
Insert 30	Descend to right child `[12,20]`, not full → insert	root `[10]`; children `[5,6]`, `[12,20,30]`
Insert 7	Descend to left child `[5,6]`, not full → insert	root `[10]`; children `[5,6,7]`, `[12,20,30]`
Insert 17	Descend to right child `[12,20,30]` — it is full. Split it first: median `20` promoted to root, children become `[12]` and `[30]`. Root becomes `[10, 20]`. Now decide which child 17 goes to: 10 < 17 < 20 → middle child `[12]`. Insert 17 there	root `[10, 20]`; children `[5,6,7]`, `[12,17]`, `[30]`

Final tree (height 1, 3 leaves, root with 2 keys and 3 children) is shown below.

Figure

Final state after inserting 10, 20, 5, 6, 12, 30, 7, 17 into a t=2 B-tree

Notice two splits happened along the way (triggered by inserting `6` and by inserting `17`), yet the tree never exceeded height $1$ across eight insertions — this is the height-stability the invariant guarantees.

Common pitfalls & traps

Pitfall	Why it happens	Fix
Splitting after descending instead of before	Feels more natural ("split when it overflows") but forces a second upward pass and awkward parent updates	Always check-and-split full children on the way down (pre-emptive splitting), as in the pseudocode above
Off-by-one on the median index during split	Confusing $t-1$ , $t$ , $2t-1$ boundaries	Fix $t$ concretely, hand-verify: a full node has $2t-1$ keys; index $t$ is the median, indices $1..t-1$ stay, $t+1..2t-1$ move
Forgetting the root can shrink	Merging the root's only two children into one leaves an empty root	Explicitly check: if root becomes empty after a merge, make the merged child the new root, decreasing height by 1
Deleting an internal key without checking sibling richness first	Naively removing an internal key and promoting an arbitrary replacement can leave a child under $t-1$ keys	Always confirm predecessor/successor subtree has $\geq t$ keys before recursing, else merge first
Treating $t$ as a fixed universal constant	Using $t=2$ (equivalent to a 2-3-4 tree) for a real disk-backed system defeats the whole purpose	Choose $t$ so that a node's serialized size matches the storage block size (often $t$ in the hundreds)

Pioneers & history

Origins · 1 minRudolf Bayer and how this was discovered

Rudolf Bayer

1939–2007 · German computer scientist at Boeing Scientific Research Labs, later TU Munich

Bayer co-invented the B-tree with Edward McCreight in 1970 while working on large-scale indexed file organization at Boeing. He had earlier contributed to the theory of balanced trees more broadly, including work related to what became known as symmetric binary B-trees — a precursor to the red-black tree formalization. The B-tree paper solved a very concrete industrial problem: how to index enormous files stored on slow, block-oriented disk hardware, without requiring the tree to be rebalanced by hand or grow disastrously deep.

History

1970

— Bayer and McCreight publish "Organization and Maintenance of Large Ordered Indexes," introducing the B-tree.

1972

— Bayer and Schkolnick refine deletion algorithms and analyze concurrent access to B-trees.

1973

— Douglas Comer's widely cited survey "The Ubiquitous B-Tree" popularizes and formalizes B-trees for a broader systems audience.

1979

— The B+ tree variant (leaves hold all data, internal nodes are pure routing indexes) becomes standard in database systems.

1980

s–present — B-trees and B+ trees become the default index structure inside nearly every relational database and filesystem.

The letter "B" itself has never been definitively explained by its inventors — commonly guessed to stand for "Bayer," "balanced," or "Boeing" — a small historical mystery that persists in textbooks to this day.

Where this matters

Nearly every relational database — PostgreSQL, MySQL's InnoDB, Oracle, SQL Server — stores its primary indexes as B+ trees, a direct descendant of the structure described here, because table data vastly exceeds RAM and disk-block-aligned nodes minimize I/O. Filesystems including NTFS, HFS+, ext4 (via its `htree` variant), Btrfs, and APFS use B-tree or B-tree-like structures to index directory entries and file extents, letting a filesystem locate a file among millions with only a handful of block reads. Key-value stores such as LMDB use B+ trees directly on memory-mapped files, exploiting the same block-alignment principle at nanosecond RAM-access scale. Even where B-trees have been partially displaced — by LSM-trees in write-heavy systems like Cassandra or RocksDB — the comparison is almost always framed against the B-tree as the baseline, because it remains the canonical answer to "how do I organize sorted data efficiently on block storage."

Ask the tutor: How does the B+ tree variant change the split and merge logic when all data lives only in the leaves?

How is a B-tree different from a B+ tree?

A B-tree stores keys and associated data in both internal nodes and leaves, so a search can terminate early at an internal node. A B+ tree stores actual data only in the leaves; internal nodes hold copies of keys purely for routing. This makes B+ tree leaves linkable into a sorted linked list, enabling fast ordered range scans — a major reason database indexes almost universally use B+ trees rather than plain B-trees. The tradeoff is slightly more storage (keys duplicated at internal levels) for much better range-query and sequential-scan performance, which usually dominates in database workloads.

Why not just use a balanced binary tree like a red-black tree on disk?

A red-black tree achieves height $O(\log_2 n)$ , but that base-2 logarithm means roughly 30 levels for a billion keys, and each level typically requires a separate disk block read if nodes aren't co-located. B-trees instead widen each node to match the disk's block size, so one disk read retrieves an entire node's worth of keys — often hundreds — collapsing the effective height to $O(\log_t n)$ with $t$ in the hundreds. The result is 3–4 disk accesses instead of 30, which matters enormously since disk latency dwarfs in-memory comparison cost.

What determines the right choice of minimum degree t in practice?

$t$ is chosen so a single node's serialized size (key/value/pointer arrays for up to $2t-1$ keys and $2t$ children) fits exactly one storage block, commonly 4KB, 8KB, or 16KB. If keys and pointers are, say, 16 bytes combined, an 8KB block might comfortably fit $t \approx 250$ . Choosing $t$ too small wastes the block-alignment advantage; choosing it too large can make a single node exceed one block, forcing multiple I/Os per node and defeating the purpose. Systems often benchmark empirically around the theoretical block-fit value.

Does a B-tree stay balanced automatically, or does it need periodic rebalancing?

It stays balanced automatically as a direct consequence of every insertion and deletion routine, never through a separate rebalancing pass. Splits during insertion and merges/borrows during deletion are performed inline as part of the same operation, and both are engineered to preserve the "all leaves at equal depth" invariant at every step. This is analogous to how Red-Black Trees fix violations via rotations and recoloring during the same insert/delete call, rather than via a background balancing sweep.

What happens to the tree's height when the root becomes empty after a deletion?

If merging a root's last two children produces a single node with all the keys, the (now childless-of-keys) old root is discarded and that merged node becomes the new root. This is the only situation in which the tree's height decreases, and it happens naturally as part of the deletion algorithm's cleanup — no separate "shrink" procedure is needed. Symmetrically, height only ever increases when the old root overflows and must be split, producing a brand-new root above it.

Can a B-tree degrade to bad performance under adversarial insertion/deletion sequences?

No — the height bound $O(\log_t n)$ is a worst-case guarantee, not an average-case one, because every node except the root is provably kept between $t-1$ and $2t-1$ keys regardless of insertion order. This is fundamentally different from an unbalanced binary search tree, which can degrade to a linked list (height $O(n)$ ) under sorted-order insertions. The split/merge machinery is specifically designed so no sequence of operations, adversarial or not, can violate the occupancy invariant.

Is a B-tree ever a bad choice compared to a hash table or an LSM-tree?

Yes, depending on the workload. Hash tables beat B-trees for pure key lookup with no ordering requirement, offering expected $O(1)$ versus $O(\log_t n)$ . LSM-trees (used by Cassandra, RocksDB, LevelDB) beat B-trees on write-heavy workloads because they batch writes sequentially rather than performing in-place block updates, at some cost to read latency. B-trees remain the best general-purpose choice when a system needs fast point lookups, ordered range scans, and moderate write loads simultaneously — which is why relational databases still favor them.