⚠️ This guide is AI-generated and may contain inaccuracies. Always verify against authoritative sources and real-world documentation.
Home → System Design → Database Indexing

📑 Database Indexing Strategies

Data structures that speed up reads at the cost of slower writes and extra storage. Choosing the right index type and column order is crucial for system performance.

Medium High Frequency

Architecture Diagram — B+ Tree vs Full Table Scan

B+ TREE INDEX LOOKUP: O(log n) 30 60 90 10 20 40 50 70 80 5 | 8 | 10 15 | 18 | 20 35 | 38 | 40 45 | 50 | 55 65 | 68 | 70 FOUND: id=50 ✓ 3 node reads → ~5ms vs FULL TABLE SCAN: O(n) Row 1: id=5 ✕ Row 2: id=8 ✕ Row 3: id=10 ✕ . . . Row N-2: id=45 ✕ Row N-1: id=50 ✓ Row N: id=55 ... scan every row 10M rows → ~30 sec Index Types Comparison B+ Tree Read-optimized, O(log n) Default in PostgreSQL, MySQL LSM Tree Write-optimized, sequential I/O Cassandra, RocksDB, LevelDB Inverted Index Full-text search Elasticsearch, Lucene

How It Works

Without an index, the database must scan every row in the table (full table scan) to find matching records. An index is an auxiliary data structure that lets the database jump directly to the relevant rows — like a book's index lets you find a topic without reading every page.

Key Index Types

B+ Tree (Default in SQL DBs)

Balanced tree with O(log n) lookup. Internal nodes store keys for navigation; leaf nodes store data pointers and are linked for efficient range scans. Handles both equality and range queries. 4 levels covers ~1B rows.

LSM Tree (Write-Optimized)

Writes go to in-memory memtable → flush to sorted SSTables on disk → background compaction. All writes are sequential (fast). Reads may check multiple levels. Used in Cassandra, RocksDB, LevelDB.

Hash Index

O(1) equality lookups using a hash table. Cannot do range queries or sorting. Used in memory stores (Redis, Memcached). Some DBs support it (PostgreSQL hash index) but B-tree is usually better.

Inverted Index

Maps terms → list of documents containing them. Essential for full-text search. "database" → [doc1, doc5, doc99]. Elasticsearch / Lucene. Also used for tag-based lookups.

Composite Index & The ESR Rule

For queries with multiple conditions, the column order in a composite index matters enormously. Follow the ESR rule:

  1. Equality columns first — exact match conditions (WHERE city = 'NYC')
  2. Sort columns next — ORDER BY columns (ORDER BY created_at DESC)
  3. Range columns last — inequality conditions (WHERE age > 25)

Why? A range condition breaks the index ordering for subsequent columns. Putting sort before range lets the database read results in order without an extra sort step.

Key Design Decisions

📖

B-tree vs LSM Tree: B-tree is read-optimized with predictable latency — best for OLTP (web apps, transactions). LSM Tree is write-optimized with sequential writes — best for write-heavy workloads (time series, logs, IoT). The tradeoff: LSM reads are slower (must check multiple levels) and compaction uses CPU/disk.

⚡

Composite index column order: INDEX(city, price, rating) seems logical but breaks the ESR rule if price is a range condition. INDEX(city, rating, price) is better — equality first, then sort, then range. The database can scan the index in order and filter price on the fly.

📊

Over-indexing: Each index slows writes — every INSERT/UPDATE/DELETE must update all indexes. A table with 10 indexes means 10 extra B-tree writes per row change. Index what you query, not everything.

🎯

Selectivity: Indexing a boolean column (2 values) is nearly useless — the index matches 50% of rows, so the DB does a table scan anyway. Index columns with high cardinality (many distinct values). Exceptions: partial indexes on rare values (WHERE status = 'failed').

When to Use

Indexing comes up in almost every system design interview that involves a database. It's often the first optimization to discuss before caching or sharding.

  • "How do you make queries fast?" — Start with proper indexing before adding caching layers
  • "Design a search system" — Inverted index (Elasticsearch/Lucene)
  • "Design a time-series database" — LSM Tree (write-optimized, sequential I/O)
  • "Find nearby locations" — Geospatial index (R-tree, geohash, S2 cells)

Interview signal: Never just say "add an index." Specify the exact columns and their order, then explain WHY using the ESR rule. This separates senior from junior answers.

Real-World Examples

  • Airbnb listing search — Composite B+ tree index on (city, type, available_date, rating, price) following ESR. Narrows 7M listings to ~2K candidates in ~5ms instead of scanning all rows.
  • Elasticsearch (Stack Overflow, GitHub, Wikipedia) — Lucene's inverted index maps words → document IDs. Full-text search returns results in milliseconds across billions of documents.
  • Cassandra (Discord, Apple) — LSM Tree handles 1M+ writes/sec. All writes are sequential — never random I/O. Background compaction merges SSTables.
  • PostGIS (Uber, Lyft) — R-tree / GiST indexes for "find all drivers within 5km." Spatial query in ~10ms across millions of location records.

Back-of-Envelope Numbers

Metric Value
B+ tree depth for 10M rows3–4 levels
B+ tree depth for 1B rows4–5 levels
B+ tree branching factor~200–500 (page size dependent)
Index lookup (B+ tree, in memory)~0.1–1 ms
Full table scan (10M rows)~10–30 seconds
Index size per entry~50–100 bytes
Cassandra write throughput (LSM)1M+ writes/sec
Write overhead per additional index~1 extra B-tree insert per row write