Indexing

Make queries fast with the right index: B-trees and LSM-trees in plain words, composite column order, covering indexes, and what indexes cost on writes.

17 minLesson 2 of 7
On this page
  1. The idea
  2. Two ways to keep an index sorted
  3. Composite indexes: column order matters
  4. What an index costs
  5. Numbers worth remembering
  6. In the interview
  7. Common mistakes
  8. What to practise next

A shop's orders table has 50 million rows of about 200 bytes each. The account page runs "orders for customer 42 since 1 March". With no index, the database reads every row to find the 3 that match: 50 × 106 × 200 B = 10 GB. At 500 MB/s that is 10 GB ÷ 0.5 GB/s = 20 seconds, for one page view.

Add an index on (customer_id, created_at) and the same query reads a handful of pages and returns in a few milliseconds.

The idea

An index is a second copy of a few columns, kept sorted, with a pointer from each entry back to its row. Like the index at the back of a book: look the word up in a sorted list and jump to the page.

Sorted order is the whole trick: the database jumps to the first matching entry and reads forward. The cost is that every write must also update every index, and indexes take disk and memory.

Two ways to keep an index sorted

B-tree: update in place

A B-tree stores sorted keys in fixed-size pages, a few kilobytes each. Each page holds a few hundred keys, so the tree is very wide and very shallow (the balanced trees lesson shows why it stays balanced). With 500 keys per page, two levels cover 500 × 500 = 250,000 entries and three cover 125 million, so 50 million orders need 3 levels. The top two levels are only about 200 pages (1 root plus 50 million ÷ 500 ÷ 500 = 200) and stay in memory, so a lookup costs about one disk read for the leaf and one for the row.

A write changes the right leaf page where it sits, splitting it if full: a random disk write for each index touched.

LSM-tree: append, merge later

A log-structured merge tree never edits in place. Writes go to a sorted table in memory (plus an append-only log, so a crash loses nothing). When the memory table fills, it is written out as a new sorted file. A background job merges files together, dropping overwritten and deleted values; this is called compaction.

Writes are fast because they are sequential. Reads pay instead: a key could be in memory or in any of several files, checked newest first. A small per-file Bloom filter answers "definitely not here", so most files are skipped.

Storage engines and indexes
OptionGood atBad atPick it when
B-tree Usual defaultPredictable fast reads and range scans. One place for each key.Each write is a random page update per index. Pages are often partly empty.Read-heavy or mixed workloads. Most relational databases. The usual answer.
LSM-treeVery high write rates; writes are sequential. Compresses well.Reads may check several files. Compaction uses disk and CPU in the background and can cause latency spikes.Write-heavy data: event logs, messages, metrics. Common in wide-column and key-value stores.
No extra indexWrites stay cheap. No extra storage.Every query not on the primary key scans the table.Small tables, columns never filtered on, or bulk analytics that read everything anyway.

Composite indexes: column order matters

An index on (customer_id, created_at) sorts by customer first, and by date only within each customer. Like a phone book sorted by last name then first name: easy to find every "Garcia", useless for finding every "Maria". Step through two queries against the same index.

One composite index, two queriesUse the arrows or ← → keys
-- index on (customer_id, created_at)WHERE customer_id = 42 AND created_at >= '03-01'WHERE created_at >= '03-01'
  1. index
    041|03-28
    142|02-11
    242|03-02
    342|03-15
    442|03-27
    543|01-04
    643|03-20
    entries read
    0

    1Index entries are sorted by customer, then date. The first query wants customer 42 since 1 March.

  2. index
    041|03-28
    142|02-11
    242|03-02start
    342|03-15
    442|03-27
    543|01-04
    643|03-20
    entries read
    1
    matches
    1

    2The tree jumps straight to the first entry at or after (42, 03-01). It skips 42|02-11 without reading it.

  3. index
    041|03-28
    142|02-11
    242|03-02
    342|03-15
    442|03-27scan
    543|01-04
    643|03-20
    entries read
    3
    matches
    3

    3Read forward. The next two entries are still customer 42 and after 1 March: matches.

  4. index
    041|03-28
    142|02-11
    242|03-02
    342|03-15
    442|03-27
    543|01-04stop
    643|03-20
    entries read
    4
    matches
    3

    4The next entry is customer 43. Everything after it is a later customer, so the scan stops. 4 entries read, 3 matches.

  5. index
    041|03-28
    142|02-11
    242|03-02
    342|03-15
    442|03-27
    543|01-04
    643|03-20
    entries read
    0

    5Second query: every order since 1 March, any customer. Dates are sorted only inside each customer, so matches are scattered.

  6. index
    041|03-28
    142|02-11
    242|03-02
    342|03-15
    442|03-27
    543|01-04
    643|03-20
    entries read
    7
    matches
    5

    6There is no place to jump to, so every entry must be read. On 50 million rows, that is a scan of all 50 million index entries, plus a row fetch per match. This query needs its own index starting with created_at.

