How Database Indexes Minimize Disk I/O to Accelerate Read Performance

It is common knowledge among software engineers that adding an index to a database column makes reads significantly faster. However, understanding why and how this happens at the hardware and storage engine level is essential for designing high-performance data systems.

Database indexing is not magic; it is fundamentally an optimization problem centered on minimizing physical disk I/O. This guide breaks down the physical layout of records on disk, how operating systems read blocks, and the mathematical mechanics of indexing.

---

1. Disks, Blocks, and Serialization

Every database—whether a relational engine storing rows or a document store serializing JSON—must persist data onto non-volatile storage (such as NVMe SSDs or HDDs).

The Fundamental Unit of Disk I/O: The Block

Hardware storage devices and operating system page caches do not read or write individual bytes. Instead, the disk is partitioned into contiguous chunks called blocks (or pages).

• Typical standard operating system and database block sizes are 4 KB, 8 KB, or 16 KB (e.g., MySQL InnoDB default page size is 16 KB).
• Block Invariant: Even if a query requires reading only a single 4-byte integer from disk, the hardware controller and OS must read the entire block containing that byte into memory.

+-------------------------------------------------------------+
|                        Physical Disk                        |
+-----------------+-----------------+-----------------+-------+
| Block 0 (600 B) | Block 1 (600 B) | Block 2 (600 B) |  ...  |
+-----------------+-----------------+-----------------+-------+
        ^                 |
        |                 v
+-------+-----------------------------------------------------+
| Disk Controller reads the entire Block into RAM/Buffer Pool |
+-------------------------------------------------------------+

---

2. Walkthrough: A Simple Database Table Without Indexes

To see the mathematics clearly, consider a hypothetical database setup with a small block size.

Schema and Row Width

Consider a users table with 5 columns:

Column	Data Type	Allocated Size
id	Integer	4 bytes
name	Fixed String	60 bytes
age	Integer	4 bytes
bio	Fixed String	128 bytes
total_blogs	Integer	4 bytes
Total Row Size		200 bytes

Disk Block Capacity

• Assume a configured block size of 600 bytes.
• Number of rows per block:
  $\text{Rows per Block} = \frac{600 \text{ bytes}}{200 \text{ bytes/row}} = 3 \text{ rows/block}$

Storing 100 Rows on Disk

If this table contains 100 records: $\text{Total Blocks} = \left\lceil \frac{100 \text{ rows}}{3 \text{ rows/block}} \right\rceil = 34 \text{ blocks}$

• Blocks 1 through 33 store $3 \times 33 = 99$ rows.
• Block 34 stores the final 100th row (with 400 bytes remaining unused or reserved).

Block 1:  [ Row 1 (id:1) ] [ Row 2 (id:2) ] [ Row 3 (id:3) ]
Block 2:  [ Row 4 (id:4) ] [ Row 5 (id:5) ] [ Row 6 (id:6) ]
...
Block 34: [ Row 100 (id:100) ] [ Empty padding...          ]

Query Execution Without an Index (Full Table Scan)

Consider the following query:

SELECT * FROM users WHERE age = 23;

Because the records are organized sequentially by insertion (or primary key) and not ordered by age:

1. The database storage engine cannot know which block contains users aged 23.
2. It must execute a Full Table Scan: load Block 1 into RAM, parse its 3 rows, check if age == 23, append matches to an output buffer, discard or cache Block 1, and repeat for Block 2 through Block 34.
3. Total I/O Cost: 34 block reads.

If we assume a normalized cost where 1 block read = 1 unit of time (e.g., 1 second/ms), evaluating this query costs 34 units of time.

---

3. Introducing the Index Structure

An index is a secondary data structure that functions like a lightweight reference table mapping indexed attribute values to physical row locations or primary identifiers.

Index Layout on Disk

When we create an index on the age column:

CREATE INDEX idx_users_age ON users(age);

The storage engine builds an auxiliary structure containing pairs of (age, id):

• age (4 bytes)
• id / row pointer (4 bytes)
• Index Entry Size: $4 + 4 = 8\text{ bytes}$

Unlike the main table, this index is strictly sorted by the indexed column (age).

Index Entries (Sorted by age):
[ age: 21, id: 2 ]
[ age: 22, id: 3 ]
[ age: 22, id: 5 ]
[ age: 23, id: 1 ]
[ age: 23, id: 4 ]
[ age: 24, id: 6 ]
...

Index Size Calculations

• Total index entries: 100 entries (one per row).
• Total size of index:
  $100 \times 8 \text{ bytes} = 800 \text{ bytes}$
