B-Tree Insert (how an index grows)
Medium+95 XPA BST can grow into a lopsided line. A B-tree stays short by SPLITTING: when a node overfills, its middle key jumps up. Watch it stay balanced.
Where it breaks
This is exactly the input that turns a plain BST into a useless leaning line.See what happens when you don't.
No visualization loaded.
Watch
—
Press Run to begin.
A real database index isn't a binary search tree — it's a B-tree. The difference: a B-tree node holds MANY keys, and the tree refuses to grow tall. Whenever a node gets too full, it bursts apart and its middle key is pushed UP a level. That single move — the split — is what keeps the tree short and perfectly balanced no matter what order the keys arrive in. Press Run and watch keys drop into leaves, then watch a full node split and push its middle up.
▸Why not just use a binary search tree for an index?
Because a BST only stays fast if it stays balanced — and feed it already-sorted keys (1, 2, 3, 4…) and it degenerates into a straight downward line, slow as scanning a list. A B-tree is built so it CAN'T lean: it grows only at the root, by splitting, so every leaf is always the same depth. Balanced by construction, not by luck.
▸What exactly is a 'split'?
Each node has a maximum number of keys it's allowed to hold (here, 3). When inserting a key would push a node over that limit, the node splits in two: the MIDDLE key moves up into the parent, and the keys to its left and right become two separate child nodes. The parent now has one more key and one more child. It's the overflow valve that keeps every node small.
▸How does the tree get taller, then?
Only one way: when the ROOT itself splits. Its middle key becomes a brand-new root all on its own, with the two halves as its children — so the whole tree gains exactly one level, all at once, from the top. Because growth always happens at the root and pushes every leaf down together, the leaves stay at equal depth. That top-down growth is the secret to staying balanced.
▸Why does holding many keys per node make it fast?
Height is what costs you — each level down is (in a real database) a slow trip to disk. A binary tree branches just 2 ways per level, so it needs many levels. A B-tree node holds dozens or hundreds of keys, so each node branches dozens of ways — the tree gets very 'bushy' and very SHORT. A few levels can index millions of rows, so a lookup touches only a handful of nodes.
▸Is the split ever a chain reaction?
Yes. When a node splits and pushes its middle key up, the PARENT might now be over its own limit — so it splits too, pushing ITS middle up, and so on. In the worst case the splits cascade all the way to the root, which then splits and makes the tree one taller. That cascade is rare but it's exactly how the balance is maintained from the bottom up.
How the work grows
O(log n) — insert and search is excellent — barely grows. Because the B-tree stays balanced by construction (it only grows at the root via splits), its height is about log n for ANY insertion order — never the O(n) line a BST can degrade into. Each insert walks down one path (≈ height) to a leaf, then maybe cascades a split back up the same path, so it's O(log n). With wide nodes the log's base is large, making the real tree only a few levels deep. Space is one slot per key, O(n).
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.