Why are B+ trees commonly used for database indexes?
Interview preparation resource from Gate Smashers.
B+ trees are used for database indexes because they remain balanced and shallow (high fan-out), which keeps page accesses low and lookup cost predictable as the index grows. Internal nodes store search keys to guide navigation while actual row references or data entries live at the leaf level; leaves are usually linked in key order, enabling both fast point lookups and efficient range or ordered scans.
Balanced, predictable height
All leaves in a B+ tree are at the same depth, so lookup cost remains predictable as the index grows. This predictable, balanced height is important because disk or page I/O is much more expensive than in-memory comparisons.
High fan-out and shallow trees
Database pages can hold many keys and child pointers, so each internal node can have many children (high fan-out). That high fan-out keeps the tree shallow, which reduces the number of page accesses required to find a key.
Leaf-level storage and linked leaves
Search keys are stored in internal nodes to guide navigation, while the actual row references or data entries are kept at the leaf level. Leaf nodes are usually linked in key order, so once the DBMS finds the first matching leaf entry it can continue through neighboring leaves efficiently.
Supported operations
Because of the structure above, B+ trees support both fast point lookups and efficient sequential access patterns, making them practical for many database workloads.
- Equality search: Navigate quickly to a key.
- Range search: Find the starting key and scan linked leaves.
- ORDER BY / ordered scans: Keys are maintained in sorted order for efficient ordered retrieval.
- Large datasets: Balanced height keeps search cost predictable as the index grows.