Database Indexing

Write path#

flowchart LR
    W["<img src="/icons/mdi-database-plus.svg" alt="mdi:database-plus" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> INSERT / UPDATE<br/><span class='sub'>incoming write</span>"]:::step
    WAL["<img src="/icons/mdi-file-document-edit-outline.svg" alt="mdi:file-document-edit-outline" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> WAL<br/><span class='sub'>sequential append</span>"]:::cache
    MEM["<img src="/icons/mdi-memory.svg" alt="mdi:memory" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> Memtable<br/><span class='sub'>in-RAM sorted tree</span>"]:::cache
    FLUSH["<img src="/icons/mdi-download.svg" alt="mdi:download" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> Flush<br/><span class='sub'>~MB threshold</span>"]:::step
    L0["<img src="/icons/mdi-database.svg" alt="mdi:database" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> SSTable L0<br/><span class='sub'>immutable</span>"]:::storage
    L1["<img src="/icons/mdi-database.svg" alt="mdi:database" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> SSTable L1<br/><span class='sub'>compacted, merged</span>"]:::storage
    L2["<img src="/icons/mdi-database.svg" alt="mdi:database" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> SSTable L2+<br/><span class='sub'>older, larger</span>"]:::storage

    W ==> WAL
    W ==> MEM
    MEM ==>|"when full"| FLUSH
    FLUSH --> L0
    L0 -.->|"background compaction"| L1
    L1 -.->|"background compaction"| L2

classDef cache stroke:#10b981,stroke-width:1.75px;
classDef storage stroke:#f59e0b,stroke-width:1.75px;
classDef step stroke:#3b6fd6,stroke-width:1.75px;

• Memtable — the in-RAM sorted buffer (typically a skiplist or red-black tree). Writes land here instantly.
• WAL (Write-Ahead Log) — a single append-only file for crash recovery. If the process dies, the WAL replays into a fresh memtable.
• SSTables — once the memtable is big enough (a few MB), it’s flushed to an immutable sorted file on disk. One sequential write of many MB instead of many random 8 KB writes.
• Compaction — a background job merges older SSTables, dropping tombstones for deleted keys and duplicate keys.

Read path — and why reads are harder#

A single point lookup may have to check many SSTables because any of them could hold the most recent value for a key.

flowchart TB
    Q["<img src="/icons/mdi-database-search.svg" alt="mdi:database-search" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> GET key = X<br/><span class='sub'>point lookup</span>"]:::ask
    M["<img src="/icons/mdi-memory.svg" alt="mdi:memory" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> Memtable<br/><span class='sub'>RAM</span>"]:::cache
    BF1{{"Bloom filter<br/><span class='sub'>L0 SSTable</span>"}}:::ask
    L0F["<img src="/icons/mdi-database.svg" alt="mdi:database" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> L0 SSTable<br/><span class='sub'>disk read</span>"]:::storage
    BF2{{"Bloom filter<br/><span class='sub'>L1 SSTable</span>"}}:::ask
    L1F["<img src="/icons/mdi-database.svg" alt="mdi:database" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> L1 SSTable<br/><span class='sub'>disk read</span>"]:::storage
    DONE["<img src="/icons/mdi-check-circle-outline.svg" alt="mdi:check-circle-outline" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> found<br/><span class='sub'>return value</span>"]:::ok
    MISS["<img src="/icons/mdi-close-circle-outline.svg" alt="mdi:close-circle-outline" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> not in table<br/><span class='sub'>skip</span>"]:::bad

    Q --> M
    M ==>|"hit"| DONE
    M -->|"miss"| BF1
    BF1 -->|"definitely not"| MISS
    BF1 -->|"maybe"| L0F
    L0F ==>|"hit"| DONE
    L0F -->|"miss"| BF2
    BF2 -->|"definitely not"| MISS
    BF2 -->|"maybe"| L1F
    L1F ==>|"hit"| DONE

