B+ Trees
All values in leaves, leaves linked. The index structure behind almost every relational PK.
Level: intermediate
What is it?
A B+ tree is a balanced multiway search tree in which internal nodes guide the search and all data entries or record pointers reside in the leaves. Leaf pages are often linked in key order, making range scans efficient.
Why does it matter?
Database indexes must support more than finding one exact key. B+ trees balance point lookups, inserts, deletes, and ordered range scans while keeping most nodes aligned with storage pages.
Mental model
Internal nodes are signposts; the leaves are the ordered index. The root-to-leaf path locates a key, while a range query walks successive leaf pages rather than restarting each search.
How it works
- High fan-out keeps the index height small and limits page reads.
- Leaf linkage supports range scans and ordered iteration.
- Node splits and merges maintain balance and occupancy after inserts/deletes.
- Clustered versus secondary index organization changes what a leaf entry references and how table rows are accessed.
- Index maintenance adds write amplification and storage overhead; every possible query does not benefit from an index.
Steps
- Start at the root and follow separators to the leaf interval containing key K.
- Search the leaf for K and retrieve the row identifier or clustered record.
- For a range [K1,K2], find K1 then traverse linked leaves until K2.
- On insert overflow, split the leaf and propagate a separator to the parent.
Real-world usage
- Understanding primary-key indexes in relational databases.
- Explaining range scans, ordering, and index maintenance.
- Reading query plans for index scans and index-only scans.
Common mistakes
- Calling every index a B+ tree; databases may use hash, bitmap, inverted, or other structures.
- Assuming an index always makes queries faster.
- Ignoring the cost of leaf splits, page writes, and index maintenance.
Interview questions
Why do B+ tree indexes support range queries well?
Values are stored in sorted leaves that can be traversed sequentially after finding the first key.
Why might an optimizer choose a sequential scan over a B+ tree index?
If many rows are needed or estimates make random index/table access more expensive than scanning pages, a sequential scan may be cheaper.