Home / System Design / Concepts / Database Indexing CONCEPT SHEET · Concepts
Database Indexing
One-liner: An index is a secondary structure that trades write cost and space for O(log N) lookups instead of full scans.
Article Concepts © Arthur Bernier Jr 524 words 1 code block
Say this#
SAY THIS
B-tree / B+tree — balanced, sorted, page-oriented; supports equality, range, ORDER BY, prefix. Default in Postgres/MySQL.Hash index — equality only, O(1); Postgres USING hash, in-memory stores.LSM-tree — log-structured merge tree: memtable → sorted SSTables → compaction; write-optimized (Cassandra, RocksDB, LevelDB, HBase).Clustered index — table rows stored in index order (InnoDB primary key); Postgres heap tables are not clustered.Composite (multi-column) index — (a, b, c); usable only via leftmost prefix : a, a,b, a,b,c.Covering index / index-only scan — all needed columns are in the index; no heap fetch. INCLUDE (col).Selectivity / cardinality — fraction of rows matched; low-selectivity indexes get ignored by the planner.Write amplification — each index adds a write per INSERT/UPDATE/DELETE.Read amplification — LSM may check several SSTables; mitigated by Bloom filters.Partial index — index with a WHERE clause (WHERE deleted_at IS NULL).Inverted index — term → document list; full-text search (Elasticsearch, Postgres GIN).EXPLAIN / EXPLAIN ANALYZE — show the plan: Seq Scan vs Index Scan vs Index Only Scan vs Bitmap Heap Scan.
How it works#
B-tree lookup: root → internal pages → leaf; leaf holds key + row pointer (TID). Range scan walks leaf siblings.
TEXT Copy
B-tree: [ 50 | 100 ] fan-out ~hundreds; 3-4 levels covers billions of rows / | \ [1..49] [50..99] [100..] -> leaf -> heap row LSM: write -> WAL + memtable (sorted in RAM) --flush--> SSTable L0 --compact--> L1 ... Ln read -> memtable -> Bloom filters -> newest SSTable first Composite index (user_id, created_at): WHERE user_id = ? ORDER BY created_at DESC LIMIT 20 is a single index range walk. WHERE created_at > ? alone cannot use it.
Trade-offs#
Choice Pro Con B-tree Range + equality + ordering, mature Random-write heavy; page splits; write amplification Hash Fastest equality No range, no ordering LSM-tree Sequential writes, high ingest, good compression Read amplification, compaction CPU/IO bursts, space amplification More indexes Faster reads Slower writes, more storage, planner confusion Covering index Avoids heap lookups Wider index, more write cost Clustered PK (InnoDB) PK range scans are sequential IO Random UUID PKs fragment pages; use sequential IDs/UUIDv7
Numbers#
B-tree height 3-4 for ~10^9 rows with 8 KB pages; lookup is 3-4 page reads, mostly cached.
Postgres default page 8 KB; MySQL InnoDB 16 KB.
Rule of thumb: a full table scan beats an index when selecting more than ~5-10% of rows.
Each additional index commonly costs 10-30% write throughput on insert-heavy tables (order of magnitude).
In the interview#
SAY THIS
Bring it up in the data model: "Index on (user_id, created_at) to serve the per-user timeline in one range scan."
Say: "I'd check with EXPLAIN ANALYZE that it's an Index Scan, and add INCLUDE columns if we want an index-only scan."
Follow-up: "Why not index everything?" → "Write amplification and storage; each index is another B-tree to update on every write."
Follow-up: "When would you pick an LSM store?" → "Write-heavy, append-mostly workloads like events, time-series, or logs: Cassandra, RocksDB, ClickHouse."
Creator
Written by Arthur Bernier Jr (Big Poppa Code). Arthur Bernier Jr — Big Poppa Code — is a software engineer, educator and entrepreneur: a former CTO at VC-backed startups and engineering lead at a billion-dollar company, mentor to 800+ engineers, now Senior Director of AI, Computer Programming and Cloud Computing at Per Scholas, and the host of the Deeper Than Code podcast. Everything on this page is his original teaching material.
bigpoppacode.io
License © Arthur Bernier Jr all rights reserved