← Back to the trees page
B-Tree / B+ Tree
Wide, shallow trees storing hundreds of keys per node — designed so each node is one disk page. The tree behind almost every database.
What to know
- High fanout means height 3–4 even for billions of keys.
- B+ trees keep values only in leaves and chain leaves for fast range scans.
- Nodes split when full and merge when underfull, staying balanced.
In the wild: MySQL InnoDB, PostgreSQL, SQLite indexes, filesystems (NTFS, ext4, APFS).
Algorithms to reach for
B-tree search/insert/split
O(log_B n)Disk-friendly ordered storage
B+ leaf-chain range scan
O(log_B n + k)BETWEEN queries without re-descending