Fixed Size Pages
A B tree stores keys in fixed size pages, usually a few kilobytes matching the disk block. A leaf page holds keys and values, an internal page holds keys and child pointers. Each page can hold only so many entries.
When a Page Is Full
Inserting into a full page would overflow it, so the engine performs a page split.
- The full page is divided into two pages, each roughly half full.
- A separator key that divides the two halves is pushed into the parent page.
- The parent now points to both children.
Splits Can Cascade
If the parent is itself full, it splits too, pushing a separator up another level. In the rare case the root splits, a new root is created and the tree grows one level taller. This is how a B tree stays balanced from the top.
Why It Stays Shallow
Because every leaf is the same distance from the root and each page fans out widely, even billions of keys sit only a handful of levels deep, so a lookup touches few pages.
Key idea
A B tree split divides a full page into two halves and promotes a separator key upward, possibly cascading to the root, which keeps the tree balanced and shallow.