classDef cache stroke:#10b981,stroke-width:1.75px;
classDef storage stroke:#f59e0b,stroke-width:1.75px;
classDef ok stroke:#16a34a,stroke-width:1.75px;
classDef bad stroke:#dc2626,stroke-width:1.75px;
classDef ask stroke:#6366f1,stroke-width:1.75px;

Bloom filters are the secret. Each SSTable ships with a tiny probabilistic filter that can say “this key is definitely NOT here” in a single hash operation. A bloom filter miss skips the SSTable entirely; only a positive (or “maybe”) answer triggers an actual disk read. In practice this keeps point-lookup reads at 1–2 disk fetches even with hundreds of SSTables.

Real-world LSM users:

• Cassandra — Netflix’s viewing-events storage.
• RocksDB — the storage engine under Kafka Streams, Flink state, many Facebook services.
• DynamoDB — publicly described as LSM-style internals.
• ScyllaDB — a Cassandra-compatible rewrite in C++.

When to pick LSM in an interview: write-heavy workloads where reads are rare or latency-tolerant — metrics, logs, event streams, IoT telemetry. The moment a read-heavy user-facing query enters the picture, B-trees usually win on tail latency.

Geohash — turn 2D into a sortable string#

Recursively subdivide the globe into base-32 cells and encode each level as one character:

• 9q — Western US
• 9q8 — Bay Area
• 9q8y — San Francisco
• 9q8yy — Mission District
• 9q8yyk — one city block

flowchart LR
    GPS["<img src="/icons/mdi-map-marker.svg" alt="mdi:map-marker" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> GPS point<br/><span class='sub'>37.77, -122.41</span>"]:::step
    ENC["<img src="/icons/mdi-cog.svg" alt="mdi:cog" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> Geohash encoder<br/><span class='sub'>recursive subdivide</span>"]:::step
    STR["<img src="/icons/mdi-format-text.svg" alt="mdi:format-text" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> String<br/><span class='sub'>9q8yyk</span>"]:::step
    BT["<img src="/icons/mdi-file-tree.svg" alt="mdi:file-tree" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> B-tree index<br/><span class='sub'>prefix range scan</span>"]:::database
    NEAR["<img src="/icons/mdi-check-circle-outline.svg" alt="mdi:check-circle-outline" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> Nearby points<br/><span class='sub'>prefix 9q8yy*</span>"]:::ok

    GPS --> ENC --> STR --> BT ==> NEAR

classDef database stroke:#f97316,stroke-width:1.75px;
classDef ok stroke:#16a34a,stroke-width:1.75px;
classDef step stroke:#3b6fd6,stroke-width:1.75px;

The elegance: close-in-reality locations share long common prefixes. A B-tree range scan on geohash LIKE '9q8yy%' returns all points in that cell. You get proximity search using nothing but a string column and a B-tree.

Redis’s geospatial commands (GEOADD, GEOSEARCH) use geohash internally. This is also the easiest to explain in an interview.

Quadtree — recursive 2D partitioning#

Divide space into 4 quadrants; when a quadrant has more than a threshold of points, split it again. Adaptive — dense areas get deep subdivision, empty ocean stays shallow. Historically important; most modern databases don’t ship quadtrees but the idea shows up in map-tile systems (Google Maps tiles are a quadtree).

R-tree — production standard#

Groups nearby objects into overlapping bounding rectangles that adapt to the data shape. Handles points and polygons in the same index (useful for “find delivery zones that cover this address”). PostGIS, MySQL’s SPATIAL INDEX, and SQLite R*Tree all use R-trees.

How to answer this in an interview: “A B-tree can’t serve proximity queries because lat/lon are independent dimensions. I’d reach for geohash if I can stay on Postgres without extensions — it turns 2D into string prefix matching so a plain B-tree works. For production GIS workloads I’d use PostGIS’s R-tree, which handles both points and polygons and is what Uber, Yelp, and most delivery apps actually run on.” That one sentence covers the whole topic.

Composite index — one B-tree, multiple columns#

A classic feed query:

1
SELECT * FROM posts
2
WHERE user_id = 123
3
  AND created_at > '2026-01-01'
4
ORDER BY created_at DESC;

