A B-tree stores real data in every node — internal
nodes and leaves both hold actual keys, and a search can succeed the moment it hits a match
partway down. A B+ tree changes one rule: internal nodes hold copies of keys used
purely to route a search, never the data itself, and every real key lives in a leaf.
Search always walks all the way to a leaf, even when it happens to pass a matching value on the
way — that sounds like it should be strictly worse, and for a single lookup it does give something
up: a B-tree search can terminate the instant it hits a match anywhere on the way down, while a B+
tree's always costs exactly the tree's height in node visits, no early exit possible. What it buys
back is bigger than that cost: since nothing but routing keys clutters
an internal node, more keys fit per node at a given page size, so the tree gets shallower for the
same n. And because every leaf holds real data and nothing but real data, the leaves
can be threaded together in a singly linked list, left to right — turning a range query
("every key between 40 and 80") from a scatter of independent searches into one descent followed
by a straight walk along that list. That's the whole reason B+ trees, not plain B-trees, are what
MySQL's InnoDB, PostgreSQL, and SQLite actually put behind a database index (B-Tree's own page
names this without building it — this page is that build).
The tree below loads the same 10, 20, 30, … 90 sequence
B-Tree's demo uses, for a direct side-by-side: same
nine values, same minimum degree t = 2 (1 to 3 keys per node), same starting height
of 3 — but every leaf here (the bottom row) is drawn with a dashed link to the leaf immediately to
its right, the actual linked list the reference implementation below maintains, not just a visual
suggestion. Leaves are shaded to tell them apart from the internal routing row above. Try
inserting 75: the leaf holding 70, 80, 90 is full, so it splits —
watch the log name the promoted separator (90) and confirm it's a copy: it
moves up into the parent and stays behind in the leaf, unlike B-Tree's split, which moves
its middle key up and out. Then insert 15 (lands in the first leaf, no split) and
insert 85 (splits the now-full 70, 75, 80 leaf again). Now try the
range query below for 40 to 80: the log reports exactly
how many internal nodes and how many leaves the scan touched — compare that count to what six
separate single-key searches would cost, printed alongside it. Finally, delete 90:
its leaf is down to one key, the legal minimum, so it borrows from its left sibling (which still
has a key to spare) rather than merging — watch the log show the sibling's own last key moving over (not the old
separator) and the parent's separator being recomputed from the leaf's new first key afterward, the
specific mechanic the Pitfalls section below verifies two ways to get wrong.
B-Tree's split cuts a full node's top t - 1 keys into a new sibling and moves the
single key between the two halves up into the parent — that key leaves the node it came
from entirely. A B+ tree's leaf split can't do that: every key has to stay findable in a leaf,
including whichever one ends up marking the boundary. Like B-Tree, this page's algorithm splits a
child before descending into it, the moment it's found to already hold 2t - 1
keys — the new key being inserted isn't part of the leaf yet and plays no role in the split itself.
So a full leaf's existing 2t - 1 keys alone split into two leaves of roughly even size
(this page's reference implementation splits at Math.ceil(n / 2), giving the left leaf
the larger half when the count is odd), and the new right leaf's own smallest key is
copied up into the parent as the routing separator — the leaf keeps it too. Only
after that split does the walk decide which of the two resulting leaves the new key
actually belongs in. Concretely, verified against the shipped script: the full 70, 80, 90
leaf splits on Math.ceil(3 / 2) = 2 — 70, 80 stay, 90 moves to
the new leaf alone — and 90 (the new leaf's own smallest, and only, key) is promoted as
a copy. Only then does 75 get compared against that new separator (75 < 90) and land in
the left leaf, which is why the leaf that ends up holding 75 is 70, 75, 80, not an even
half of four. The new leaf is spliced into the linked list at the same time (old leaf's
next becomes the new leaf, new leaf's next becomes whatever the old leaf
used to point to), so the moment the split finishes, a linked-list walk starting anywhere still
visits every leaf in order without needing to know a split just happened.
The copy-vs-move distinction only applies to leaves. An internal node in a B+ tree holds nothing but routing separators — no separator "belongs" to any one subtree the way a leaf's key belongs to that leaf — so splitting one is exactly B-Tree's own operation, move the true middle key up and out, no copy, no leaf, no linked list to maintain. Both algorithms use the same proactive, split-before-descending discipline B-Tree's own page describes in full: check whether the child about to be descended into is full before stepping into it, splitting there if so, which means (leaf or internal) a node is never entered already full and the whole walk stays a single top-down pass with no backtracking.
Search behaves like B-Tree's with one change: an internal node's keys are pure routing, so a
match there doesn't end the search — the walk continues to a leaf regardless, and the leaf is
where the real comparison happens. A range query for every key between
lo and hi reuses that same single descent to find the leaf holding
lo, then walks the linked list rightward, collecting matches and stopping the first
time a leaf's own maximum key exceeds hi — no further internal-node reads at all past
the first descent. Measured directly against this page's own loaded-and-modified demo tree (12
values — the "Try it" sequence above, through inserting 85 but before either delete — height 3):
a range query for 40 to 80 touches 2 internal nodes
(the one-time descent) and 4 leaves — 6 node visits total for
6 results. The same 6 values looked up as six independent single-key searches, B-Tree-style, cost
18 node visits — each of those 6 searches re-reads the same 2 internal
nodes from the root, 6 times each, where the linked range scan reads them once. The gap only
widens as node count grows or the tree gets deeper; the live "Range query"
button above runs this exact count against whatever the demo tree currently looks like, not a
fixed canned number.
B-Tree's borrow moves the parent's own separator key down into the shrinking child and pulls the sibling's outermost key up to replace it — legal there because that separator is real data, free to relocate. A B+ tree's separator is a copy; the leaf-level operations have to work differently, and getting this wrong is the specific, verified failure mode this page's Pitfalls section below documents with real numbers:
next has to skip over the absorbed one, pointing at whatever the absorbed leaf used
to point to.Verified directly against the shipped script's own state: continuing from the "Try it" sequence
above (load 10–90, insert 75, insert 15, insert 85), deleting 90 finds its leaf
down to a single key — the bare minimum — with a left sibling 80, 85 that has one
to spare. The borrow moves 85 (the sibling's real last key) over, the leaf briefly
holds 85, 90 before the delete removes 90, leaving just 85, and the
separator between them — previously 90, the value that no longer marks anything — is
recomputed as 85, the leaf's actual new minimum. A separate
verified case (not the default "Try it" path, but checked directly the same way): starting from a
fresh load and deleting 30, then 10, then 60, then 40 drives a leaf down to the
bare minimum with no sibling able to spare a key, forcing a merge instead of a borrow — the
leaf holding 40 and its neighbor holding 50 combine into one 40,
50 leaf, the parent's separator between them is dropped entirely (not folded in), and the
absorbed leaf's predecessor is re-pointed past it in the linked list — confirmed by walking the
full linked list afterward and getting the exact sorted remainder, not just checking the merged
leaf's own contents.
class BPlusTree {
#t;
#root;
constructor(t = 2) {
this.#t = t;
this.#root = { keys: [], children: [], leaf: true, next: null };
}
#splitLeaf(parent, i) {
const y = parent.children[i]; // full leaf, 2t - 1 keys
const z = { keys: y.keys.splice(Math.ceil(y.keys.length / 2)), children: [], leaf: true, next: y.next };
y.next = z;
const sep = z.keys[0]; // COPY up — stays in z too
parent.children.splice(i + 1, 0, z);
parent.keys.splice(i, 0, sep);
}
#splitInternal(parent, i) { // identical to B-Tree's own split
const t = this.#t;
const y = parent.children[i];
const z = { keys: y.keys.splice(t, t - 1), children: [], leaf: false, next: null };
const midKey = y.keys.pop(); // MOVED up — no copy, pure routing key
z.children = y.children.splice(t, t);
parent.children.splice(i + 1, 0, z);
parent.keys.splice(i, 0, midKey);
}
#insertNonFull(node, k) {
if (node.leaf) {
let i = node.keys.length - 1;
while (i >= 0 && k < node.keys[i]) i--;
node.keys.splice(i + 1, 0, k);
return;
}
let i = 0;
while (i < node.keys.length && k >= node.keys[i]) i++; // >= routes a match RIGHT — see Search
const child = node.children[i];
if (child.keys.length === 2 * this.#t - 1) {
child.leaf ? this.#splitLeaf(node, i) : this.#splitInternal(node, i);
if (k >= node.keys[i]) i++;
}
this.#insertNonFull(node.children[i], k);
}
insert(k) {
if (this.search(k)) return false; // duplicate — same guard as B-Tree
if (this.#root.keys.length === 2 * this.#t - 1) {
const newRoot = { keys: [], children: [this.#root], leaf: false, next: null };
this.#root = newRoot;
newRoot.children[0].leaf ? this.#splitLeaf(newRoot, 0) : this.#splitInternal(newRoot, 0);
}
this.#insertNonFull(this.#root, k);
return true;
}
#findLeaf(k, node = this.#root) {
if (node.leaf) return node;
let i = 0;
while (i < node.keys.length && k >= node.keys[i]) i++;
return this.#findLeaf(k, node.children[i]);
}
search(k) { return this.#findLeaf(k).keys.includes(k); } // always reaches a leaf — see Search
range(lo, hi) {
const out = [];
let leaf = this.#findLeaf(lo);
while (leaf) {
for (const k of leaf.keys) if (k >= lo && k <= hi) out.push(k);
if (leaf.keys.length && leaf.keys[leaf.keys.length - 1] > hi) break;
leaf = leaf.next; // the whole payoff — no re-descending
}
return out;
}
// ---- delete: borrow moves real leaf data, merge drops the separator, both fix `next` ----
#borrowLeaf(node, idx, fromLeft) {
if (fromLeft) {
const child = node.children[idx], sibling = node.children[idx - 1];
child.keys.unshift(sibling.keys.pop());
node.keys[idx - 1] = child.keys[0]; // recomputed, not swapped — see Pitfalls
} else {
const child = node.children[idx], sibling = node.children[idx + 1];
child.keys.push(sibling.keys.shift());
node.keys[idx] = sibling.keys[0];
}
}
#mergeLeaf(node, idx) {
const child = node.children[idx], sibling = node.children[idx + 1];
child.keys.push(...sibling.keys); // no separator folded in — see Pitfalls
child.next = sibling.next;
node.keys.splice(idx, 1);
node.children.splice(idx + 1, 1);
}
// #borrowInternal / #mergeInternal: identical to B-Tree's #fill helpers, omitted here — see
// b-tree.html's own reference implementation for the full internal-node borrow/merge code.
}Verified from scratch before writing a line of this page's prose: 500 trials of 60 randomized
mixed insert/delete/search/range operations each (30,000 operations total, values drawn from a
small range to force frequent splits, merges, and borrows) against a plain JavaScript
Set-plus-sorted-array model, checking after every single operation — insert
and delete results (present/absent) matching the model, five random search probes agreeing with
the model, a range query against a random [lo, hi] window matching an independent
filter of the model every fifth step, and a full structural invariant check (every node's key
count within [t - 1, 2t - 1] outside the root, every internal node's child count
exactly one more than its key count, every leaf at the identical depth, every node's own keys
strictly sorted, and — the B+-tree-specific check the other tree pages don't need — the leaf
linked list itself walked start to finish and confirmed strictly sorted with no gaps or
duplicates against the in-order traversal it should match). Zero mismatches across all 30,000
operations. Re-verified against the exact shipped functions (not the scratch prototype) through a
hand-rolled fake-DOM harness driving real Insert/Delete/Search/Range-query clicks: a further 300
trials of 50 mixed operations each (15,000 operations) against the same model, reading results
back out of the shipped log text rather than a return value, found zero mismatches; the "Try it"
sequence above traced exactly as described, and the range-query node-visit counts (2 internal + 4
leaves = 6, versus 18 for six independent searches) matched the scratch reference's own count
precisely.
Reusing B-Tree's borrow — move the old separator down, promote the sibling's key up —
looks plausible and corrupts the tree almost immediately. Swap this page's
#borrowLeaf for a literal copy of B-Tree's #borrowFromLeft (move the
parent's separator into the child, replace it with the sibling's popped key) and run the same
same-shaped stress harness against the exact shipped functions (200 trials, 60 mixed
insert/delete/search operations each): 119 of 200 trials fail an invariant, a
model mismatch, or throw outright, most within the first handful of operations. The
reason is structural, not a rare edge case: the "separator" being moved down is a copy
with no other owner, so pushing it into the child doesn't insert real data that belonged there —
it silently duplicates a value that's still sitting, correctly, somewhere in the leaf that
originally copied it up, or in a case checked directly, plants a value in a leaf that never had it
and never should. An in-order/linked-list walk of the resulting tree comes back with a value out
of order or duplicated almost every time, not "eventually, under some rare sequence."
Moving the real data correctly but forgetting to recompute the separator afterward
doesn't corrupt the tree's shape at all — it corrupts search
for the exact value that just moved. This is the more dangerous of the two bugs,
because every structural invariant this page checks (key counts, child counts, leaf depth, sorted
keys, even the linked-list walk) stays perfectly clean — the leaf really does hold the right keys
in the right order. Checked directly against the exact shipped functions (not just a scratch
reimplementation): patching this one broken variant in (leaf borrow moves the sibling's key
correctly, then simply skips updating node.keys[idx - 1]/node.keys[idx]
afterward), running 800 randomized 30-operation trials, then clicking Search for every value the
model still says is present finds the shipped Search button wrongly reporting "not found" for a
value that's really in the tree in 165 of 800 trials — the stale separator now
sits on the wrong side of the boundary it's supposed to describe, so a search for the just-moved
value follows the routing key straight past the leaf that actually holds it. Nothing about the
tree's own shape gives this away; only checking search's answer against an
independent model catches it, which is exactly why this page's verification harness
checks search results after every single operation rather than only at the end of a run.
WHERE age BETWEEN 20
AND 30, an index-ordered JOIN, a paginated query) reads only leaf/data pages
after the first descent, the same distinction measured above.ext4/XFS on-disk structures use B+-tree-shaped indexes for exactly
this reason: "list every file starting with a given prefix" is a range query.Time: identical asymptotic shape to B-Tree — height at most
log_t((n + 1) / 2), so search, insert, and delete
all cost O(log_t n) node visits, each visit doing O(t) work scanning that
node's keys. A range query returning k results costs
O(log_t n + k / t): one descent to find the start, then O(k / t) leaf
reads via the linked list, with zero further internal-node reads regardless of how
large k gets — the concrete 2-internal/4-leaf split measured above for one small
example, not just the asymptotic shape. Space: O(n), same as B-Tree,
plus one extra pointer per leaf for the linked list — negligible next to the O(t) keys
and child pointers each node already carries.
See Choosing a Search Tree for how B+ Tree fits alongside B-Tree and the site's other disk/cache-aware entries.