IO Cost & Trade-offs: Choosing Your Index
Concept. Each index has costs and benefits. Map your workload against different index structures. Decide whether the table is physically sorted on the key. Derive the IO cost from the structure and the layout.
Intuition. Hash indexes optimize equality lookups. B+Trees support point lookups and range scans. LSM (built on SSTables) sustains high write throughput. Inverted indexes support full-text search. A clustered layout changes the constant factors for reads and the index size.
This page is structured around three questions. Each maps to one section.
-
How do I choose an index? → Pick the right structure for your workload.
-
What if the data is sorted? → A sorted dictionary needs a much smaller index than an unsorted one. That's clustering.
-
What is the cost? → IO chart per access pattern, plus what
O(log N)actually means in practice.
Q1. How do I choose an index?
Three structures cover almost every relational workload. Match the column to the kind of query that's hot:
| Hash index | B+Tree | LSM (on SSTables) | |
|---|---|---|---|
| Lookup | O(1) equality, hash to bucket, read the entry | O(log N) any key, descend root → internal → leaf | Walks tiers (MemTable → L0 → L1+), Bloom-skipped |
Range / ORDER BY |
None, hash scrambles neighbours | Native, leaves are linked left-to-right | Native, merged view across tiers |
| Write cost | Update one bucket (split on overflow) | Random write + occasional rebalance | Append to RAM, sequential flush, background compaction |
| Typical use | Primary keys, caches | General-purpose OLTP | Counters, events, write-heavy analytics |
| Production examples | Redis, Memcached | PostgreSQL, MySQL InnoDB | Bigtable, Cassandra, DynamoDB, RocksDB |
For full-text search across many documents, the right structure is an inverted index (term dictionary plus postings lists). Used heavily in the Spotify case studies later in the module.
Q2. What if the data is sorted?
Sorted data lets the index scale with N (pages), not n (rows). The intuition is a dictionary.
Two dictionaries with the same content (n = 171,476 words spread over N = 1,000 pages). The only difference: one is sorted, the other isn't.
| Webster's: sorted dictionary | RandomWebster's: unsorted dictionary | |
|---|---|---|
| Word order | Alphabetical, from "aardvark" to "zyzzyva" | Scattered randomly across pages |
| Index density | Sparse: one entry per page (first word + page number) | Dense: one entry per word |
| Lookup | Find "coffee" with one index lookup ("clutch-coffin to page 217"), jump there, scan a few rows | "coffee" is on page 847, "coffeehouse" on page 12: every word needs its own pointer |
| Index size | ~1,000 entries (N pages) | ~171,476 entries (n words, 170x larger) |
The same idea applied to a database table is clustering.
Figure: Clustering puts one user’s listens togetherFind all listens for user 7. The same eight rows occupy four pages in either layout, with two rows per page. Arrival order scatters user 7 across four pages. Clustering by user_id and listen_time groups the four matching rows into two pages. Counts exclude index lookup cost. Thin green markers identify matching rows.
Figure 1. Find all listens for user_id = 7. Both layouts contain the same eight rows, two per page; the figure shows user_id and song_id. In arrival order, user 7’s four listens occupy four pages. Clustering by (user_id, listen_time) groups them onto two neighboring pages, in time order. That is four versus two data-page reads, excluding index lookup cost. The index finds the rows; clustering puts them on fewer pages.
| Clustered index | Unclustered index | |
|---|---|---|
| Physical layout | Table data is physically sorted by the index key | Table data is in insert order, not sorted by the index key |
| Index density | Sparse (one entry per page) | Dense (one entry per row) |
| Queries returning many rows | Nearby matches share pages: find the first page, walk forward | Matches may be scattered: up to one data-page read per matching row |
| Bottom line | Best for the access pattern you scan most | All non-primary indexes are usually unclustered |
A table can only be clustered on one set of columns at a time, because the physical sort order can only go one way. Every other index on the same table is unclustered. Production systems sometimes keep multiple copies of the same table, each clustered differently, when several access patterns need to be fast.
Q3. What is the cost?
Pull the structural choice (Q1) and the clustered/unclustered choice (Q2) together, and you get the IO cost for any access pattern.
| Access pattern | Hash index | B+Tree | LSM |
|---|---|---|---|
| Point lookup: one matching row | Find its bucket, then the row | Descend the tree, then fetch the row | Check memory and candidate SSTables |
| Range scan | No ordered range access | Linked leaves; clustered rows reduce scattered reads | Merge matching ranges across files |
| Inserts and updates | Update a bucket; split if needed | Update a page; split or rebalance if needed | Buffer in RAM, then flush and compact |
Clustering matters most when a query returns many rows: nearby matches share data pages. A single-row lookup still needs its index path and the matching data page.
What "O(log N)" actually means
The Big-O hides a lot. A B+Tree's O(log N) is ⌈log_fanout(N)⌉, and fanout is large, so the tree remains shallow over a wide range of table sizes: often 3 to 4 index-page reads per point lookup, plus the data page when stored separately. (See the fanout table on the B+Tree page for the exact arithmetic across page sizes from 64 KB to 64 MB.)
| Fanout | Table size | Tree levels | Reads per point lookup |
|---|---|---|---|
| 1,000 | 1 billion rows | 3 levels | 3 |
| 65,000 | 1 trillion rows | 3 levels | 3 |
Hash O(1) |
any | 1 bucket | 1 |
When you compare hash (O(1)) against B+Tree (O(log N)), the real difference is small (1 vs 3 page reads). The useful difference is whether the index supports range scans. The Big-O is asymptotic shorthand, not a recipe for choice.
What drives LSM cost: SSTable counts, not Big-O
LSM cost depends on the files that may contain the key, their sizes, caching, and compaction. Count how many SSTables a read must inspect, rather than relying on table size alone.
-
Reads: walk the MemTable, then every Level-0 SSTable that might contain the key, then the Level-1+ file. The cost is the count of SSTables touched (Bloom-filter-skipped where possible). For a counter, that means summing fragments from each tier. For a latest-wins value, it means returning the first match.
-
Writes: the MemTable buffers writes in RAM. When it fills, sorting it produces one SSTable. That sort is the same in-memory operation as the big sort algorithm. When compaction merges several Level-0 files into one Level-1+ file, that's a sort-merge across already-sorted runs. No new algorithm. Same primitives, applied to LSM's tier structure.
So when you reason about LSM cost, count SSTables and remember which operation is doing the work: in-memory sort for a flush, sort-merge for a compaction.
See also. The big sort page walks through how a runs-and-merge sort actually streams through memory and disk, and the sort-merge join page works the merge step end-to-end. The LSM compaction loop is the same algorithm, with SSTables as the input runs.