Two single-column indexes force the planner to fetch two big sets and intersect them, then sort. A single composite index gives both filtering and sorting in one B-tree walk:

1
CREATE INDEX idx_user_time ON posts(user_id, created_at);

The index’s keys are tuples — sorted by user_id first, then created_at within each user:

flowchart TD
    ROOT["<img src="/icons/mdi-file-tree.svg" alt="mdi:file-tree" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> Composite B-tree<br/><span class='sub'>(user_id, created_at)</span>"]:::database
    K1["<img src="/icons/mdi-key-outline.svg" alt="mdi:key-outline" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> (1, 2026-01-01)"]:::step
    K2["<img src="/icons/mdi-key-outline.svg" alt="mdi:key-outline" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> (1, 2026-01-02)"]:::step
    K3["<img src="/icons/mdi-key-outline.svg" alt="mdi:key-outline" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> (1, 2026-01-03)"]:::step
    K4["<img src="/icons/mdi-key-outline.svg" alt="mdi:key-outline" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> (2, 2026-01-01)"]:::step
    K5["<img src="/icons/mdi-key-outline.svg" alt="mdi:key-outline" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> (3, 2026-01-01)"]:::step

    ROOT --> K1
    ROOT --> K2
    ROOT --> K3
    ROOT --> K4
    ROOT --> K5

    K3 ==>|"user_id=1 AND created_at > '2026-01-01'<br/>range-scan THIS subtree only"| HIT["<img src="/icons/mdi-check-circle-outline.svg" alt="mdi:check-circle-outline" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> match"]:::highlight

    classDef highlight fill:#f3ebff,stroke:#7c3aed,stroke-width:1.5px,color:#4c1d95;

classDef database stroke:#f97316,stroke-width:1.75px;
classDef step stroke:#3b6fd6,stroke-width:1.75px;

Column order rules of thumb:

• Equality first, range second, sort last. (user_id, created_at) works; (created_at, user_id) doesn’t help the common query pattern.
• The index is only useful for prefixes of the column list. (a, b, c) accelerates WHERE a = ?, WHERE a = ? AND b = ?, WHERE a = ? AND b = ? AND c = ?. It does not accelerate WHERE b = ?.
• “Most selective column first” is a good default, but query patterns trump selectivity — if you always sort by created_at, it must be in the index even if it’s not selective.

Covering index — answer without touching the table#

Normal index lookup = (1) find the row in the index, (2) fetch the actual row from the heap for any column the index doesn’t carry. For read-heavy queries returning just a few columns, those heap fetches are wasted work.

A covering index includes the extra columns directly:

1
-- Normal: index on (user_id, created_at); "likes" requires a heap read
2
CREATE INDEX idx_user_time ON posts(user_id, created_at);
3

4
-- Covering: "likes" travels with the index; query is answered purely from the index
5
CREATE INDEX idx_user_time_likes ON posts(user_id, created_at) INCLUDE (likes);

Trade-off: the index is bigger (more storage, slower writes) but the query is an order of magnitude faster because it skips heap page reads. Reach for this when one hot query dominates your table and returns few columns — activity feeds, leaderboards, unread-count endpoints. Don’t sprinkle INCLUDE everywhere; modern query planners are good with plain indexes and the maintenance cost is real.

Write-side optimizations — shrink what you maintain#

Every index costs write throughput. The goal here is to maintain less index per write without losing read speed.

Partial indexes — index only the rows a hot query actually touches. Classic case: an orders table where 99% of rows are status = 'closed' but every query filters on status = 'open':

1
-- Instead of a full index on status (bloated, rarely useful):
2
CREATE INDEX idx_orders_status ON orders(status);
3

4
-- Index only the 1% that matters — drop size + write cost by ~100x:
5
CREATE INDEX idx_open_orders ON orders(user_id, created_at)
6
  WHERE status = 'open';

Inserts that land on closed orders skip this index entirely. The index stays tiny (1% of rows) and SELECT … WHERE status = 'open' AND user_id = ? uses it.

