Glossary
B-Tree
A balanced tree data structure optimized for storage systems that read and write blocks of sorted data.
Concepts Covered
- B-tree indexes
- Balanced search trees
- Disk locality
- Range scans
- Page splits
- Database lookup performance
Definition
A B-tree is a balanced search tree that stores many keys per node. Database storage engines use B-tree variants because they minimize random I/O and preserve sorted order for efficient range scans.
Why systems engineers care
Indexes are not abstract magic. Their shape influences write amplification, read latency, lock behavior, cache locality, and query planning. Understanding B-trees helps explain why some predicates are cheap and others are expensive.
Useful intuition
Compared with a binary tree, a B-tree is wide and shallow. Each node can hold many keys, so a lookup usually touches only a small number of pages.
| Operation | Typical property |
|---|---|
| Point lookup | Traverses root to leaf |
| Range scan | Walks sorted leaves |
| Insert | May split pages |
| Delete | May rebalance or leave space |
Knowledge links
Use these links to understand what to know first, where this idea appears, and what to study next.
Related Concepts
Core ideas that connect to this topic.