• Blocks required for index:
  $\left\lceil \frac{800 \text{ bytes}}{600 \text{ bytes/block}} \right\rceil = 2 \text{ blocks}$

Notice the vast difference in storage footprint:

• Main Table: 34 blocks
• Secondary Index: 2 blocks

---

4. Query Execution with an Index

Now, re-evaluate the query using the index:

SELECT * FROM users WHERE age = 23;

Execution proceeds in two distinct phases:

flowchart TD
    A["Query: WHERE age = 23"] --> B["Phase 1: Scan Index Blocks"]
    B --> C["Read Index Block 1 & 2 (2 Block I/Os)"]
    C --> D["Collect Matching IDs: id = 1, id = 4"]
    D --> E["Phase 2: Fetch Base Records"]
    E --> F["Fetch id 1 -> Read Block 1 (1 Block I/O)"]
    E --> G["Fetch id 4 -> Read Block 2 (1 Block I/O)"]
    F --> H["Collate & Return Results"]
    G --> H

Phase 1: Index Traversal

1. The engine reads the index blocks from disk into memory.
2. In the worst-case linear scan of the index, it reads all 2 index blocks.
3. The engine inspects the entries and collects matching row identifiers: id: 1 and id: 4.
4. Disk I/O for Phase 1: 2 block reads.

Phase 2: Record Fetching (Bookmark Lookup)

To return SELECT *, the engine needs the full record (name, bio, total_blogs), which does not exist in the index.

1. Look up id: 1: Located in Block 1 of the main table. The engine issues a disk read for Block 1 (1 block I/O).
2. Look up id: 4: Located in Block 2 of the main table. The engine issues a disk read for Block 2 (1 block I/O).
3. Disk I/O for Phase 2: 2 block reads.

Total Cost and Comparison

Strategy	Index Reads	Data Block Reads	Total Disk I/Os	Relative Performance
Full Table Scan	0	34	34	1x (Baseline)
With Index	2	2	4	~8.5x faster

By leveraging an index, total disk I/O dropped from 34 blocks to 4 blocks—yielding an over 8x performance improvement on a dataset of only 100 rows. At enterprise scales (millions or billions of rows), an unindexed query requires hundreds of thousands of block reads, whereas an indexed query accesses orders of magnitude fewer blocks.

---

5. Further Optimizations Used by Real-World Engines

The example above scanned the entire index sequentially. Real database engines apply several additional layers of optimization to reduce I/O even further:

1. Early Termination in Sorted Data

Because the index is stored in sorted order by age, once the storage engine reads past age = 23 (encountering age = 24), it can immediately halt the scan. If all matches reside in the first block, the second index block never needs to be fetched from disk.

2. Multi-Level Indexing: B-Trees and B+ Trees

Rather than scanning index blocks sequentially, databases structure indexes as B-Trees or B+ Trees:

• Internal nodes contain navigation keys and pointers to child nodes.
• Leaf nodes contain the keys and row pointers (or clustered row data).
• With high branching factors (fan-out of 100 to 1000+), an index across millions of rows can be traversed in only 3 to 4 block reads ($O(\log_B N)$).

3. Covering Indexes

If a query only requests columns that are present inside the index:

SELECT id FROM users WHERE age = 23;

The database performs an Index-Only Scan. Because id is already stored inside the index entry, Phase 2 is skipped completely. Total disk I/O drops from 4 blocks to 2 blocks.

---

6. The Trade-Offs of Indexing

While indexes accelerate reads, they are not free. Every index introduces fundamental systems trade-offs:

1. Write Amplification (DML Overhead): Every INSERT, UPDATE (on indexed columns), or DELETE requires updating both the primary table and every secondary index. This turns a single write into multiple disk I/O operations.
2. Storage Footprint: Indexes consume disk space and memory (buffer pool). Excessive indexing can exhaust RAM, evicting frequently accessed data pages.
3. Maintenance Overhead: Highly fragmented indexes require periodic reorganizations or vacuuming to maintain sequential I/O efficiency.

---

Summary

• Disks operate on blocks, not individual bytes or rows. Query latency is bounded by the number of blocks transferred between disk and memory.
• Without an index, the engine must read every block allocated to a table (Full Table Scan).
• Indexes are compact and sorted, allowing the database to read a fraction of the blocks to identify target rows.
• A query against an unindexed column can easily saturate storage I/O bandwidth, causing latency spikes across the entire system. Ensuring critical access patterns are supported by appropriate indexes is fundamental to database performance.