Every tree on this site so far — BST,
AVL,
red-black,
splay — branches at most two ways per node. A B-tree
branches many ways: each node holds several sorted keys at once, and a node with k keys
has k + 1 children, one for each gap between (and around) the keys. That single change
has a large consequence — the tree gets wide instead of deep. A binary tree holding
a million keys needs roughly 20 levels even perfectly balanced; a B-tree with, say, 100 keys per node
needs about 3. Every level of a tree is a pointer to chase, and for a structure that lives on disk
rather than in RAM — a database index, a filesystem's directory tree — a pointer chase is a seek, and
a seek is millions of times slower than comparing a few more keys already sitting in memory once
you've paid for the block. Fewer levels means fewer seeks; that trade is the entire reason B-trees
exist.
The parameter that controls the branching factor is called the minimum degree,
written t. Every node except the root must hold between t - 1 and
2t - 1 keys, and every internal node's number of children is always exactly one more
than its number of keys. Small t values are easiest to draw and reason about — this
page's demo fixes t = 2, so every node holds 1 to 3 keys and has 2 to 4 children. That
specific case has a name of its own: a t = 2 B-tree is exactly a
2-3-4 tree, and it turns out to be the same structure as a
red-black tree wearing a different notation — a
3-key B-tree node unpacks into a black node with two red children, a 2-key node unpacks into a black
node with one red child folded onto either side, and a red-black tree's height-balance rule (no root-
to-leaf path has more than twice the black nodes of any other) is the same balance guarantee this
page's split rule enforces directly on the wide node. Two very different-looking pages on this site
describe one underlying shape.
The tree below was built by inserting 10, 20, 30, … 90 — nine values, strictly
ascending, the exact input that collapsed a plain
BST into a straight chain and forced
splay/AVL/
red-black to do real rebalancing work to avoid it.
A B-tree doesn't need to react at all: it stays at height 3 the whole way through, verified below, not
because anything detects and fixes imbalance after the fact, but because insert itself never
lets a node overflow past 2t - 1 keys in the first place. Try inserting 25
— it lands in the leaf that already holds 30, with no split needed. Then try 75: the
leaf holding 70, 80, 90 is already full, so watch the log name the split before it
happens — the middle key (80) moves up into the parent, the node divides into 70 and
90, and only then does the walk continue downward to place 75. Search works the
ordinary way: at each node, scan its keys
to find the value, an exact match, or the gap to descend through. Delete has its own two-step story,
covered in full below — try deleting 30 first: both of the root's children hold only
one key each (the legal minimum), so removing 30 forces a merge that cascades down two levels and
shrinks the tree's height from 3 to 2, all in one click. Then delete 10: this time a
sibling has a key to spare, so the fix is a cheap borrow (a rotation through the parent) instead of a
merge — no height change.
A node is full once it holds 2t - 1 keys — for this page's
t = 2, that's 3. Splitting a full node y (the i-th child of
some parent) works in one fixed move: the top t - 1 keys of y (and, if
y isn't a leaf, its top t children) are cut off into a brand-new node
z; the single key that used to sit between those two halves — y's new
maximum after the cut — moves up into the parent, landing at index i, with
z inserted as the parent's new child at index i + 1. y and
z now each hold exactly t - 1 keys — the legal minimum, half of what
y had before minus the one that moved up — and the parent has gained exactly one key and
one child, keeping its own key/child-count relationship intact. If the parent was itself the root and
had no room, splitting it is what grows the tree by one level: the only place a B-tree's height ever
increases is at the root, which is also why every root-to-leaf path in a B-tree is always exactly the
same length (checked below, not just claimed) — a leaf never ends up shallower than another because
nothing about a split can make one subtree's leaves diverge from another's depth.
The textbook alternative to this page's approach inserts first, then walks back up fixing any node that ended up over capacity — workable, but it needs either parent pointers or a call stack that remembers the whole descent path, so it can unwind and split. This page's algorithm instead makes it structurally impossible for a full node to ever be walked into:
The whole operation is a single top-down pass with no backtracking, which is the practical payoff of proactive splitting: a node can be discarded (or, in an on-disk implementation, its page written back) the moment the walk moves past it, since nothing later will ever need to revisit it.
Search starts at the root and, at each node, scans its sorted keys left to right. Three things can
happen at a key: the target is smaller (keep scanning, or descend through the gap immediately before
it if this is the last key checked), it matches exactly (done — found), or the target is larger than
every key in the node (descend through the last gap, past all of them). Descending means following
the child pointer sitting at that gap's index; falling off the bottom of a leaf without a match means
the value isn't in the tree. With a small t like this page's, scanning a node's keys is a
handful of comparisons; production B-trees sized for disk pages often use dozens or hundreds of keys
per node and binary-search within each one instead of scanning linearly — a real optimization, but one
this page's reference implementation skips, since it wouldn't change any comparison count that matters
at t = 2.
Insert only ever has to worry about one full node on the way down at a time, which is why
proactively splitting it just before descending is enough. Delete has the opposite problem: removing a
key can leave a node under the minimum of t - 1 keys, and unlike a full node
(which only insert can cause), an under-full node can cascade — fixing one node's shortage by pulling a
key from it can immediately make its neighbor short too. The proactive discipline this page's insert
algorithm uses generalizes directly: instead of guaranteeing every node about to be entered has
room to grow, delete guarantees every node about to be entered has room to shrink — at least
t keys, one more than the bare minimum, so that losing one during the visit still leaves it
legal.
k being deleted the ordinary way, at each node deciding whether it
sits in this node's own keys or in the gap leading to some child.k is one of the current node's own keys and the node is a leaf,
removing it is a direct splice — nothing else can be affected, since a leaf has no children to keep
consistent.k is one of the current node's own keys but the node is internal,
it can't just be spliced out — every other key still needs a value on each side of it. Instead: if the
child immediately to k's left has ≥ t keys, find its largest key (the
predecessor, always in a leaf — keep following the rightmost child down), copy it into
k's old slot, then recursively delete the predecessor from that child instead (a strictly
simpler problem: deleting a key that's now known to live in a leaf, or another internal node one level
down). Symmetrically, if the right child has ≥ t keys, pull up the
successor (its smallest key) instead. If neither child can spare a key, merge
the two children and k itself into one node, then delete k from that merged
node.k isn't in the current node at all, the walk is about to descend into whichever
child's gap it belongs in — but first, if that child has only t - 1 keys (the bare
minimum, one fill away from going illegal), fix it: borrow a key from a sibling that has
one to spare — the same rotation shape as AVL's or
red-black's rebalancing, just through a wide node
instead of a two-way one: the parent's separator moves down into the thin child, and the sibling's
outermost key moves up to replace it, so the ordering invariant between them never breaks — if either
sibling has ≥ t keys, or, if
both siblings are also sitting at the bare minimum, merge the child with one sibling through
their shared parent separator — the same merge operation used by the internal-key case above, just
triggered on the way down instead of by finding k directly.Like insert, the whole walk is single-pass with no backtracking — every node the search actually descends into is fixed up before the descent, never after, so nothing already passed needs to be revisited. Borrowing costs the same O(1) work as a merge locally, but a borrow stops the fix right there; only a merge can propagate, and even then it propagates at most once per level on the way down, the same way a split propagates at most once per level on the way up during insert.
class BTree {
#t;
#root;
constructor(t = 2) {
this.#t = t;
this.#root = { keys: [], children: [], leaf: true };
}
#splitChild(parent, i) {
const t = this.#t;
const y = parent.children[i];
const z = { keys: y.keys.splice(t, t - 1), children: [], leaf: y.leaf };
const midKey = y.keys.pop(); // must be pop(), not shift() — see Pitfalls
if (!y.leaf) z.children = y.children.splice(t, t);
parent.children.splice(i + 1, 0, z);
parent.keys.splice(i, 0, midKey);
}
#insertNonFull(node, k) {
let i = node.keys.length - 1;
while (i >= 0 && k < node.keys[i]) i--;
if (node.leaf) {
node.keys.splice(i + 1, 0, k);
return;
}
i++;
if (node.children[i].keys.length === 2 * this.#t - 1) {
this.#splitChild(node, i);
if (k > node.keys[i]) i++;
}
this.#insertNonFull(node.children[i], k);
}
search(k, node = this.#root) {
let i = 0;
while (i < node.keys.length && k > node.keys[i]) i++;
if (i < node.keys.length && node.keys[i] === k) return true;
if (node.leaf) return false;
return this.search(k, node.children[i]);
}
insert(k) {
if (this.search(k)) return false; // duplicate — see Pitfalls
if (this.#root.keys.length === 2 * this.#t - 1) {
const newRoot = { keys: [], children: [this.#root], leaf: false };
this.#root = newRoot;
this.#splitChild(newRoot, 0);
}
this.#insertNonFull(this.#root, k);
return true;
}
// ---- delete ----
#getPred(node) {
while (!node.leaf) node = node.children[node.children.length - 1];
return node.keys[node.keys.length - 1];
}
#getSucc(node) {
while (!node.leaf) node = node.children[0];
return node.keys[0];
}
#borrowFromLeft(node, idx) {
const child = node.children[idx];
const sibling = node.children[idx - 1];
child.keys.unshift(node.keys[idx - 1]);
node.keys[idx - 1] = sibling.keys.pop();
if (!child.leaf) child.children.unshift(sibling.children.pop());
}
#borrowFromRight(node, idx) {
const child = node.children[idx];
const sibling = node.children[idx + 1];
child.keys.push(node.keys[idx]);
node.keys[idx] = sibling.keys.shift();
if (!child.leaf) child.children.push(sibling.children.shift());
}
#merge(node, idx) {
const child = node.children[idx];
const sibling = node.children[idx + 1];
child.keys.push(node.keys[idx], ...sibling.keys);
if (!child.leaf) child.children.push(...sibling.children);
node.keys.splice(idx, 1);
node.children.splice(idx + 1, 1);
}
#fill(node, idx) {
const t = this.#t;
if (idx > 0 && node.children[idx - 1].keys.length >= t) {
this.#borrowFromLeft(node, idx);
} else if (idx < node.children.length - 1 && node.children[idx + 1].keys.length >= t) {
this.#borrowFromRight(node, idx);
} else if (idx < node.children.length - 1) {
this.#merge(node, idx);
} else {
this.#merge(node, idx - 1); // idx was the last child — merge with its left sibling instead
}
}
#removeFromInternal(node, idx) {
const t = this.#t; // must check capacity — see Pitfalls
const k = node.keys[idx];
if (node.children[idx].keys.length >= t) {
const pred = this.#getPred(node.children[idx]);
node.keys[idx] = pred;
this.#remove(node.children[idx], pred);
} else if (node.children[idx + 1].keys.length >= t) {
const succ = this.#getSucc(node.children[idx + 1]);
node.keys[idx] = succ;
this.#remove(node.children[idx + 1], succ);
} else {
this.#merge(node, idx);
this.#remove(node.children[idx], k);
}
}
#remove(node, k) {
const t = this.#t;
let idx = 0;
while (idx < node.keys.length && node.keys[idx] < k) idx++;
if (idx < node.keys.length && node.keys[idx] === k) {
if (node.leaf) { node.keys.splice(idx, 1); return; }
this.#removeFromInternal(node, idx);
return;
}
if (node.leaf) return; // not present — delete() already checked search() first
if (node.children[idx].keys.length < t) this.#fill(node, idx); // must happen before descending — see Pitfalls
const nextIdx = Math.min(idx, node.children.length - 1);
this.#remove(node.children[nextIdx], k);
}
delete(k) {
if (!this.search(k)) return false;
this.#remove(this.#root, k);
if (this.#root.keys.length === 0 && !this.#root.leaf) {
this.#root = this.#root.children[0]; // root emptied by a merge — tree shrinks by one level
}
return true;
}
}The interactive demo above uses an equivalent set of functions with extra bookkeeping — a stable
id on every node, a recorded descent path, and a list of split/merge/borrow events — purely to drive the
highlighting and log text; the underlying splitting, insertion, and deletion logic is identical. Insert
was verified against a plain JavaScript Set as a reference model across 500 randomized
trials of 60 mixed inserts each (values drawn from a small range to force frequent splits and duplicate
attempts), checking after every single insert: every node's key count within [t - 1,
2t - 1] (root
exempt), every node's child count exactly one more than its key count, every node's keys strictly
sorted, every leaf at the identical depth, an in-order traversal matching the Set's
sorted contents exactly, and search agreeing with the Set for five random
probes after each insert — 30,000 inserts, zero mismatches. The checker was self-tested against two
deliberately broken variants first: swapping pop() for shift() in
#splitChild (caught at the third insert of the very first trial — in-order traversal came
back out of order) and dropping the z.children = y.children.splice(t, t) line (caught by
a crash the moment an internal node's own split fired, not a leaf's), before trusting a clean run on
the real code. Re-verified with a real click-driven fake-DOM harness against the exact shipped
functions: the loaded 10-through-90 sequence lands at height 3 with the exact node shapes named in
Pitfalls below, and inserting 75 against that loaded state logs a split of the 70, 80, 90
leaf (80 promoted) before placing 75, matching the scratch reference's own trace of the identical
sequence, and running both broken variants against the shipped functions confirmed the same failures
named in Pitfalls: the children-move bug crashes loading this very page's own 10-through-90 sequence
(not just a synthetic one), and the promoted-key bug leaves the shipped tree's own structure
misordered. See /tmp/btree/ref.js, test1.js, test2_broken.js,
test3_ascending.js, test4_pitfalls.js, test5_small_pitfall.js,
and /tmp/btree/harness.js/fake_dom.js/test_broken_children.js/
test_broken_shift.js, scratch, not committed.
Delete got the same two-layer treatment. A scratch reference implementation ran 500 trials of 60
randomized mixed insert/delete operations each (30,000 operations total, values drawn from a small range
to force frequent splits, merges, and borrows) against a plain Set model, checking after
every single operation the same invariants as insert plus one more (both insert and delete
results — present/absent — have to match the model exactly) — zero mismatches. The checker was
self-tested first against two deliberately broken delete variants: skipping the pre-emptive #fill
call before descending, and having #removeFromInternal always take the predecessor route
without checking either child's capacity first (both described in full in Pitfalls below) — both caught
immediately. Re-verified against the exact shipped Delete button through the same real click-driven
fake-DOM harness: starting from this page's own loaded 10-through-90 tree, deleting 30
merges the root's two children through separator 40 into [20, 40, 60], discovers the child
now holding 30 is also at the minimum, merges again through separator 40 into
[30, 40, 50], removes 30 directly, and then shrinks the root — landing on
[20, 60] over [10], [40, 50], [70, 80, 90], height 2. Deleting 10
next borrows instead: the sibling [40, 50] has a spare key, so 20 rotates down and 40
rotates up with no merge at all, landing on [40, 60] over [20], [50], [70, 80, 90].
Deleting 60 after that hits the internal-key case directly (60 is a root key): its
right child [70, 80, 90] has keys to spare, so the successor 70 is pulled up in its place,
landing on [40, 70] over [20], [50], [80, 90]. All three outcomes match the
class-based reference implementation's own trace of the identical sequence exactly, not just
independently plausible-looking trees.
Promoting the wrong key during a split silently breaks the tree's ordering, not just its
balance. The key that moves up during a split has to be y's new maximum after
the top t - 1 keys are cut away — y.keys.pop(), not
y.keys.shift(). Swap the two and the bug doesn't crash and doesn't look wrong at a
glance: inserting 1, 2, 3, 4 with the broken version produces a root of
[1] with children [2] and [3, 4] — every value from the input
is present somewhere, so a naive "does it contain everything" check would pass. But the parent key
1 is supposed to mean "everything left of me is < 1, everything right is
> 1," and the left child holds 2, which violates that outright. Checked
directly: calling search(2) against this broken tree returns false — it
compares 2 against the root's key 1, decides 2 belongs in the right subtree since 2 > 1,
and never looks left, even though 2 is sitting right there. An in-order traversal makes the same bug
visible from a different angle: it comes back 2, 1, 3, 4, not sorted, immediately.
Forgetting to move children during an internal-node split doesn't fail until the first
internal split — which this page's own loaded example reaches on its very last insert. The
first several splits while building the 10-through-90 demo only ever split leaves (leaves
have no children to move, so a version of #splitChild missing the
z.children = y.children.splice(t, t) line works by pure accident every time). The bug
stays invisible until a node that already has children becomes full and gets split — which,
tracing through this exact sequence, first happens splitting the root while inserting 90,
the ninth and last value. At that point z is created with an empty children
array but a promised two children (since z.leaf is false), and the very
next line that tries to read node.children[i].keys during the following descent hits
undefined and throws — confirmed by running the broken variant against this page's own
loaded sequence, not a synthetic one.
Skipping the duplicate check before inserting doesn't corrupt values — it corrupts the
"keys are sorted" guarantee everything else depends on. #insertNonFull's leaf
case only ever compares with < while finding where to splice a new key in; it has no
reason to also check ===, because insert is supposed to rule out duplicates
before it's ever called. Remove that guard and insert 10, 20, 30, 40, 20, 20: the tree
ends up with a node holding 20, 20 side by side, and the in-order traversal comes back
10, 20, 20, 20, 30, 40 — every value in non-decreasing order, easy to glance at and call
fine, but two adjacent keys are equal, which the strict ordering every proof and every
duplicate-free assumption on this page relies on forbids. Confirmed by running the exact broken
sequence above.
Skipping the pre-emptive #fill call doesn't crash — it just leaves a node
under the legal minimum, silently, until something else notices. Delete a value from a node
that's exactly at the minimum without first checking (and fixing) it, and the splice still "succeeds":
running this broken variant against this page's own shipped functions, deleting 30
from the loaded tree leaves the leaf that held it holding 0 keys — one below the
t - 1 = 1 minimum every complexity claim on this page assumes. Nothing about
search breaks immediately (the empty leaf just reports "not found" at that dead end, which
happens to be correct for anything that would've been there), and the very next insert(25)
silently "heals" the empty leaf by dropping 25 straight into it — so the bug never announces itself
with a wrong answer, only with a structure that's temporarily out of spec. Confirmed on the exact
shipped Delete/Insert buttons in that order, not reasoned about.
Choosing predecessor vs. successor without checking either child's capacity first can leave
a keyless "pass-through" node — the exact height blowup B-trees exist to prevent, smuggled back in
through delete. If #removeFromInternal always takes the predecessor route (skips
the node.children[idx].keys.length ≥ t check and the successor/merge fallbacks
entirely), deleting an internal key whose left child is already at the minimum pulls that
child's own minimum key up and then has to merge underneath to fix the resulting shortage — running
this broken variant against the shipped functions, deleting 40 (the loaded tree's own
root key) from the loaded tree leaves an internal node with 0 keys and exactly one child.
Every one of the tree's 8 remaining values is still search-able (checked directly, all
eight), so this bug is invisible to a pure correctness check — but it's added a level to that one path
without adding any branching, which is precisely the shape of degeneration the intro paragraph says a
B-tree can't suffer from. It shows up as a measurable regression, not just a theoretical one:
search(20), which the correct tree answers in 2 node visits (20 sits at the
root's own child, no need to reach a leaf), needs 3 visits after this bug — the demo's own
descent counter, not a hand count.
ext4/XFS on-disk structures all use B-tree variants for the identical reason a database
does: a directory with millions of entries still resolves a single filename lookup in a handful of
block reads.t = 2 case, just unpacked into individual two-way nodes — is simpler to
implement and just as fast in RAM.Time: a B-tree of minimum degree t holding n keys has
height at most log_t((n + 1) / 2) — the standard bound, not re-derived here. The payoff of
a large t is concrete: at t = 100, a million keys need a height of at most
2 (three levels total, root included) — three node reads to find any key among a million, versus a
perfectly balanced binary tree's roughly 20 levels for the same n. search,
insert, and delete all cost O(log_t n) node visits — delete's
fill (borrow or merge) is the same constant-work-per-level check as insert's split, just running on the
way down instead of being triggered by a value on the way up — each visit doing O(t)
work scanning that node's keys (or O(log t) with a binary search inside the node, for
implementations where t is large enough for that to matter) — O(t log_t n)
overall, which is why t is chosen to match a disk page's size exactly: large enough to
keep the tree shallow, small enough that scanning one full node is still cheap once it's already been
read into memory. Space: O(n); unlike the site's binary trees, a B-tree's
per-node overhead is dominated by the keys and child pointers a node holds (up to 2t - 1
and 2t respectively) rather than a fixed per-node cost, and typically runs well below one
pointer per key once t is large, the opposite of a binary tree's fixed two-pointers-per-key
floor.
See Choosing a Search Tree for why disk- or cache-backed storage is the one factor that settles this choice on its own, ahead of every other question the other four entries argue over.