The Page Split Climbs Toward the Root
A sorted index is not a sorted array with better manners.
If every insertion had to slide half the file, the index would spend its life making room. If every key lived in its own pointer node, the search path would be too tall for storage. B-trees won because they turned the problem into a page budget:
put many ordered keys in one page
keep every leaf at the same depth
split only when a page is full
That is the operating shape behind the theorem and the engineering habit. Bayer and McCreight framed the original problem as maintaining a large ordered index on a backing store such as a disk or drum, where only small parts of the index fit in main memory at once.1 Their abstraction was not “a clever binary tree.” It was a tree whose nodes are pages.
The page is the unit that matters.
The Broad Node
A B-tree page carries several keys and several child pointers. For a page capacity controlled by some device-dependent parameter \(k\), Bayer and McCreight’s paper describes pages that can hold up to \(2k\) keys, with ordinary non-root pages kept at least half full. The important consequences are:
- search, insertion, and deletion take time proportional to \(\log_k I\) for an index of size \(I\);
- storage utilization is at least 50 percent in their model;
- all root-to-leaf paths have the same length;
- splits start at leaves and propagate upward;
- a root split is the only way the tree height increases.2
That last line is the one to keep on the mental clipboard. A B-tree does not rebalance by rotating after every local tremor. A full page splits. The split creates a separator key for the parent. If the parent is now full, the same repair climbs one level. Most inserts never reach the root. Occasionally one does, and the whole tree gets one level taller.
Comer’s 1979 survey calls the B-tree a de facto standard index organization in database systems and spends much of its attention on variants, especially the B+-tree.3 In a B+ tree, data entries live in the leaves and internal pages mostly route searches. That is the shape used by many storage engines because it makes range scans natural: find the first leaf, then walk leaf pages in key order.
SQLite’s file-format document is a useful concrete witness. It describes B-tree pages as either leaf pages or interior pages, with interior pages holding \(K\) keys and \(K+1\) child-page pointers. It also states the well-formedness condition that children of an interior page have the same depth.4
The lab below is a small B+ tree, not SQLite. It keeps unique integer keys, stores payloads only implicitly in leaves, promotes the first key of the right leaf after a split, and counts a toy “page write” whenever an insertion dirties a page. There is no deletion, WAL, latch coupling, prefix compression, variable cell size, overflow page, free-list, MVCC, or page cache policy. The point is the page-split mechanism.
Lab: Insert Until A Page Cracks
Deterministic toy B+ tree. The audit checks sorted leaves, equal leaf depth, separator routing, occupancy bounds, split accounting, finite metrics, and that every inserted key routes back to the leaf that stores it.
With the default settings, the lab inserts keys 1 through 42 into pages that
hold at most five keys. The final tree has:
height: 3 page levels
pages: 18
leaf pages: 14
splits: 15
root splits: 2
average leaf fill: 60.0%
page writes/insert: 1.71
The low fill is not a bug in the audit. It is a consequence of naive half splits under append-only insertion. Every time the rightmost leaf overflows, it is split roughly in half, then future keys go to the new rightmost page. Many old leaves remain half full. Real engines often have extra policies for right-edge growth, fill factors, bulk loading, and page compaction. This lab is showing the bare split rule.
Switch Insert order to seeded shuffle. With the same page capacity and number of keys, the final run ends with 15 pages, 12 splits, and 76.4 percent average leaf fill. Random-looking inserts revisit old leaves and use space that append-only splitting left behind.
Now increase Max keys per page. In the append-only run with 42 inserts:
max keys 3: height 4, pages 31, splits 27, 2.29 writes/insert
max keys 5: height 3, pages 18, splits 15, 1.71 writes/insert
max keys 7: height 3, pages 13, splits 10, 1.48 writes/insert
max keys 9: height 2, pages 9, splits 7, 1.33 writes/insert
This is the fanout bargain in miniature. Larger pages make each inspected node more expensive internally, but they reduce the number of pages on the route from root to leaf. On storage, that is usually the right trade: a page read can buy many key comparisons.
The implementation is inspectable:
assets/js/btree-split-lab.js.
You can reproduce the audit from Node. It treats each run as ten named invariants: balanced leaves, page occupancy, separator shape, sorted page keys, leaf-chain order, route correctness, internal child counts, split accounting, state key counts, and finite summary metrics.
const lab = require("./assets/js/btree-split-lab.js");
const EXPECTED_GRID_SHAPE = [
"patterns=append/reverse/shuffle/alternating",
"maxKeys=3/5/7/9",
"counts=12/31/64",
"seeds=3/17"
];
const EXPECTED_BY_PATTERN = [
"pattern=append:cases=24:checks=240/240:height=2..4:pages=3..48:leaves=2..32:splits=1..44:fill=0.571..0.689",
"pattern=reverse:cases=24:checks=240/240:height=2..5:pages=3..58:leaves=2..32:splits=1..53:fill=0.571..0.689",
"pattern=shuffle:cases=24:checks=240/240:height=2..4:pages=3..42:leaves=2..28:splits=1..38:fill=0.600..0.886",
"pattern=alternating:cases=24:checks=240/240:height=2..5:pages=3..53:leaves=2..32:splits=1..48:fill=0.571..0.689"
];
const EXPECTED_BY_MAX_KEYS = [
"maxKeys=3:cases=24:checks=240/240:height=3..5:pages=8..58:leaves=5..32:splits=5..53:fill=0.667..0.861",
"maxKeys=5:cases=24:checks=240/240:height=2..3:pages=4..28:leaves=3..21:splits=2..25:fill=0.600..0.886",
"maxKeys=7:cases=24:checks=240/240:height=2..3:pages=3..20:leaves=2..16:splits=1..17:fill=0.571..0.857",
"maxKeys=9:cases=24:checks=240/240:height=2..3:pages=3..15:leaves=2..12:splits=1..12:fill=0.574..0.861"
];
const EXPECTED_BY_COUNT = [
"count=12:cases=32:checks=320/320:height=2..3:pages=3..9:leaves=2..6:splits=1..6:fill=0.571..0.857",
"count=31:cases=32:checks=320/320:height=2..4:pages=5..26:leaves=4..15:splits=3..22:fill=0.574..0.886",
"count=64:cases=32:checks=320/320:height=2..5:pages=11..58:leaves=10..32:splits=9..53:fill=0.571..0.762"
];
const EXPECTED_CHECK_SEQUENCE = [
{ name: "all-leaves-balanced", ok: true },
{ name: "finite-summary-metrics", ok: true },
{ name: "internal-child-counts", ok: true },
{ name: "leaf-chain-sorted", ok: true },
{ name: "page-occupancy", ok: true },
{ name: "search-routes-to-key", ok: true },
{ name: "separator-min-keys", ok: true },
{ name: "keys-sorted-within-pages", ok: true },
{ name: "split-accounting", ok: true },
{ name: "state-key-counts", ok: true }
];
const EXPECTED_CHECK_NAMES = EXPECTED_CHECK_SEQUENCE
.map((check) => check.name)
.sort();
const EXPECTED_CASES = 4 * 4 * 3 * 2;
const EXPECTED_CHECKS = EXPECTED_CASES * EXPECTED_CHECK_SEQUENCE.length;
function sameList(actual, expected) {
return actual.length === expected.length &&
actual.every((value, index) => value === expected[index]);
}
function sameJson(actual, expected) {
return JSON.stringify(actual) === JSON.stringify(expected);
}
function fixed3(value) {
return Number(value).toFixed(3);
}
function range(values) {
return `${Math.min(...values)}..${Math.max(...values)}`;
}
function groupShape(name, rows) {
return `${name}:cases=${rows.length}:` +
`checks=${rows.reduce((sum, row) => sum + row.passedChecks, 0)}/` +
`${rows.reduce((sum, row) => sum + row.totalChecks, 0)}:` +
`height=${range(rows.map((row) => row.height))}:` +
`pages=${range(rows.map((row) => row.pages))}:` +
`leaves=${range(rows.map((row) => row.leafPages))}:` +
`splits=${range(rows.map((row) => row.splits))}:` +
`fill=${fixed3(Math.min(...rows.map((row) => row.avgLeafFill)))}..` +
`${fixed3(Math.max(...rows.map((row) => row.avgLeafFill)))}`;
}
function groupBy(audit, key) {
return Array.from(new Set(audit.cases.map((row) => row[key]))).map((value) =>
groupShape(`${key}=${value}`, audit.cases.filter((row) => row[key] === value))
);
}
function uniqueNumbers(audit, key) {
return Array.from(new Set(audit.cases.map((row) => row[key])))
.sort((a, b) => a - b)
.join("/");
}
const audit = lab.auditBtreeSplitLab();
const shape = {
byCount: groupBy(audit, "count"),
byMaxKeys: groupBy(audit, "maxKeys"),
byPattern: groupBy(audit, "pattern"),
checkNames: Array.from(new Set(audit.cases.flatMap(
(row) => row.checks.map((check) => check.name)
))).sort(),
grid: [
`patterns=${Array.from(new Set(audit.cases.map((row) => row.pattern))).join("/")}`,
`maxKeys=${uniqueNumbers(audit, "maxKeys")}`,
`counts=${uniqueNumbers(audit, "count")}`,
`seeds=${uniqueNumbers(audit, "seed")}`
]
};
const checkRowDrifts = audit.cases.map((row) => ({
key: `${row.pattern}/${row.maxKeys}/${row.count}/${row.seed}`,
checks: row.checks.map((check) => ({
name: check.name,
ok: check.ok
}))
})).filter((row) => !sameJson(row.checks, EXPECTED_CHECK_SEQUENCE));
const shapeErrors = [];
if (!sameList(shape.grid, EXPECTED_GRID_SHAPE)) {
shapeErrors.push({ name: "grid", actual: shape.grid, expected: EXPECTED_GRID_SHAPE });
}
if (!sameList(shape.byPattern, EXPECTED_BY_PATTERN)) {
shapeErrors.push({
name: "byPattern",
actual: shape.byPattern,
expected: EXPECTED_BY_PATTERN
});
}
if (!sameList(shape.byMaxKeys, EXPECTED_BY_MAX_KEYS)) {
shapeErrors.push({
name: "byMaxKeys",
actual: shape.byMaxKeys,
expected: EXPECTED_BY_MAX_KEYS
});
}
if (!sameList(shape.byCount, EXPECTED_BY_COUNT)) {
shapeErrors.push({ name: "byCount", actual: shape.byCount, expected: EXPECTED_BY_COUNT });
}
if (!sameList(shape.checkNames, EXPECTED_CHECK_NAMES)) {
shapeErrors.push({
name: "checkNames",
actual: shape.checkNames,
expected: EXPECTED_CHECK_NAMES
});
}
if (checkRowDrifts.length) {
shapeErrors.push({
name: "checkRows",
actual: checkRowDrifts.slice(0, 10),
expected: EXPECTED_CHECK_SEQUENCE
});
}
const summary =
`${audit.passed}/${audit.total} cases and ` +
`${audit.passedChecks}/${audit.totalChecks} checks passed`;
const failedCases = audit.cases.filter(
(row) => !row.passed || row.passedChecks !== row.totalChecks
);
if (shapeErrors.length ||
failedCases.length ||
!audit.ok ||
audit.cases.length !== EXPECTED_CASES ||
audit.total !== EXPECTED_CASES ||
audit.totalChecks !== EXPECTED_CHECKS ||
audit.passed !== audit.total ||
audit.passedChecks !== audit.totalChecks) {
throw new Error(JSON.stringify({
summary,
shapeErrors,
errors: audit.errors.slice(0, 10),
failedCases: failedCases.slice(0, 10),
totals: {
cases: audit.cases.length,
passed: audit.passed,
passedChecks: audit.passedChecks,
total: audit.total,
totalChecks: audit.totalChecks
}
}, null, 2));
}
console.table(audit.cases.slice(0, 8).map((row) => ({
pattern: row.patternLabel,
maxKeys: row.maxKeys,
count: row.count,
seed: row.seed,
height: row.height,
pages: row.pages,
leafPages: row.leafPages,
splits: row.splits,
checks: `${row.passedChecks}/${row.totalChecks}`,
fill: row.avgLeafFill.toFixed(3)
})));
console.log(summary);
That grid covers four insert orders, four page capacities, three key counts, and two shuffle seeds. Each row carries the failed check names, so a broken separator or occupancy invariant has a concrete reproducing case.
What A Split Certifies
Here is the insertion repair in the toy B+ tree:
search from root to the target leaf
insert the key into that sorted leaf
if the leaf still fits:
stop
split the leaf into two leaves
promote the first key of the right leaf to the parent
if the parent overflows:
split the parent and promote its middle separator
if the root overflows:
create a new root
A split is not merely an allocation event. It is a proof obligation. After the split:
- the leaves must still appear in sorted order;
- every leaf must still sit at the same depth;
- every internal page with \(K\) separator keys must have \(K+1\) child pointers;
- each separator must route keys to the same leaf a search would later inspect;
- non-root pages must not exceed capacity or fall below the chosen occupancy floor.
That is why the lab’s audit is more important than the picture. Pretty pages can hide a broken separator. The invariant is the thing being drawn.
The Cost Is Bursty
B+ tree insert cost is pleasantly small most of the time. One search path is read, one leaf is changed, and the update is done.
The burst arrives when a page is full. The insertion dirties the leaf, allocates a sibling, rewrites separators, and may dirty each ancestor up to the root. That is not the same shape as an LSM tree compaction bill, but it is still a write-amplification story: maintenance work is concentrated at structural boundaries.
The burst is also why concurrency protocols around B-trees are careful. Comer discusses the multiuser problem because reserving too much of the path blocks other updates, while reserving too little can force the operation to restart when the page structure changes under it.5 Modern engines vary in the details, but the shape is inherited from the same page-split fact.
What This Toy Leaves Out
The lab uses fixed-size integer keys, which makes every page hold exactly
maxKeys keys. Real database pages are messier. SQLite’s format, for example,
has page headers, cell pointer arrays, unallocated space, cell content areas,
reserved regions, and overflow pages for payloads that do not fit within the
page budget.6 A page can be “full” because of bytes, not just
because of a clean key count.
The lab also omits deletion. Deletion has its own repair work: redistribution, merge, free-space management, and sometimes deliberately postponed cleanup. It omits logging and recovery. A page split that looks local in memory must become durable without letting a crash publish half a tree.
So the simulator is not a storage-engine benchmark. It is a mechanical cross-section. When a B+ tree works, this is the core receipt:
broad pages make the tree shallow
sorted leaves preserve range order
splits repair overflow locally
separator keys make the repair searchable
root splits are the only height increases
The index grows by splitting pages.
The split climbs only when it must.
-
Rudolf Bayer and Edward M. McCreight, “Organization and maintenance of large ordered indexes”, Acta Informatica 1, 1972, pp. 173-189. The Springer abstract describes the disk/drum backing-store model, the \(\log_k I\) operation bound, at-least-50-percent storage utilization, and the use of pages organized as B-trees. ↩
-
Bayer and McCreight’s Boeing technical-report version, “Organization and Maintenance of Large Ordered Indices”, July 1970. The report states that pages can hold up to \(2k\) keys, that splits and catenations start at leaves and propagate toward the root, and that root split is the only height-increase event. ↩
-
Douglas Comer, “The Ubiquitous B-Tree”, ACM Computing Surveys 11(2), 1979, pp. 121-137. Public PDF copy: https://carlosproal.com/ir/papers/p121-comer.pdf. ↩
-
SQLite, “Database File Format: B-tree Pages”. The document describes table and index b-trees, leaf and interior pages, interior pages with \(K\) keys and \(K+1\) child-page pointers, ordered separator semantics, and equal child depth in well-formed databases. ↩
-
Comer, “The Ubiquitous B-Tree,” Section 4, “B-Trees in a Multiuser Environment,” discusses why reserving an entire root-to-leaf path is undesirable and why reserving too few nodes can force an update to restart. ↩
-
SQLite, “Database File Format: B-tree Pages”, page layout and overflow discussion. ↩