Database Indexing for System Design Interviews

01 How Database Indexes Work

Unless you're interviewing for a database-internals role, the storage details below won't be asked directly. But they're the foundation for understanding why indexes exist at all.

Data lives on disk, in pages

When data is stored in a database it's ultimately written to disk as files. The main table is typically a heap file — a collection of rows in no particular order, like a notebook where you write entries as they arrive. The data lives on disk (SSDs today), but it can only be processed once it's loaded into RAM. So every query requires reading data from disk into memory.

Querying without an index means scanning every page one by one — loading each into memory to check whether it contains the target. With millions of pages that's millions of relatively slow disk reads to find a single record: flipping through every page of a massive book to find one word.

How the index changes the access pattern

An index transforms the access pattern. Instead of reading every page sequentially, the index gives a structured path directly to the data, minimizing how many pages you touch by telling you exactly which page holds your target. It's the difference between reading every page of a book and using the table of contents to jump to the right one.

Indexes aren't free — the cost side

Every index costs additional disk space, sometimes nearly as much as the original data. Writes take a hit too: inserting or updating a row means the database must update the main table and every index on it, so one write can trigger several disk writes.

In practice the memory impact is often overblown — modern databases have smart buffer-pool management that softens the cost of multiple indexes. Still, monitor index usage and avoid creating indexes that don't earn significant benefit.

02 B-Tree Indexes

The most common index type. A balanced tree that keeps data sorted and minimizes the disk reads needed to find any value.

The rules every B-tree node follows

This structure maps perfectly onto disk storage: each node is sized to fit in a single 8 KB page, maximizing I/O efficiency. When PostgreSQL looks up id=350, it may read only 2–3 pages: the root, maybe one internal node, then the leaf.

Real-world examples

PostgreSQL uses B-trees for almost everything — primary keys, unique constraints, and most regular indexes. Creating this table:

CREATE TABLE users (
    id SERIAL PRIMARY KEY,
    email VARCHAR(255) UNIQUE
);

automatically creates two B-tree indexes — one for the primary key, one for the unique email constraint. Both rely on sorted order for uniqueness checks and range queries.

DynamoDB organizes items within a partition in sort-key order for efficient range queries; its internals aren't fully documented but it's understood to use an LSM-style engine rather than a B-tree. Even MongoDB uses B-trees — specifically B+ trees, a variant where all data lives in the leaf nodes:

db.users.createIndex({ "email": 1 });

This creates a B-tree mapping email values to document locations.

03 LSM Trees (Log-Structured Merge Trees)

B-trees handle balanced workloads well. But what happens when writes dominate — say a metrics system like Datadog ingesting millions of readings per second?

With a B-tree, each write means finding the right leaf page, reading it into memory, updating it, and writing it back. At a few thousand writes/sec that's fine. At 100,000 writes/sec those random disk seeks become the bottleneck — like updating folders scattered throughout a filing cabinet, spending more time searching than storing.

How LSM trees work

The trick: batch writes in memory and flush them to disk sequentially, converting many small random writes into fewer large sequential ones.

The cost: reads get harder

Where a B-tree finds any record in 2–3 reads, an LSM read must check multiple places, newest first: the memtable → any immutable memtables awaiting flush → all SSTables on disk. A single point query might touch dozens of files in the worst case — like hunting for a document that could be in your desk drawer, a filing cabinet, or any of several archive boxes.

In the wild: Cassandra stores Netflix's billions of viewing events without slowing playback; RocksDB (Facebook) is the storage engine behind many databases, handling millions of social interactions/sec; DynamoDB is understood to use an LSM-style architecture for high write throughput (its exact internals aren't public, and it does not switch engines based on access patterns).

04 Hash Indexes

A specialized tool: blazing-fast exact-match lookups, and nothing else.

# hash index on email
buckets[hash("alice@example.com")] -> [ptr to page 1]
buckets[hash("bob@example.com")]   -> [ptr to page 2]

