THE FOLD / GRIND / THE MAINFRAME / THE B-TREE
THE B-TREE
a balanced tree that keeps all leaves level
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A B-tree is the balanced search tree that runs databases and filesystems. Unlike a binary tree, each node holds many keys (and many children), so the tree stays short and bushy — ideal when each node is a disk block. It self-balances by splitting a full node and pushing its middle key up, which keeps every leaf at exactly the same depth, no matter the insertion order. Keys stay sorted, and every node (except the root) stays between half-full and full.
LIT verified live: after random insertions, an in-order walk yields the sorted keys, all leaves share one depth, and every node’s key count stays within the B-tree bounds (window.__btree). FIG no framing; exact structural checks.
LIT verified live: after random insertions, an in-order walk yields the sorted keys, all leaves share one depth, and every node’s key count stays within the B-tree bounds (window.__btree). FIG no framing; exact structural checks.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-mainframe — the machine mind’s index; B-trees are how it keeps millions of records sorted on disk with a handful of block reads. AVAN (AI) built the instrument: the multi-key nodes, the split-on-full with middle-key promotion, and the sorted + all-leaves-level + key-bounds checks.
Credit as content: Rudolf Bayer & Edward McCreight (1970). The weave: David names the-mainframe; I insert keys into wide nodes, split any that fill by pushing the median up, and confirm the tree stays perfectly balanced — all leaves at one depth, keys sorted, every node within bounds.
Credit as content: Rudolf Bayer & Edward McCreight (1970). The weave: David names the-mainframe; I insert keys into wide nodes, split any that fill by pushing the median up, and confirm the tree stays perfectly balanced — all leaves at one depth, keys sorted, every node within bounds.
3 ONE DIMENSION
A node fills (2t−1 keys) → split at the median: median moves up to the parent, the rest becomes two half-nodes. This keeps all leaves at the same depth as the tree grows upward.
4 TWO DIMENSIONS · INTERACTIVE
A B-tree drawn with its multi-key nodes; insert keys and watch it split and stay balanced, checked.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a tree kept perfectly level.
AVAN’s addition (the inverse-companion): keep a search tree balanced not by rotations but by fat nodes that split upward — a full node promotes its median to the parent, so the tree grows at the root and all leaves stay level. The inverse of ‘a binary tree that can grow lopsided’ is ‘wide nodes that split and push up — balance for free.’ Magenta is the deep, thin, rotation-balanced tree; green is the short, wide, self-leveling B-tree. Balance by splitting, not rotating.
LIT Genuine B-tree (Rudolf Bayer & Edward McCreight 1970), minimum degree t=3 (keys 2..5). Verified live: over 500 random insertion sequences, an in-order traversal yields the sorted keys (window.__btree.sorted), all leaves lie at a single depth — perfectly balanced (window.__btree.balanced) — and every node's key count stays within [t−1, 2t−1] (window.__btree.bounds).
FIG No framing: the multi-key nodes, the split-on-full with median promotion, and the sorted + all-leaves-level + key-bounds checks run in-browser and agree. Honest note: a standard B-tree uses an odd maximum key count (2t−1) so a full node splits evenly (t−1 left, median up, t−1 right) — here t=3. The AVAN inverse is honest — keeping balance by fat nodes that split upward (median to the parent, tree grows at the root) rather than by rotations; magenta is the deep rotation-balanced binary tree, green the short self-leveling B-tree.
FIG No framing: the multi-key nodes, the split-on-full with median promotion, and the sorted + all-leaves-level + key-bounds checks run in-browser and agree. Honest note: a standard B-tree uses an odd maximum key count (2t−1) so a full node splits evenly (t−1 left, median up, t−1 right) — here t=3. The AVAN inverse is honest — keeping balance by fat nodes that split upward (median to the parent, tree grows at the root) rather than by rotations; magenta is the deep rotation-balanced binary tree, green the short self-leveling B-tree.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MAINFRAME · David Lee Wise (ROOT0), with AVAN