Day 10 — Indexing: B-tree, LSM-tree, Hash, and Beyond

Time budget: ~60 min · Level: The most concrete way to move from "understands databases" to "understands database performance." Poorly-indexed schemas are the #1 cause of production DB fires.

Every experienced backend engineer has seen the story: the app was fast, then it wasn't. EXPLAIN on the slow query shows Seq Scan. Add an index. It's fast again. Simple in narrative, deep in nuance. Today: the nuance.

Why indexes exist — the physical reality

Without an index, finding user WHERE email = 'alice@example.com' requires reading every row in the table: a sequential scan, cost = O(n). At 100M users that's ~5-30 seconds of pure disk I/O.

An index is a secondary data structure that lets you find rows without scanning the base table. Trade-offs: - Speedup on reads: O(log n) for tree-based indexes, O(1) for hash. - Slowdown on writes: every INSERT/UPDATE/DELETE must also update every relevant index. - Storage cost: 5-30% of base-table size per index, often more. - Maintenance cost: VACUUM (Postgres), compaction (LSM), rebuilds after schema changes.

The core mental model: indexes trade write speed and storage for read speed. Adding an index is never free.

B-tree indexes — the default

Used by: Postgres, MySQL/InnoDB, Oracle, SQL Server, DynamoDB (via LSI/GSI), pretty much every OLTP engine.

Structure

A B+tree (the practical variant almost everyone uses): internal nodes hold routing keys; leaves hold the sorted keys and pointers to rows. Fan-out is typically 100-500 keys per node, so a tree of 3-4 levels deep can index billions of rows while requiring only 3-4 disk reads per lookup.

Strengths

Equality lookups — WHERE email = 'X' — O(log n)
Range scans — WHERE created_at > '2026-08-01' — walk the leaves in sorted order
Ordering — ORDER BY created_at uses the index directly, no separate sort needed
Prefix matches — WHERE name LIKE 'ali%' (but NOT LIKE '%ce')
Uniqueness enforcement — UNIQUE constraints are B-tree-backed

Weaknesses

Random writes cause page splits — inserting into the middle of a sorted structure fragments pages, causing bloat and I/O amplification.
Every write pays the log(n) update cost across all B-tree indexes on the table.
Doesn't accelerate queries where the LEFT side of the key is not fixed (LIKE '%foo').

When B-tree is right

Almost always the default for OLTP.
Especially good for read-heavy workloads with occasional writes.

LSM-tree indexes — write-optimized

Used by: Cassandra, RocksDB, LevelDB, ScyllaDB, HBase, BigTable, and modern KV stores.

Structure

Writes go into an in-memory memtable (a sorted map). When it fills up, it's flushed to disk as an immutable SSTable (sorted string table). Multiple SSTables accumulate; a background compaction process merges them into larger sorted files.