Fill factor + HOT updates (Postgres) — Postgres’s Heap-Only Tuple optimization lets an UPDATE re-write the row in the same page without touching any index, as long as no indexed column changes and the page has free space. Dropping fill factor leaves that free space:

1
ALTER TABLE posts SET (fillfactor = 85);   -- 15% free per page

Biggest wins on hot-updated tables (user sessions, counters) where the updated columns are NOT indexed.

CREATE INDEX CONCURRENTLY — a regular CREATE INDEX takes an exclusive write lock. On a production table with 100 M rows, that’s minutes of downtime. The concurrent variant builds in the background:

1
CREATE INDEX CONCURRENTLY idx_posts_user_time ON posts(user_id, created_at);

Slower overall, but no write lock. Non-negotiable for production schema changes.

Drop + recreate for bulk loads — if you’re importing 100 M rows from a dump, every existing index pays the write tax row-by-row. Drop the indexes, COPY the data, recreate the indexes once at the end. Typically 3–10× faster.

UNLOGGED / async commit for non-critical tables — staging tables, session stores, and rate-limit counters don’t need WAL durability. UNLOGGED tables skip the WAL and synchronous_commit = off lets the commit return before the WAL fsync. Accept the “lose the last second on crash” trade-off.

Read-side optimizations — answer more queries from less I/O#

Functional (expression) indexes — if you query a computed value, index the computation, not the raw column:

1
-- WHERE lower(email) = ? — a regular index on email is NOT used
2
CREATE INDEX idx_users_email_lower ON users(lower(email));
3

4
-- WHERE (data->>'status') = 'active' — JSONB path index
5
CREATE INDEX idx_orders_status_jsonb ON orders((data->>'status'));

A common interview gotcha: candidates add an index on created_at but the query is WHERE DATE(created_at) = CURRENT_DATE. The regular index is useless; you need INDEX ON (DATE(created_at)).

Bitmap index scans (Postgres) — when a query filters on several columns that each have their own single-column index, Postgres can scan each index, build a bitmap of matching pages, AND/OR the bitmaps, then fetch only pages in the result set. Lets you avoid a composite index when queries mix columns unpredictably:

1
-- Rather than one composite for every combination, keep single-column indexes:
2
CREATE INDEX idx_status   ON orders(status);
3
CREATE INDEX idx_customer ON orders(customer_id);
4
-- Postgres bitmap-AND-merges these automatically for
5
--   WHERE status = 'open' AND customer_id = 42

Don’t rely on this for the hottest query — a targeted composite index is still faster — but it’s the right tool when query shapes are ad-hoc and many.

Index-only scans + visibility map — a covering index is “only as covering as the visibility map allows.” Postgres has to check whether a row is visible to the current transaction; for ancient stable rows the visibility map says “all visible, trust the index.” For recently-updated rows it falls back to a heap fetch. Running VACUUM (or autovacuum tuned aggressively) updates the visibility map and keeps index-only scans actually … index-only.

Materialized views for expensive aggregations — if a dashboard recomputes SUM(amount) GROUP BY region, day from 10 B rows on every render, no index helps. Precompute:

1
CREATE MATERIALIZED VIEW sales_daily AS
2
SELECT region, date_trunc('day', created_at) AS day, SUM(amount) AS total
3
FROM orders GROUP BY 1, 2;
4

5
CREATE UNIQUE INDEX ON sales_daily(region, day);
6
REFRESH MATERIALIZED VIEW CONCURRENTLY sales_daily;  -- nightly cron

You’ve traded freshness for read latency — the right move for reporting and analytics endpoints.

Balancing the trade-off#

A realistic rule of thumb for the maintenance cost of an index:

Every index pays on every write. That’s why staff-level answers always name the write side when proposing a new index.