1 / 6

The rule: put columns tested with equals first, then the one column used for a range or sort. An index on (a, b, c) serves queries on a, on a, b, and on a, b, c, but not on b alone. Columns after a range condition help little, because inside the range they are no longer sorted.

Covering indexes

After finding 3 entries, the database still fetches 3 rows to read total: one random read each. If the index is (customer_id, created_at, total), the answer is in the index itself and the table is never touched. That is a covering index. It matters most on hot queries that return many rows: for a 200-row page it saves 200 reads. The cost is a bigger index.

What an index costs

Every index is maintained on every write. A table with a primary key and 3 secondary indexes does 4 B-tree updates per insert. At 2,000 inserts a second, that is 2,000 × 4 = 8,000 page changes a second instead of 2,000. Indexes also need memory: an index whose upper levels do not fit in RAM turns each lookup into several disk reads.

So index for the queries you actually run, and drop indexes nothing uses.

Numbers worth remembering

  • A lookup in a B-tree index: 3 or 4 levels for up to hundreds of millions of rows, usually 1 or 2 disk reads because the top levels are cached.
  • A random read: about 0.1 ms on an SSD, about 10 ms on a spinning disk. A sequential scan: hundreds of MB a second.
Estimate: Size of one index

How big is an index on (customer_id, created_at) for the orders table?

You know
  • 50 million orders
  • customer_id and created_at are 8 bytes each, the row pointer about 8 bytes
  • Assume about 40 bytes per entry once page overhead is included

Show the working
  1. 8 + 8 + 8 = 24 bytes of data per entry; round up to 40 for page overhead and free space
  2. 50 × 106 × 40 B = 2 × 109 B = 2 GB

Estimate 2 GB (anything from 700 MB to 6 GB is a good answer)

2 GB fits in memory on one server, so lookups stay fast. Ten such indexes would be 20 GB of RAM to keep hot.

In the interview

Bring up indexes right after the access patterns. For each hot query, name the index that serves it, with column order. When writes are heavy, say how many indexes you will pay for.

Indexing an order history
Interviewer

Users see their orders, newest first, 20 per page. How does that stay fast?

You

That query filters by customer and sorts by date, so I'd index (customer_id, created_at DESC). The database jumps to the customer and reads 20 entries in order: no sort, no scan. If the page only shows date and total, I'd add total to make it covering.

Interviewer

Support also searches orders by status. Add an index on status?

You

Alone, no. There are maybe five statuses, so "status = shipped" matches a huge share of rows, and the index barely narrows anything. If support filters by status within a date range, I'd index (status, created_at), or run those queries on a replica.

Follow-ups you should expect:

  • "How do you add an index to a 500 GB live table?" Use the database's online index build, which avoids blocking writes but takes hours and extra I/O. Run it off-peak.
  • "How do secondary indexes work when the data is sharded?" A local index per shard means a query by that column asks every shard. A global index is partitioned by the indexed value, so reads hit one place but each write updates another shard, usually asynchronously. See sharding.

Common mistakes

Quick check

Index on (country, city, signup_date). Which query can use it best?

A B-tree page holds 100 keys. How many levels index 1 million rows?

A service appends 80,000 events a second and reads them rarely, by key. Which storage engine fits?

What to practise next

An index makes one machine fast; replication keeps copies on several machines, which is next. Indexes for prefix lookups appear in Design Typeahead Search.