Indexing and Disk Access: Understanding the Economics of I/O
Storage engines operate in a world governed by physical constraints. CPU cycles are abundant and predictable, but disk operations—especially random reads—are expensive, slow, and highly variable. The efficiency of a database engine depends not only on how it stores data, but on how it minimizes the number, cost, and unpredictability of I/O operations.
At the core of this challenge lie three ideas: the vast gap between memory and disk latency, the importance of blocks and pages as fundamental units of access, and the principle of locality, which determines whether reads will be fast or painfully slow. This note explores these concepts and explains why any modern storage engine must be explicitly designed around I/O efficiency.
The Cost of Access: Memory vs Disk
Although CPUs have grown exponentially faster, disk performance has improved at a much slower pace. The difference in latency between memory and disk is stunning—and shapes every major design choice inside a storage engine.
Approximate order-of-magnitude latencies:
L1/L2 cache ~ 1–10 ns
RAM access ~ 100 ns
NVMe random read ~ 50–100 µs
SSD random read ~ 100–200 µs
HDD random read ~ 5–10 ms
Network round-trip (LAN) ~ 0.1 ms
Network round-trip (WAN) ~ 10–100 ms
A millisecond is a million nanoseconds.
A random HDD access is therefore tens of millions of CPU cycles.
This gap explains why engines avoid random disk I/O, why they batch writes, why they use buffers and page caches, and why data structures like B-Trees and LSM Trees exist at all.
Every algorithm inside a storage engine is, consciously or not, an attempt to minimize expensive I/O.
Blocks and Pages: The Units That Matter
Storage devices do not read bytes one by one. They read blocks—typically 4 KB, 8 KB, or 16 KB chunks. Database engines therefore structure their files into pages, aligning with the underlying hardware.
| Page 1 (e.g. 4 KB) |
+---------------------------+
| Page 2 |
+---------------------------+
| Page 3 |
+---------------------------+
When a lookup requires a single key inside a B-Tree, the engine must load:
- the page containing the root node,
- the page(s) of intermediate nodes,
- the page storing the actual key.
Even a simple query may trigger multiple page reads. Engines like PostgreSQL, InnoDB, or WiredTiger rely heavily on buffer pools to keep frequently accessed pages in memory. If the page is present in the buffer pool, the access costs ~100 ns.
If not, the engine pays the full disk latency.
Effective indexing is therefore the art of predicting which pages matter most and shaping data layouts to minimize random reads.
Locality: The Secret Lever of Performance
Locality both spatial and temporal is the single most important concept for I/O-efficient systems.
Spatial locality
If related keys are stored close to each other, a single page read retrieves multiple useful values.
This is why SSTables and B-Trees store data in sorted order.
Temporal locality
Workloads often access the same keys repeatedly.
Engines exploit this by caching hot pages in memory.
When locality is poor—keys scattered across unrelated pages—read amplification increases dramatically, slowing down queries and overwhelming I/O subsystems.
The best engines are designed to make locality the default behavior.
Why Modern Engines Must Be I/O-Efficient
Even with SSDs and NVMe drives, random access remains orders of magnitude slower than memory. As datasets grow and workloads diversify, engines must be explicitly designed around I/O economics.
This affects every major subsystem:
- Indexing must reduce the path length to find data.
- Data layouts must maximize sequential I/O and locality.
- Caching must minimize unnecessary page faults.
- Write paths must exploit sequential writes to avoid fragmentation.
- Compaction or rebalancing must maintain structure without overwhelming the system.
Whether an engine uses B-Trees or LSM Trees, whether it is transactional or analytical, whether it runs on a laptop or a distributed cluster—the economics of I/O shape performance more than any other factor.
Ultimately, designing storage engines is the art of managing imbalance: fast CPUs vs slow disks. I/O is the bottleneck that never truly disappears.
Conclusion
Understanding the economics of I/O is essential for evaluating or designing a database engine. Latency gaps between memory and disk create performance cliffs; blocks and pages enforce alignment constraints; locality determines whether queries behave predictably or degrade catastrophically.
Every major decision inside a storage engine—indexing method, file layout, caching strategy, write path—exists to minimize expensive I/O.
Once this is understood, the architectures of modern engines become clearer: they are elaborate systems built to navigate the physical realities of storage.
Recommended References
- Jim Gray & A. Reuter — Transaction Processing: Concepts and Techniques
- Garcia-Molina et al. — Database Systems: The Complete Book
- PostgreSQL Internals — Buffer Manager and Page Layout
- LevelDB / RocksDB — Block-Based Table Format
- ACM Queue — The Pathologies of Big Data