What a B Tree Engine Is
A B tree is the classic on disk index used by engines like InnoDB and most relational databases. It stores keys in sorted order across fixed size blocks called pages, usually four to sixteen kilobytes each.
- Internal pages hold keys and pointers to child pages.
- Leaf pages hold the actual rows or row pointers.
- The tree stays balanced, so every leaf sits at the same depth.
Why It Stays Shallow
Each page holds hundreds of keys, so the tree has a very high fanout. A few levels can index billions of rows. A lookup walks from the root down to a leaf, touching only as many pages as the tree is deep, often three or four.
How Writes Work
A write finds the target leaf and updates it in place. If a page overflows, it splits into two. This in place style gives predictable read latency but means random writes scatter across the disk.
Key idea
A B tree stores sorted keys in balanced fixed size pages, giving fast point lookups and range scans by updating data in place.