flowchart TD
    Q["<img src="/icons/mdi-help-circle-outline.svg" alt="mdi:help-circle-outline" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> New query arrives"]:::ask
    RATE{{"Read rate ≫ write rate?"}}:::ask
    HOT{{"Always filters same subset?"}}:::ask
    SORT{{"Sorts / orders by a column?"}}:::ask
    AGG{{"Aggregates over many rows?"}}:::ask

    COMP["<img src="/icons/mdi-file-tree.svg" alt="mdi:file-tree" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> Composite index<br/><span class='sub'>equality → range → sort</span>"]:::ok
    PART["<img src="/icons/mdi-filter-outline.svg" alt="mdi:filter-outline" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> Partial index<br/><span class='sub'>WHERE predicate</span>"]:::ok
    COVER["<img src="/icons/mdi-table-column.svg" alt="mdi:table-column" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> Covering index<br/><span class='sub'>INCLUDE columns</span>"]:::ok
    MV["<img src="/icons/mdi-table-eye.svg" alt="mdi:table-eye" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> Materialized view<br/><span class='sub'>+ index the view</span>"]:::ok
    NONE["<img src="/icons/mdi-close-circle-outline.svg" alt="mdi:close-circle-outline" class="diagram-node-icon" width="24" height="24" style="display:block;margin:0 auto 4px;" /> Leave it; seq-scan<br/><span class='sub'>writes too hot</span>"]:::warn

    Q --> RATE
    RATE -->|"yes"| HOT
    RATE -->|"no — writes dominate"| NONE

    HOT -->|"yes"| PART
    HOT -->|"no"| SORT

    SORT -->|"yes"| COMP
    SORT -->|"no"| AGG

    AGG -->|"yes"| MV
    AGG -->|"no — few columns"| COVER

classDef ok stroke:#16a34a,stroke-width:1.75px;
classDef warn stroke:#d97706,stroke-width:1.75px;
classDef ask stroke:#6366f1,stroke-width:1.75px;

Finding indexes you don’t actually need — Postgres keeps counters for every index:

1
-- Indexes that have never been used since the last reset
2
SELECT schemaname, relname AS table, indexrelname AS index, idx_scan
3
FROM   pg_stat_user_indexes
4
WHERE  idx_scan = 0
5
ORDER  BY pg_relation_size(indexrelid) DESC;
6

7
-- Queries that do full table scans worth fixing
8
SELECT query, calls, total_exec_time
9
FROM   pg_stat_statements
10
WHERE  query !~* 'pg_'
11
ORDER  BY total_exec_time DESC
12
LIMIT 20;

Production heuristic: drop any index with idx_scan = 0 after 30 days of traffic (except the ones only used by rare cron jobs — tag those). Every dropped index is free write throughput.

One-sentence summary per type#

Pitfalls to volunteer#

• Over-indexing. Each index slows every write on the table; audit unused ones via pg_stat_user_indexes in Postgres.
• Leftmost-prefix rule. (a, b, c) index does not help WHERE b = ?. A composite index is an ordered commitment.
• Indexes on low-cardinality columns are mostly useless. A B-tree on status with three values (pending, active, done) rarely beats a seq scan.
• Functional indexes. If you query LOWER(email) = ?, you need CREATE INDEX ON users (LOWER(email)) — a regular index on email won’t be used.
• NULL semantics. Most indexes do store NULLs (Postgres, MySQL B-tree) but some operators won’t use them; WHERE col IS NOT NULL usually bypasses the index unless you have a partial index.
• Partial indexes. CREATE INDEX ON orders (user_id) WHERE status = 'open' keeps the index small when the hot query only looks at a sliver of the table — Postgres specialty.
• Writes during read queries. Long-running analytical reads on an LSM-heavy table can pin old SSTables on disk; compaction can’t reclaim space. Watch tombstone accumulation in Cassandra.
• Index-only scans. Postgres only uses them if the visibility map says the page is all-visible. A covering index that looks covering still hits the heap on recently-updated rows. Vacuum matters.

Indexes are a single abstraction with many implementations, each tuned to a different workload shape. You’ll be fine in 95% of interviews by answering B-tree and defending it; the other 5% is recognizing the shape of the problem — heavy writes (LSM), proximity (geohash/R-tree), substring (inverted) — and reaching for the right tool. Everything else is optimization.