IO Cost Summary: Choosing Your Index

Visual: Index Types Head-to-Head

Index IO Costs: Pick Your Fighter Hash Index hash(key) → bucket Data Page IO Costs ✓ Write: 1-2 IOs ✓ Point Query: 1-2 IOs ✗ Range Query: Not supported! 🏆 Wins for: Exact lookups only Example: Session store, user by email O(1) lookups if keys fit in RAM B+Tree Index 500 Root 200 700 900 100 300 600 800 850 950 Leaf pages with actual data 4 levels: Root → Internal → Internal → Leaf Fanout ~1000 → billions of rows in 3-4 IOs IO Costs (F ≈ 1000) ✓ Write: 3-4 IOs ✓ Point Query: 3-4 IOs ✓ Range Query: 3 + scan 🏆 Wins for: Mixed workloads Example: User tables, OLTP Jack of all trades, master of ranges LSM Tree MemTable (RAM) Flush SSTable₁ SSTable₂ ... SSTableₖ IO Latency (K SSTables) ✓ Write: 0 IOs (deferred) 🚀 → Writes to memory, flush later ✗ Point Query: K×2 IOs 🏆 Wins for: Write-heavy workloads Example: Events, logs, time-series 1M writes/sec? No problem!

IO Cost Comparison

Index IO Costs Comparison

Understanding n vs N: The Dictionary Analogy

Webster's Dictionary (Sorted)

n = 171,476 words
From "aardvark" to "zyzzyva"

N = 1,000 pages
Physical book pages

Index size: Just N entries
First word per page + page number

Example: Page 42: "bicycle–bind"
To find "binomial": Check index, go to page 43, scan

RandomWebster's Dictionary (Unsorted)

n = 171,476 words
Randomly scattered across pages

N = 1,000 pages
Same physical book

Index size: All n entries
Every word + its page location

Example: "aardvark" p.847, "apple" p.203
Must track every single word individually

The Key Insight
Sorted data compresses beautifully (N << n). Unsorted data requires tracking everything.

For detailed formulas and specifications, see the IO Reference Guide.

Decision Flowchart

                Need range queries?
                      ↓
            No ←─────────────→ Yes
            ↓                    ↓
    Writes > 10× Reads?     B+Tree ✓
            ↓                (PostgreSQL)
    No ←─────────→ Yes
    ↓               ↓
  Hash ✓         LSM ✓
 (Redis)      (Cassandra)

Database Systems: Who Uses What?

PostgreSQL
B+Tree (balanced workloads)
Redis
Hash (cache, sessions)
Cassandra
LSM (write-heavy)
MongoDB
B+Tree primary + LSM for oplog

Hybrids

Real systems use multiple indexes for different jobs:

B+Tree for primary data • LSM for write-ahead logs • Hash for caches

Pick the right tool for each workload, not one index for everything!