IO Cost & Trade-offs: Choosing Your Index

Concept. Choose an index by answering three questions. Map the workload to an index structure. 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 the 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.

The same range query, every rating of 4 or 5, over the same four matching rows. On a clustered table sorted by rating the matches sit in two contiguous green pages (two sequential reads, a sparse index); on an unclustered table in insert order the same matches scatter across all four pages (four random reads, a dense index). Green marks an in-range row and a page that gets read.

Figure 1. A range query for rating 4 or 5 matches four rows. A clustered table stores rows sorted by rating, so the matches occupy two contiguous pages and require two sequential reads. The index stores one entry per page (sparse). An unclustered table stores rows in insert order, so the four matches occupy four pages and require one random read per matching row. The index stores one entry per row (dense). Green marks an in-range row and a page that gets read.

	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)
Range scans	Sequential reads: find the first page, walk forward	One IO per matching row, jumping around the table
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.

Chart comparing IO cost across index types for equality lookups, range scans, inserts and updates: hash and B+Tree are both fast on equality, clustered B+Tree wins range scans, LSM wins inserts and updates.

Figure 2. Equality lookups on hash and B+Tree take 1 to 4 IOs, and clustering does not change the lookup because the lookup returns one row. Range scans depend on clustering. A clustered B+Tree reads contiguous pages, an unclustered B+Tree performs one IO per matching row, and hash does not support range scans. Inserts and updates favor LSM, which appends to RAM. A B+Tree pays random-write cost plus occasional rebalancing. A hash index updates a bucket and may split the bucket.

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 asymptotic claim collapses to a constant in practice: roughly 3 to 4 page reads per point lookup, regardless of table size. (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 costs don't fit cleanly on the asymptotic chart, because they aren't a function of the table size. They're a function of how many SSTables are sitting at each level at the moment you read or write.

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.