system-design · beginner

Database Indexes — Find Rows Without Scanning Everything

The Central Question

Consider a production orders table in an e-commerce platform holding 50,000,000 purchase records.

A user opens their mobile application, triggering the following backend API request:

SELECT order_id, total_amount, created_at
FROM orders
WHERE user_id = 89041
ORDER BY created_at DESC
LIMIT 20;

Without an auxiliary search structure, the database engine must execute a Sequential Table Scan (Full Table Scan). It reads all 50,000,000 rows from physical storage into RAM memory, evaluates user_id = 89041 for every single row, sorts the matching subset in memory, and returns 20 rows.

At 50,000,000 rows, a sequential scan consumes 100% database CPU, reads gigabytes of disk I/O, and takes 8 to 15 seconds to execute—causing severe API timeouts.

To transform expensive full table scans into sub-millisecond lookups, databases use Indexes.

A Database Index is a secondary, self-balancing search data structure (most commonly a B-Tree) maintained alongside table data to locate matching rows quickly without reading un-related rows.

This lesson answers one central question: How do B-Tree and Hash database indexes transform $O(N)$ full table scans into $O(\log N)$ or $O(1)$ disk lookups, and how do engineers design multi-column composite indexes while balancing read acceleration against write amplification penalties?

Scan vs. Seek: Sequential Scans vs. B-Tree Index Traversal

The performance difference between un-indexed and indexed queries maps directly to algorithmic time complexity:

flowchart TB
  subgraph Sequential Scan: O(N) Un-indexed Search
    Q1[Query: WHERE user_id = 89041] --> ReadAll[Read 50,000,000 Rows sequentially from disk heap]
    ReadAll --> Filter[Evaluate user_id for every row in memory]
    Filter --> Time1[Execution Time: 12,000 ms]
  end
  subgraph B-Tree Index Seek: O(log N) Indexed Search
    Q2[Query: WHERE user_id = 89041] --> Traverse[Traverse B-Tree Root -> Branch -> Leaf]
    Traverse --> DirectRead[Read exact 20 Heap Tuples via disk pointers]
    DirectRead --> Time2[Execution Time: 1.5 ms]
  end

Figure 1: Algorithmic contrast between an $O(N)$ sequential table scan and an $O(\log N)$ B-Tree index lookup.

Algorithmic Mathematical Comparison

Where $B$ is the B-Tree fan-out factor (typically $B \approx 100$ to $500$ entries per node page). A B-Tree indexing 50,000,000 rows requires only 3 to 4 pointer hops from root to leaf!

B-Tree Anatomy: How Indexes Work on Disk

The B-Tree (Balanced Tree) is the standard index data structure in PostgreSQL, MySQL InnoDB, and Oracle. It keeps indexed keys in sorted order across fixed-size disk page nodes:

flowchart TD
  Root["Root Node Page [Keys: 250, 750]"] --> B1["Branch Node Page [Keys: 50, 100, 200]"]
  Root --> B2["Branch Node Page [Keys: 300, 500, 700]"]
  
  B1 --> L1["Leaf Page 1: Key 50 -> Pointer Tuple #102"]
  B1 --> L2["Leaf Page 2: Key 100 -> Pointer Tuple #891"]
  
  Note1["Leaf Node Pages form a doubly linked list for fast range scans."]

Figure 2: Architectural anatomy of a B-Tree index structure showing Root, Branch, and Leaf pointer nodes.

B-Tree Leaf Page Doubly-Linked Range Scans

1. Root and Branch Nodes: Direct search traversals downward to the correct leaf page based on key comparisons.
2. Leaf Nodes: Contain the actual indexed column values alongside Tuple ID (TID) Disk Pointers targeting the underlying table heap.
3. Doubly Linked Leaf Chain: All leaf pages link sequentially to their adjacent neighbors. This enables ultra-fast range queries (WHERE created_at BETWEEN '2026-01-01' AND '2026-01-31') without re-traversing the tree from the root.

Composite Indexes and the Left-Prefix Rule

A Composite Index indexes multiple columns together in a specific, defined order, such as (user_id, status, created_at DESC).

The order of columns defined in a composite index dictates which queries can utilize the index based on the Left-Prefix Rule:

flowchart TD
  IndexDef["Composite Index: (user_id, status, created_at)"] --> Q1{"WHERE user_id = 89041?"}
  Q1 -->|Uses Left-Prefix| Match1[Fully Indexed - Fast Seek]
  
  IndexDef --> Q2{"WHERE user_id = 89041 AND status = 'COMPLETED'?"}
  Q2 -->|Uses Left-Prefix| Match2[Fully Indexed - Fast Seek]
  
  IndexDef --> Q3{"WHERE status = 'COMPLETED'?"}
  Q3 -->|Violates Left-Prefix!| Miss[CANNOT use Index! Full Table Scan]

Figure 3: Operational flow chart illustrating the Composite Index Left-Prefix Rule.

Left-Prefix Rule Summary

• WHERE A = ?
• WHERE A = ? AND B = ?
• WHERE A = ? AND B = ? AND C = ?

