Database indexes - System Design Guide

Overview

A database index is an extra data structure that lets the database find rows without scanning the whole table, like a book's index lets you find a topic without reading every page. Most indexes are B-trees: balanced, sorted trees where a lookup takes O(log n) page reads, and ranges and sorting come almost for free.

Indexes speed up reads but cost storage and slow down writes, because every insert and update must also update each index. Good indexing means matching indexes to your actual query patterns: the columns in WHERE, JOIN, and ORDER BY, in the right order for composite indexes.

The index at the back of a textbook

To find 'photosynthesis', you look it up alphabetically in the index and jump to page 112 instead of reading every page. But every time a new chapter is added, the index must also be updated.

When to use it

Queries filter, join, or sort on columns of large tables.
Enforcing uniqueness (unique indexes).
EXPLAIN shows sequential scans on large tables.
Covering frequent queries entirely from the index.

Where it shows up in interviews

Query optimization

Recognize it when: a query is slow on a big table.

Speed up an orders history page
Optimize a search filter

Access pattern design

Recognize it when: design indexes for the main queries.

Design the database for Twitter timelines
Design a URL shortener's lookups

Where it is used in real software

B+ trees in databases

PostgreSQL, MySQL InnoDB, SQL Server, and SQLite use B+ trees for primary and secondary indexes.

LSM trees

Cassandra, RocksDB, and ScyllaDB use log-structured merge trees for write-heavy workloads.

Inverted indexes

Elasticsearch and PostgreSQL GIN indexes map words to documents for full-text search.

Key terms

B-tree / B+ tree: Balanced sorted tree; leaves hold keys and pointers, linked for range scans.
Composite index: Index on several columns; order matters (leftmost prefix rule).
Covering index: Contains all columns the query needs, so no table lookup is required.
Selectivity: How well a column narrows results; high selectivity makes indexes useful.
Clustered index: Table rows stored in index order (InnoDB primary key).

How it works, step by step

1
Find frequent and slow queries
Slow query logs and pg_stat_statements.
2
Inspect the plan
EXPLAIN ANALYZE shows scans, joins, and row counts.
3
Design the index
Equality columns first, then range or sort columns: (customer_id, created_at).
4
Consider covering
INCLUDE extra columns to avoid table lookups.
5
Verify and prune
Confirm the plan uses it; drop unused indexes that only slow writes.

B-tree lookup for customer_id = 42

Root: [30 | 60]

Internal: [35 | 45]

Leaf: [40, 42, 44]

Table row

STEP 142 is between 30 and 60, so follow the middle pointer. One page read.

Composite index (customer_id, created_at)

Which queries can use it? (leftmost prefix rule)

Query	Uses index?	Why
WHERE customer_id = 42	Yes	Leftmost column
WHERE customer_id = 42 ORDER BY created_at DESC	Yes, no sort	Rows already ordered by created_at within customer
WHERE customer_id = 42 AND created_at > '2026-01-01'	Yes	Equality then range
WHERE created_at > '2026-01-01'	No (usually)	Skips the leftmost column
WHERE customer_id IN (1, 2) ORDER BY created_at	Partially	Must merge or sort across customers

NOWQuery: WHERE customer_id = 42 | Uses index?: Yes | Why: Leftmost column

Column order is the most important decision in a composite index: equality filters first, then range or sort columns.

Implementation

1-- Before: sequential scan over 50M rows2EXPLAIN ANALYZE3SELECT id, total_cents FROM orders4WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20;5-- Seq Scan on orders ... rows=50000000 ... 4200 ms6 7-- Composite + covering index (PostgreSQL INCLUDE)8CREATE INDEX CONCURRENTLY idx_orders_customer_recent9  ON orders (customer_id, created_at DESC) INCLUDE (total_cents);10 11-- After: index-only scan12-- Index Only Scan using idx_orders_customer_recent ... 0.08 ms13 14-- Partial index: only index what you query15CREATE INDEX idx_orders_pending ON orders (created_at) WHERE status = 'pending';16 17-- Find unused indexes that only slow down writes18SELECT relname, indexrelname, idx_scan FROM pg_stat_user_indexes WHERE idx_scan = 0;

Complexity and performance

B-tree lookupO(log n)

~3-5 page reads for billions of rows.

Full scanO(n)

Reads every page.

Write cost+1 index update each

Per index per write.

Trade-offs

Read speed vs write cost

Each index speeds some reads but slows every insert, update, and delete, and uses disk and memory.

B-tree vs LSM

B-trees give fast reads and in-place updates; LSM trees give much faster writes with background compaction and slightly slower reads.

Variants and related techniques

Hash index

O(1) equality lookups, no ranges.

Partial and expression indexes

Index a subset of rows or a computed value like lower(email).

Inverted, spatial, vector

GIN for text/JSON, GiST for geometry, HNSW for embeddings.

Common mistakes

Wrapping indexed columns in functions.
Fix: WHERE lower(email) = ... cannot use an index on email; create an expression index.
Indexing low-selectivity columns alone.
Fix: A boolean column rarely benefits; combine it with selective columns or use a partial index.
Too many indexes on write-heavy tables.
Fix: Remove unused ones.

Interview questions

How does a B-tree index speed up queries?

It keeps keys sorted in a balanced tree with high fan-out, so a lookup walks a few levels (O(log n) page reads) instead of scanning all rows, and range queries scan adjacent leaves.

Why does the order of columns in a composite index matter?

The index is sorted by the first column, then the second within it, and so on. A query can use the index only for a leftmost prefix of its columns; put equality columns first, then range or sort columns.

Practice problems

Problem	Difficulty	What it trains
Design indexes for 3 queries on an orders table	Easy	Composite order.
Fix a slow report with covering and partial indexes	Medium	Plans.