The Workhorse Index
Most database indexes are B trees, specifically the B plus tree variant. They keep data sorted and allow lookups, range scans, and ordered access in logarithmic time with very few page reads.
Structure
- Internal pages hold separator keys and pointers to child pages.
- Leaf pages hold the indexed keys and pointers to the actual rows.
- Leaves are linked in a sibling chain so a range scan walks left to right without revisiting parents.
- The tree stays balanced, so every leaf is the same depth from the root.
Splits and Height
When a leaf fills, it splits into two and pushes a separator key up to the parent. Splits can cascade to the root, which is the only way the tree grows taller. Because each page holds hundreds of keys, even billions of rows need only a handful of levels, so a lookup touches few pages.
Key idea
A B plus tree keeps keys sorted in balanced leaf pages linked for range scans, and page splits that cascade upward keep the tree shallow so lookups touch only a few pages.