The Hidden Cost: Write Amplification

While indexes accelerate read queries, they impose a direct write penalty on every INSERT, UPDATE, and DELETE operation known as Write Amplification:

flowchart LR
  App[Application INSERT Statement] --> TableHeap[Write 1 Row to Table Heap]
  App --> Idx1[Update Primary Key B-Tree]
  App --> Idx2[Update Index 2: user_id B-Tree]
  App --> Idx3[Update Index 3: status B-Tree]
  App --> Idx4[Update Index 4: email B-Tree]

Figure 4: Write amplification illustrating one table insert updating four separate disk index structures.

The Write Amplification Trade-off

Over-indexing write-heavy tables degrades insert QPS, increases CPU lock contention, and inflates disk storage consumption.

Complete Worked Example: PostgreSQL EXPLAIN ANALYZE Optimization

Let's inspect a real-world optimization walkthrough for the CheckoutLab platform (checkoutlab.com).

1. Un-Indexed Slow Query Output

EXPLAIN ANALYZE 
SELECT * FROM orders 
WHERE user_id = 89041 
ORDER BY created_at DESC 
LIMIT 20;
-- QUERY PLAN:
-- Limit (cost=125430.12..125430.17 rows=20 width=142) (actual time=8412.110..8412.125 rows=20 loops=1)
--   -> Sort (cost=125430.12..125980.40 rows=22011 width=142)
--        Sort Key: created_at DESC
--        -> Seq Scan on orders (cost=0.00..124102.00 rows=22011 width=142)
--             Filter: (user_id = 89041)
-- Execution Time: 8415.420 ms

2. Creating the Composite Covering Index

-- Create Composite Index CONCURRENTLY to avoid blocking production table writes
CREATE INDEX CONCURRENTLY idx_orders_user_created 
ON orders (user_id, created_at DESC);

3. Optimized Indexed Query Output

EXPLAIN ANALYZE 
SELECT * FROM orders 
WHERE user_id = 89041 
ORDER BY created_at DESC 
LIMIT 20;
-- QUERY PLAN:
-- Limit (cost=0.43..12.45 rows=20 width=142) (actual time=0.045..0.112 rows=20 loops=1)
--   -> Index Scan using idx_orders_user_created on orders (cost=0.43..13241.12 rows=22011 width=142)
--        Index Cond: (user_id = 89041)
-- Execution Time: 0.145 ms

Execution time dropped from 8,415 ms down to 0.145 ms (a 58,000x speedup)!

Failure Modes and Engineering Mitigations

What You Should Remember

1. Indexes trade write cost for read speed: Indexes use B-Trees to transform $O(N)$ sequential scans into $O(\log N)$ disk seeks.
2. Left-Prefix Rule governs composite indexes: A composite index on (A, B, C) only accelerates queries that filter on leading column prefixes (A, A+B, A+B+C).
3. Beware Write Amplification: Every secondary index forces an additional disk write on inserts, updates, and deletes.
4. Use CONCURRENTLY for production migrations: Standard index creation acquires table write locks; always build indexes concurrently in production.
5. Verify query plans with EXPLAIN ANALYZE: Never guess whether an index helps; inspect execution plans to confirm index scans.

Index Maintenance & Vacuuming Mechanics

Partial Indexes and Expression Indexes

Glossary of Terms

Practice Scenario and Self-Assessment

Architecture Scenario

CREATE TABLE messages (
    id BIGSERIAL PRIMARY KEY,
    sender_id BIGINT NOT NULL,
    recipient_id BIGINT NOT NULL,
    created_at TIMESTAMP NOT NULL,
    body TEXT
);

The application executes two frequent queries:

• Query 1: SELECT FROM messages WHERE recipient_id = 42 ORDER BY created_at DESC LIMIT 50;
• Query 2: SELECT FROM messages WHERE sender_id = 42 AND recipient_id = 99;

1. Design the minimal set of composite indexes to optimize both queries without creating redundant index write amplification.
2. Explain why creating an index on (created_at, recipient_id) fails to optimize Query 1 under the Left-Prefix Rule.

Interactive Self-Assessment

It violates the Left-Prefix Rule because the query omits the leading column (user_id).

Composite indexes only support integer columns.

B-Tree indexes cannot execute equality filter comparisons.

The query must explicitly specify the index name in the FROM clause.

It acquires an exclusive table write lock for the duration of the build, blocking all incoming application writes.

It deletes all primary key constraints on the target table.

It converts the database network protocol from TCP to UDP.

It automatically drops all other existing secondary indexes on the table.

What to Learn Next

• Data Replication — Keeping Copies in Sync: Learn how secondary indexes behave across read replicas.
• Database Sharding — Split Data Across Many Machines: Master partitioning strategies when tables outgrow a single node.
• ACID Transactions — All-or-Nothing Database Work: Explore how indexes enforce unique constraints during transactions.

Track: Data, Storage and Messaging

Previous: Database Storage Architectures — B-Trees vs. LSM-Trees

Next: Database Sharding — Split Data Across Many Machines

By Shubham Jain

All articles · Study paths

Shubham Jain · Learning Lab