B-Trees: The Shape of Databases
B-Trees: The Shape of Databases
A visual explanation of the data structure under PostgreSQL, MySQL, and SQLite. We build a
B-tree from first principles — page sizes, fan-out, the leaf chain — and then use EXPLAIN
to watch a query planner walk the tree we just built.
Topics covered:
- Why nodes are sized to disk pages
- Range scans and the leaf chain
- Splits, merges, and index bloat
- Reading your index's health from its statistics
Related articles
Why Databases Use B-Trees (and Not Hash Tables)
Indexes are shaped by the physics of disk and memory. What a B-tree is, why hash indexes can't replace it, and what the shape of the tree says about your database.
Why Your Query Is Slow (And It's Not the Index)
Buffer pool misses, WAL contention, lock waits, and connection pooling — the non-index causes of database slowness.
How SQL Query Optimizers Think
Cost-based optimization, join ordering, and statistics — why your query plan changed overnight and what to do about it.
Depth, delivered weekly
One technical dispatch a week — articles and episode notes before they go public.
One technical dispatch per week. No noise.