THE B-PLUS TREE

The balanced, disk-friendly index: internal nodes only route, and every key and value lives in the leaves — which are linked in order so a range scan just walks the chain. Every node stays at least half full; a full node splits and can grow the height. Rendered, not quoted: the tree below is built live by inserting 1…12, then verified exhaustively.

SOURCE Comer, D. — The Ubiquitous B-Tree, ACM Computing Surveys 11(2):121–137 (1979); on Bayer & McCreight (1972).

Blue Team · builds & defends
3

THE MODEL

Order m = 4: up to 3 keys per node, split on the 4th. Internal keys are separators only — a key k descends right when k ≥ sep. All values sit in leaves; each leaf holds a next pointer to its right neighbour.

Invariants, checked exhaustively: keys sorted within every node; all leaves at one depth; every non-root node ≥ ceil(m/2)=2 full; every value reachable in a leaf; each separator equals the minimum key of its right subtree.

5

THE LINEAGE

The index behind nearly every SQL database. It is the-b-tree specialised for disk pages: Bayer's balanced multiway tree with all data pushed into linked leaves, so a page holds only routing keys (higher fan-out, shallower tree) and range queries become a sequential chain walk instead of an in-order traversal.

7

THE WITNESS

Re-checks the displayed tree live — flips red if the Red Team tampers.

checking…
The Machine
4

DATA IN IN ↓

Insert this sequence into an empty B+ tree, in order:

0

THE PANEL LIT

The live tree after all inserts. Purple = routing nodes, green = leaves; the leaf chain (→) is the range-scan path.

router   leaf · values live here
8

DATA OUT OUT ↓

Point lookup find(9) and range scan [4, 9] walked over the leaf chain:

…
Red Team · attacks & breaks
1

THE ADVERSARY WALL

"Just sort the keys in one big leaf." — then every insert shifts O(n) keys and each split rewrites a whole page. The tree exists to bound work at O(log n) per op and to keep pages half full so disk reads stay few.
"Skip the min-fullness rule to avoid splits." — nodes drift to one key, fan-out collapses, height blows up, and the balance guarantee is gone. That exact attack is wired into window 6.
2

THE GRAVEYARD

A B+ tree stores values in internal nodes too. → No — internal nodes hold only separators; all values are in leaves. That is the B+ vs. plain B-tree distinction.

Range scans do an in-order tree traversal. → They descend once to the low key, then follow leaf next pointers — sequential, cache-friendly.

Leaves can sit at different depths if it saves a split. → Never. Growth happens only at the root, so all leaves stay at one depth — perfect balance.

6

THE TAMPER

Skip the min-fullness invariant on a split: bias it 1 + 3 so the left leaf is left under-full. Balance is lost — the Witness (7) catches it live.

state: clean