Reads potentially check multiple SSTables + the memtable + bloom filters (to avoid reading SSTables that don't contain the key).

Strengths

Massive write throughput — all writes are sequential appends. No random-write penalty. This is why Cassandra outperforms Postgres on write-heavy time-series (see Day 8).
Excellent compression — SSTables are immutable, so compression algorithms work great.
Predictable write latency — no in-place page updates that block on locks.

Weaknesses

Read amplification — a lookup may need to check 5-15 SSTables + bloom filters + memtable. Slower reads than B-tree.
Write amplification — a single logical write can cause data to be rewritten many times over the lifetime of a value due to compactions (up to 30× in extreme cases).
Space amplification — until compaction finishes, multiple versions of the same key exist on disk.
Compaction tuning is a black art — Cassandra's LCS vs STCS vs TWCS have very different trade-offs.

When LSM is right

Write-heavy workloads (time-series, event logs, chat messages).
Predictable access patterns where you can tune compaction strategy.

Hash indexes — the "just find this key" index

Used by: Redis (natively for hash types), Postgres (as USING HASH), Memcached, and internally in many join/aggregation operators.

Structure

A hash table. Key → slot → value.

Strengths

O(1) equality lookup — faster than B-tree for pure WHERE x = 'y' queries with no ordering.

Weaknesses

No range scans — can't do WHERE x BETWEEN a AND b.
No ordering — can't skip a SORT step.
No prefix matches — can't do LIKE 'ali%'.
Historically in Postgres: not WAL-logged (fixed in PG 10+).

When hash is right

In Postgres: rarely — B-tree is almost as fast for equality and does much more.
In Redis: constantly — that's Redis's fundamental data model.
In query planners: hash joins and hash aggregates use in-memory hash tables to accelerate joins.

Bitmap indexes — the analytical index

Used by: Oracle, DuckDB, ClickHouse (indirectly), analytical stores.

Structure

For each distinct value of a column, store a bitmap: bit i is 1 iff row i has that value. Great for low-cardinality columns (gender, country, category).

Strengths

Bitwise combining — WHERE country = 'US' AND status = 'active' becomes bitmap AND — extremely fast.
Tiny for low-cardinality columns.

Weaknesses

Awful for high-cardinality columns — a bitmap per unique email address is huge.
Postgres does not use persistent bitmap indexes but builds them on the fly during query execution.
Expensive to update on OLTP workloads.

When bitmap is right

Data warehouses and analytical queries on low-cardinality columns.

Inverted indexes — search engines

Used by: Elasticsearch, OpenSearch, Solr, Lucene, Postgres GIN.

Structure

A map from term → list of documents containing that term. To search "system design," you fetch the posting lists for "system" and "design" and intersect them.

Strengths

Fast full-text search with ranking, fuzzy matching, phrase queries.
Facets and aggregations over indexed fields.

Weaknesses

Not a system of record — designed to be a derived index.
Expensive to update — each document change touches many terms.
Doesn't support transactions well.

When inverted is right

Any time you need "search" as opposed to "lookup" — free-text, autocomplete, log queries.

Composite (multi-column) indexes

Structure: CREATE INDEX ON orders (customer_id, created_at).

The index is sorted by customer_id first, then by created_at within each customer. This means: - ✅ WHERE customer_id = 42 — uses index - ✅ WHERE customer_id = 42 AND created_at > '2026-01-01' — uses index - ✅ WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 10 — uses index (no sort needed) - ❌ WHERE created_at > '2026-01-01' alone — does NOT use index (leading column not specified) - ❌ WHERE created_at > '2026-01-01' AND customer_id = 42 — DOES use index (planner reorders)

Rule of thumb: put the most-frequently-filtered column first. Equality columns before range columns.

Real-world tip: the index (a, b) also satisfies queries on just a. So you don't need both (a) and (a, b) — the latter subsumes the former.

Covering indexes and index-only scans

An index-only scan happens when all the columns your query needs are in the index — the database doesn't need to visit the base table at all.

-- Without covering index
SELECT email FROM users WHERE user_id = 42;
-- Requires: index lookup + heap fetch to get 'email'

-- With covering index
CREATE INDEX ON users (user_id) INCLUDE (email);
SELECT email FROM users WHERE user_id = 42;
-- Requires: index lookup only — 2× to 10× faster

Postgres uses INCLUDE (col) for non-key covering columns. MySQL/SQL Server automatically use secondary indexes as covering when possible.

Trade-off: covering columns increase index size. Only include what queries genuinely need.

Partial indexes — index only what matters

-- Index only non-deleted rows
CREATE INDEX ON users (email) WHERE deleted_at IS NULL;

-- Index only high-value orders
CREATE INDEX ON orders (customer_id) WHERE amount > 1000;

Massive space and update-cost savings if the predicate excludes most rows. Postgres and SQL Server support partial indexes natively; MySQL requires generated-column workarounds.

Use when: your queries almost always include a specific predicate (WHERE deleted_at IS NULL is the classic).

Expression indexes

CREATE INDEX ON users (LOWER(email));
SELECT * FROM users WHERE LOWER(email) = LOWER($1);  -- Uses the index

Index the result of a function or expression. Common for case-insensitive lookups, computed columns, JSON extractions.

GIN and GiST — Postgres's special-purpose indexes

GIN (Generalized Inverted Index) — inverted-index-like structure for composite values: - JSONB path queries: WHERE data @> '{"status": "active"}' - Full-text search: WHERE tsvector @@ to_tsquery('system design') - Array containment: WHERE tags @> ARRAY['urgent']

GiST (Generalized Search Tree) — extensible tree for non-standard data types: - Geometric queries: PostGIS uses GiST for spatial indexing - Range types - Trigram similarity (pg_trgm) for fuzzy matching

Both are heavier to update than B-tree but essential for their specific use cases.

Reading `EXPLAIN` — the fundamental skill

Every DB engineer should be able to read an execution plan. Postgres example:

EXPLAIN ANALYZE SELECT * FROM orders
  WHERE customer_id = 42 AND created_at > '2026-08-01';

                              QUERY PLAN
-----------------------------------------------------------
Index Scan using orders_customer_created_idx on orders
  (cost=0.42..8.44 rows=1 width=64) (actual time=0.032..0.045 rows=3 loops=1)
  Index Cond: ((customer_id = 42) AND (created_at > '2026-08-01'::date))
Planning Time: 0.115 ms
Execution Time: 0.070 ms

What to look for: - Seq Scan — the table is being read row-by-row. Bad for large tables. Missing index? - Index Scan — using an index. Good. - Index Only Scan — didn't need to touch the heap. Great. - Bitmap Heap Scan + Bitmap Index Scan — Postgres combined multiple indexes. - Hash Join, Merge Join, Nested Loop — join algorithms; huge differences at scale. - Estimated rows vs actual rows — if they diverge by 10×+, statistics are stale (ANALYZE).

Write cost of indexes — the silent killer

Every additional index on a table means every INSERT / UPDATE / DELETE does more work.

INSERT: index insertion for each index (log(n) each).
UPDATE of an indexed column: delete + insert in that index. Non-HOT update in Postgres.
DELETE: index tombstones + eventual vacuum.

A table with 10 indexes will accept writes ~3-5× slower than the same table with 1 index.

Rule: don't add "just in case" indexes. Each one has a running cost.

Index bloat — the operational reality

In MVCC systems (Postgres, MySQL), deleted or updated rows leave dead tuples in indexes. Over time these bloat storage and slow scans.

Symptoms: - Index size grows faster than table size. - Query latency creeps up even though row count is stable. - pg_stat_user_indexes.idx_scan shows the index is being used, but performance is poor.

Fixes: - VACUUM (regular; incremental). - REINDEX CONCURRENTLY — rebuild the index without downtime. - Long-running transactions block vacuum (Day 9 lesson!). Watch pg_stat_activity.

When NOT to index

Very small tables (<1000 rows) — the scan is faster than the index lookup.
Columns with very low cardinality (boolean) — the planner may still prefer a seq scan.
Columns rarely used in WHERE / JOIN / ORDER BY / GROUP BY.
Frequently-updated columns where the write cost exceeds the read savings.

Diagnose unused indexes: SELECT * FROM pg_stat_user_indexes WHERE idx_scan = 0 — any index that's never used is pure overhead. Drop it.

Real-world index disasters (interview anecdotes worth knowing)

The 100-index nightmare. A team added indexes over 5 years without ever removing any. Table had 47 B-tree indexes. INSERT throughput dropped 10×. Fix: drop indexes that show 0 scans over 30 days.
The missing composite. Query WHERE user_id = X AND status = 'active' was slow. Team had two separate single-column indexes. Postgres was BitmapAnd-ing them but the combined selectivity meant it was still slow. Adding a composite (user_id, status) was 20× faster.
Index on volatile column. Indexed last_seen_at (updated on every user page view). Index bloat exploded within days. Fix: don't index high-write columns unless queries actually need it; consider Redis or a materialized view instead.
Wrong column order. Composite index on (country, user_id) when queries were mostly WHERE user_id = X. The index was unusable for those queries. Fix: (user_id, country).
The forgotten LOWER(). Users complained email lookup was slow. Query was WHERE LOWER(email) = LOWER($1). Base index was on email, not LOWER(email) — so it went unused. Fix: expression index.

Interview angles

"How would you speed up a WHERE status = 'pending' AND created_at > NOW() - INTERVAL '7 days' query on a 100M-row orders table?"

Structured answer: 1. Selectivity math first. If 99% of orders are status = 'completed', then status = 'pending' is 1% = 1M rows. Combined with time filter, likely <10k rows. 2. Composite index (status, created_at) — good. 3. Better: partial index CREATE INDEX ... ON orders (created_at) WHERE status = 'pending'. Smaller, faster, and only maintained on the tiny hot subset. 4. Trade-off: partial indexes only help queries that include the predicate. 5. Verify: EXPLAIN ANALYZE before and after; look for Index Only Scan if possible.

"You have 8 indexes on a table and inserts are slow. How do you decide which to drop?"

Check pg_stat_user_indexes.idx_scan — indexes with 0 scans are the first to go.
For low-usage indexes, check if a composite subsumes them.
For redundant single-column indexes covered by a composite, drop the single-column one.
Measure INSERT throughput before and after each drop in a staging environment.

Spaced-repetition callbacks in today's quiz

LSM vs B-tree write throughput (Day 8 Q7 — you nailed it) reappears in a T/F check today.
Post-mortem structure (Days 3/5/6/7/8/9 Q9) — Q9 today extends the pattern to an index regression.
Capacity math (chronic-gap-turned-strength) — Q8 asks for numbers on write amplification when adding indexes to a hot table.

Day 10 — Indexing: B-tree, LSM-tree, Hash, and Beyond

Why indexes exist — the physical reality

B-tree indexes — the default

Structure

Strengths

Weaknesses

When B-tree is right

LSM-tree indexes — write-optimized

Structure

Strengths

Weaknesses

When LSM is right

Hash indexes — the "just find this key" index

Structure

Strengths

Weaknesses

When hash is right

Bitmap indexes — the analytical index

Structure

Strengths

Weaknesses

When bitmap is right

Inverted indexes — search engines

Structure

Strengths

Weaknesses

When inverted is right

Composite (multi-column) indexes

Covering indexes and index-only scans

Partial indexes — index only what matters

Expression indexes

GIN and GiST — Postgres's special-purpose indexes

Reading EXPLAIN — the fundamental skill

Write cost of indexes — the silent killer

Index bloat — the operational reality

When NOT to index

Real-world index disasters (interview anecdotes worth knowing)

Interview angles

Spaced-repetition callbacks in today's quiz

Reading `EXPLAIN` — the fundamental skill