Why do databases prefer B-Trees/B+ Trees over Binary Search Trees?

Difficulty: 5/10

B‑Tree vs BST, Disk I/O, Cache locality

Database Index Trees

Databases operate primarily on storage systems where disk or SSD I/O is far more expensive than an in-memory pointer operation. B-Trees and B+ Trees have high branching factors, which make the tree shallow and reduce the number of pages that must be read. B+ Trees also place records or record pointers in leaves and link the leaves, making range scans efficient.

javascript

1
High fan-out reduces tree height.
2
Nodes are designed around storage pages or blocks.
3
Fewer levels mean fewer I/O operations.
4
B+ Tree leaves support efficient sequential and range scans.
5
Database indexes need predictable performance at large scale.

Scenario Questions

0-2 years experience

2-5 years experience

Follow-up Questions