Collisions are handled by allowing multiple entries per bucket — many systems use chaining with overflow storage (PostgreSQL's hash indexes link buckets to overflow pages). To find a user by email: hash it, go to the bucket, follow the pointer.

PostgreSQL supports hash indexes but doesn't use them by default; as its docs note, "B-trees can handle equality comparisons almost as efficiently as hash indexes." Redis uses hash tables as its primary structure because all data is in memory; MySQL's MEMORY engine defaulted to hash indexes for the same reason.

05 Geospatial Indexes

Specialized in practice, but a favorite interview topic thanks to location apps like Uber, Yelp, and Find My Friends. The rise of proximity search made this a common focus.

Why regular indexes fall short on location data

Say we're building Yelp: millions of restaurants, each with a latitude and longitude, and a user wants "restaurants within 5 miles of me." The naive approach is two B-tree indexes:

CREATE INDEX idx_lat ON restaurants(latitude);
CREATE INDEX idx_lng ON restaurants(longitude);

This falls apart because we're solving a 2D spatial problem with two independent 1D indexes.

Use the latitude index and you get every restaurant in that latitude band — a strip circling the globe — then must point-check each for longitude. Combine both indexes (an index intersection) and the database merges two large result sets, producing a rectangle far bigger than your circular radius, still needing a distance filter. We need indexes that understand 2D relationships.

Geohash — turn 2D into a 1D string

The simplest to understand, and beautifully so: convert a 2D location into a 1D string that preserves proximity. Divide the world into four squares labeled 0–3, then divide each of those into four, and so on. Each division adds precision. Real geohashes use base-32 encoding to make strings like dr5ru; the longer the string, the more precise:

CREATE INDEX idx_geohash ON restaurants(geohash);

Finding nearby places becomes a prefix range scan. For radius queries you also include adjacent geohash cells (your circle may cross a cell boundary) — still just a handful of prefix range scans. This is exactly how Redis's geospatial commands work internally:

GEOADD restaurants -122.4194 37.7749 "Restaurant A"
GEOSEARCH restaurants FROMLONLAT -122.4194 37.7749 BYRADIUS 5 mi

(GEORADIUS is deprecated in favor of GEOSEARCH.)

Quadtree — subdivide only where it's dense

Instead of turning coordinates into strings, a quadtree directly partitions space into a tree. Start with one square over the whole area. When a square holds more than a threshold of points (the k value, typically 4–8), split it into four quadrants; keep recursing until each region is sparse enough or you hit a max depth.

The key advantage is adaptive resolution — dense areas subdivide finely while sparse regions stay coarse. The cost: unlike geohash, quadtrees need a specialized tree structure rather than reusing existing B-trees, which is why most modern databases prefer geohash or R-tree variants.

R-tree — flexible overlapping rectangles

R-trees are the default spatial index in modern databases (PostgreSQL/PostGIS, MySQL). Rather than splitting into fixed quadrants, they use flexible, overlapping rectangles that adapt to where the data actually clusters. Organizing photos on a table: a quadtree divides the table into equal quarters and keeps subdividing; an R-tree draws natural overlapping groupings around clusters of nearby photos.

Searching for restaurants in San Francisco, an R-tree finds the big rectangle for the city, then drills through progressively smaller overlapping rectangles down to individual locations. Because rectangles adapt, a single R-tree can index both points and larger shapes — restaurant pins, delivery-zone polygons, road networks — in one structure. Quadtrees struggle with mixed data, subdividing endlessly to isolate shapes.

06 Inverted Indexes

B-trees are great for exact matches and ranges but fail at searching through text content.

SELECT * FROM posts WHERE content LIKE '%database%';

Consider three posts:

doc1: "B-trees are fast and reliable"
doc2: "Hash tables are fast but limited"
doc3: "B-trees handle range queries well"

The inverted index maps each token to the documents it appears in:

b-trees  -> [doc1, doc3]
fast     -> [doc1, doc2]
reliable -> [doc1]
hash     -> [doc2]
range    -> [doc3]
queries  -> [doc3]

A search for fast just looks up the token and returns [doc1, doc2] — pointers to the pages holding those rows.

You'll find inverted indexes wherever real text search happens — searching GitHub repos, Slack history, or documentation. The trade-offs: substantial storage overhead and careful updates (changing a document means updating entries for every term it contains). For making text searchable, that's a price worth paying.

07 Index Optimization Patterns

Beyond picking a type, experienced engineers analyze read/write patterns and craft indexes that support their actual queries. Two patterns dominate.

Composite indexes — the most common pattern

Instead of one index per column, combine multiple columns into a single index in a specific order, matching how you actually query. A typical feed query:

SELECT * FROM posts
WHERE user_id = 123
  AND created_at > '2024-01-01'
ORDER BY created_at DESC;

Two separate indexes force the database to find posts by user, find posts after the date, intersect, then sort. A composite index does it in one shot:

CREATE INDEX idx_user_time ON posts(user_id, created_at);

Under the hood this is a B-tree whose key is a tuple of both columns, sorted by user_id first, then created_at:

(1, 2024-01-01)
(1, 2024-01-02)
(1, 2024-01-03)
(2, 2024-01-01)
(3, 2024-01-01)

The database seeks to the first user_id=123 entry and scans sequentially until it passes the date range. Because entries are already sorted by created_at within each user, you get filtering and sorting for free — a 2D query collapsed into a 1D ordered scan.

Common interview shapes: order history (customer_id, order_date), event processing (status, priority, created_at), activity feeds (user_id, type, timestamp).

Covering indexes — answer the query from the index alone

-- Regular index
CREATE INDEX idx_user_time ON posts(user_id, created_at);

-- Covering index also stores the likes column
CREATE INDEX idx_user_time_likes ON posts(user_id, created_at) INCLUDE (likes);

Showing a feed with like counts, a regular index finds matching posts then fetches each post's page just to read likes. Including likes in the index skips those page lookups entirely — powerful for read-heavy features like feeds and leaderboards. The trade-off is size: covering indexes store extra columns.

08 Choosing an Index — The Decision Flow

The instructor's confession: in a real interview you rarely go deep on any one index's implementation. What matters is spotting where queries are inefficient, which columns to index, and whether a special index is needed.

09 Active Recall

Answer from memory before expanding each. These test reconstruction and decision-making, not trivia.

10 Quick Revision

A compact refresh — not a replacement for the sections above.