Under the Hood: How Indexes Direct Disk I/O
Without an index, finding a single row in a 50,000,000-record table requires a Sequential Scan (Seq Scan): reading every single disk block into memory (O(N) I/O). An index is an auxiliary data structure stored on disk that maps column values to row locators (in PostgreSQL, physical tuple pointers: ItemPointer / TID: (page_id, offset); InnoDB secondary indexes store the primary key instead), reducing lookup complexity to O(log N).
Index Lookup vs. Sequential Scan
Index Mechanics & Cardinality Rules
1. Multi-Column (Composite) Index Ordering (Left-to-Right Prefix Rule)
If you create an index on (tenant_id, status, created_at), the B-Tree sorts first by tenant_id, then by status, then by created_at. A query filtering by tenant_id AND status uses the index efficiently. A query filtering solely by status cannot use the index for an efficient seek because the leading column is missing. At best the planner scans the whole index, or uses a skip scan (Oracle, MySQL 8.0.13+, PostgreSQL 18+), which pays off only when the leading column has few distinct values.
2. Covering Indexes (Index-Only Scan)
An index lookup typically requires two steps: finding the tuple pointer in the index, then fetching the full row from the heap table. By using an index with included columns:
CREATE INDEX idx_orders_covering ON orders(customer_id) INCLUDE (total_amount, status);The database can satisfy SELECT customer_id, total_amount, status FROM orders WHERE customer_id = 42; entirely from the index page in RAM without touching the table heap at all (an Index-Only Scan).
Worked example: what an index actually saves
Take a users table with 50,000,000 rows of about 200 bytes each. At roughly 35 rows per 8 KB page, that is about 1.4M pages, or about 11 GB.
- Seq scan for one email: read about 1.4M pages. From a cold NVMe drive at around 2 GB/s that is roughly 5-6 seconds. Even fully cached in RAM, it costs around 1 second of CPU to evaluate 50M rows.
- B-tree on email: index entries of about 40 bytes give roughly 200 per page. log base 200 of 50M is about 3.3, so the tree has 4 levels. The root and internal pages are cached, so a lookup is about 1-2 leaf and heap page reads, well under 1 ms.
- Write cost: every INSERT now also inserts into each index. Five secondary indexes means about six B-tree modifications per row plus their WAL. Write-heavy tables should carry only the indexes their queries prove they need.
Choosing an index type
| Index | Good for | Not good for |
|---|---|---|
| B-tree (default) | Equality, ranges, ORDER BY, prefix LIKE 'abc%' | Suffix or contains search, very low selectivity |
| Hash | Pure equality with slightly smaller size | Ranges, sorting |
| GIN | JSONB containment, arrays, full-text | Write-heavy tables (slow updates) |
| BRIN | Huge append-only tables ordered by time | Randomly ordered data |
| Partial | Hot subsets such as WHERE status = 'pending' | Queries that do not repeat the predicate |
Composite index rule of thumb
For WHERE tenant_id = ? AND status = ? AND created_at > ? ORDER BY created_at, index (tenant_id, status, created_at). Equality columns go first and the range and sort column last, so the database seeks to one contiguous slice and reads it in order with no sort step.
Failure modes
- Index-only scan that is not: in PostgreSQL, heap fetches still happen for pages not marked all-visible in the visibility map. Vacuum is what keeps index-only scans cheap.
- Unused indexes: check
pg_stat_user_indexes.idx_scan = 0and drop them. They slow every write and waste cache. - Clustered vs heap: in MySQL InnoDB, secondary indexes store the primary key, not a physical pointer. A wide or random primary key (UUIDv4) bloats every secondary index.