Back to System design

Database Indexing: B-Tree vs LSM, Composite, Covering

medium
Scale: B-tree O(log N) lookup; LSM amortized O(log N) reads, O(1) writes Storage: Index 10-30% of table; LSM may temporarily double during compaction Postgres, MongoDB, Stripe
FundamentalsDatabasesIndexing

An index is a separate data structure that lets the database find rows matching a query without scanning the whole table. The trade-off is fundamental: indexes accelerate reads but cost on every write and consume storage.

ScaleB-tree O(log N) lookup; LSM amortized O(log N) reads, O(1) writes
StorageIndex 10-30% of table; LSM may temporarily double during compaction

Key Concepts

1
1. Two storage families. B-tree (Postgres, MySQL InnoDB, SQL Server): balanced search tree; supports equality, range, ORDER BY, prefix LIKE. Default for OLTP. LSM-tree (Cassandra, RocksDB, LevelDB): writes to memtable → flush to immutable SSTables → background compaction merges. Massive write throughput; reads do amplification across SSTables.
1. Two storage families.
2
2. Composite index order is critical. For WHERE a=? AND b>? ORDER BY c, the right index is (a, b, c) — equality first, then range, then sort. The leftmost prefix rule: an index on (a, b, c) is also usable for queries on a or (a, b). Wrong column order = unused index. Always validate with EXPLAIN ANALYZE.
2. Composite index order is critical.WHERE a=? AND b>? ORDER BY c(a, b, c)a(a, b)
3
3. Specialized index types. Covering index: includes all SELECT columns in the index leaf — index-only scan, no heap fetch. Partial index: adds a WHERE clause (e.g., WHERE deleted = false) — smaller, faster for the common case. GIN: full-text, JSONB containment, array membership. GiST: spatial, geometric, fuzzy. BRIN: tiny index for naturally ordered huge tables (logs). Bloom filters (in LSM): skip SSTables for absent keys.
3. Specialized index types.WHERE deleted = false
4
4. The cost of indexes. Every index is updated on every write — typical 10-30% extra storage and 5-20% write throughput cost. Unused indexes silently burn write capacity for nothing. Audit and drop them: pg_stat_user_indexes for Postgres; sys.dm_db_index_usage_stats for SQL Server. Stale stats → bad plans; run ANALYZE after large data changes.
4. The cost of indexes.pg_stat_user_indexessys.dm_db_index_usage_stats
5
5. The tuning loop. (a) Enable slow-query logging (pg_stat_statements). (b) Identify top offenders by total time. (c) EXPLAIN ANALYZE each — look for sequential scans, hash joins on large tables, sort spills. (d) Design indexes for those specific queries. (e) Re-measure. Common pitfall: functions in WHERE clauses break index usage (WHERE lower(email)=? needs a functional index).
5. The tuning loop.pg_stat_statementsEXPLAIN ANALYZEWHERE lower(email)=?

Related Problems

CAP Theorem and PACELCeasyLoad Balancing: L4 vs L7, Algorithms, Health CheckseasyCaching Strategies: Cache-aside, Write-through, Write-backeasySQL vs NoSQL: When to Pick WhicheasySharding Strategies: Range, Hash, Directory, Geomedium

Approach

  1. Enable slow-query logging or query stats (Postgres pg_stat_statements).
  2. Identify the top 5-10 slow queries by total time.
  3. EXPLAIN ANALYZE each. Look for sequential scans, hash joins on large tables, sort spills.
  4. Design indexes specifically for those queries. Composite columns ordered: equality → range → sort.
  5. Consider covering indexes (INCLUDE clause in Postgres) to avoid heap fetch.
  6. Drop unused indexes (pg_stat_user_indexes idx_scan = 0 for weeks).
  7. Schedule VACUUM/ANALYZE (Postgres) or OPTIMIZE TABLE (MySQL) regularly.
  8. For LSM, tune compaction strategy (size-tiered vs leveled) for read/write ratio.

Index types

B-tree: equality, range, ORDER BY, LIKE 'prefix%'. Default for OLTP.

Hash: equality only, O(1). Postgres has them but rarely better than B-tree.

GIN (inverted): full-text, JSONB, arrays.

GiST: spatial, geometric, trigrams (fuzzy match).

BRIN: tiny index for naturally ordered huge tables (logs).

Bitmap: low-cardinality columns; common in OLAP not OLTP.

LSM-tree (storage engine, not table-level index): write-optimized; supports range scans within an SSTable level.

Components

  • Query planner / cost estimator (uses table statistics).
  • ANALYZE / table statistics refresh.
  • WAL / binlog for durable updates.
  • Compaction (LSM) — leveled, size-tiered, universal.
  • Bloom filters (LSM) — skip SSTables for absent keys.
  • Index-only scans / covering indexes.
  • Online index creation (CREATE INDEX CONCURRENTLY in Postgres).

Trade-offs

More indexes: faster reads, slower writes, more disk.

B-tree: balanced; writes do some random I/O at scale.

LSM: sequential writes (great throughput), read amplification (multiple SSTables).

Composite index: powerful, but wrong column order = unused.

Covering index: avoids heap fetch but larger index.

Partial index: smaller and faster for the matching subset; unusable for queries that don't match the WHERE.

Common pitfalls

  • Indexing every column 'just in case'. Each costs writes.
  • Wrong column order in composite index. EXPLAIN reveals it.
  • Indexing low-cardinality columns. Planner ignores them.
  • Forgetting to ANALYZE after large data changes; stale statistics → bad plans.
  • Functions in WHERE clauses break index usage (WHERE lower(email) = ? — need a functional index).
  • IS NULL queries often not covered by standard B-tree indexes.