■ B-Tree

Start — a phone book with tabbed pages. Imagine a giant phone book, but each page holds a whole block of names already in order, plus little tabs telling you which page to flip to next. To find "Khan," you don't read every page — you glance at the tabs, jump to the right block, and scan just that one. A B-tree is exactly this: a tree of fat "pages," each holding many sorted keys and signposts to the pages below. Few flips, fast find.

Build — why the pages are fat. The slow part of a database isn't comparing numbers; it's fetching a page from disk, which is roughly 100,000× slower than reading memory and always grabs a whole block (say 16 kB) at once. So we pack hundreds of keys into each node and read them in a single fetch. A node with $m$ children stores $m-1$ keys in sorted order, and the child sitting between two keys holds every value that falls between them. If each node carries about 100 keys, one node covers 100 records, its children cover $100\times100=10{,}000$, and three levels already reach a million. Worked number: with branching $\sim 100$, a million records sit only $\log_{100}(10^6)=3$ fetches deep.

Deepen — the precise rule. Formally, a B-tree of minimum degree $t$ keeps between $t-1$ and $2t-1$ keys in every non-root node (the root may hold fewer), and every leaf lies at the same depth, so the tree stays perfectly height-balanced. Its height obeys $h \le \log_t\!\frac{n+1}{2}$, giving search, insert, and delete in $O(\log_t n)$ disk accesses. Inserting splits a full node — its median key rises into the parent — while deleting borrows from or merges with a sibling to avoid underflow. In the sim, the n slider sets how many keys you feed in, and the preset menu changes the order they arrive in.

Try this in the sim above. Step through with Next while reading the pseudocode panel beside the animation — it states the genuine B-tree invariants ($\ge t-1$ keys per non-root node, split a full node on the way down). Switch the preset between Sorted and Random and watch how the per-step messages change as the keys are processed in different orders. Then slide n from 4 up to 16 and press Reset to load more keys, and use First / Last to jump straight to the ends of the trace.

Step 1 — Motivation: Disk I/O. In databases, data lives on disk. Disk read/write is 100,000× slower than RAM. Each disk read fetches a 'page' (4KB-16KB). B-tree node = one disk page, holding many keys (t ~ 50-1000). Tree height: log_t(n). For n=10^9, t=500: height ≤ 4. Only 4 disk reads to find any record!

Step 2 — Structure. Minimum degree t. Node properties: each non-root node has t-1 to 2t-1 keys. Children = keys+1. All leaves at same depth (height-balanced). Keys within a node are sorted. For a node with keys k_1,...,k_m and children C_0,...,C_m: C_i contains all keys between k_i and k_{i+1}.

Step 3 — Search O(log_t n) = O(log n / log t). At each node: binary search for key among up to 2t-1 keys O(log t), then recurse into child. Height: h ≤ log_t((n+1)/2). Total: O(h · log t) = O(log n). Disk accesses: O(h) = O(log_t n) — each level = one disk read.

Step 4 — Insert with Proactive Splitting. Search for insertion leaf. If any node on the path is full (2t-1 keys): split it before descending. Splitting: median key moves up to parent, node splits into two nodes of t-1 keys each. This ensures parent always has room for the new key. O(h) disk writes per insert.

Step 5 — Delete with Merge/Redistribute. Three cases: (1) Key in leaf with t keys — simple delete. (2) Key in internal node — replace with in-order successor/predecessor (from a child with t keys). (3) Key in node with t-1 keys — first redistribute from sibling (if sibling has t keys) or merge with sibling. O(h) disk accesses.

Step 6 — B+ Tree (Standard in Databases). B+ tree: all data stored in leaves. Internal nodes hold only keys for routing. Leaves linked in a sorted linked list — enables efficient range scans. MySQL InnoDB, PostgreSQL, SQLite, Oracle: all use B+ trees. B+ tree leaf scan: O(k) for k consecutive records — no tree traversal needed.