Indexes and B-trees

The problem: finding one row

Snip's links table will hold about 600 million rows after five years (01.05 Back-of-the-envelope estimation). An owner opens their dashboard and Snip runs:

SELECT code, long_url, created_at
FROM links
WHERE owner_id = 42
ORDER BY created_at DESC
LIMIT 50;

Without help, the database has only one way to answer: read every row in the table, keep the ones where owner_id = 42, then sort them. That's a full table scan: about 300 GB read to return 50 rows. At SSD speeds that's around 15 seconds, for every dashboard load.

An index is a sorted copy with a map

An index is a separate structure that keeps one or more columns in sorted order, each entry pointing at its row. Because it's sorted, the database can jump to the right place instead of reading everything, the way you'd find a word in a dictionary.

Almost every relational database uses a B-tree for this. Data on disk is read in pages (8 KB in Postgres), so a B-tree packs hundreds of sorted keys into each page:

• The root page holds a few hundred keys, each pointing to a page on the next level down.
• Each inner page splits its range further.
• The leaf pages hold every key in order, each with a pointer to its row.

Because each level multiplies by hundreds, the tree is very shallow. Three hundred keys per page means three levels cover 27 million rows and four cover 8 billion. Finding any one row takes about four page reads, and the upper levels are usually already in memory. Try it with Snip's table:

Column order matters

An index on several columns sorts by the first, then by the second within each first value, and so on, like a phone book sorted by surname, then first name. That decides which queries it can help:

CREATE INDEX links_owner_created ON links (owner_id, created_at DESC);

The rule: an index helps a query that filters on a leftmost prefix of its columns. Put columns compared with = first, then the column you sort or range over.

If an index also contains every column a query needs, the database can answer from the index alone without visiting the table at all. That's a covering index, and it saves a page read per row.

What indexes cost

Indexes make reads fast by making writes slower:

• Every insert updates every index. A table with six indexes does seven writes for each new row, and an update to an indexed column changes the index too.
• Storage. Each index is a sorted copy of its columns; several indexes can rival the table in size.
• Memory. Hot indexes want to stay in RAM. Unused indexes still compete for it.

So index for the queries you actually run, check that each index is used, and drop the ones that aren't. Snip's links table needs just two: the primary key on code (for redirects) and (owner_id, created_at) for dashboards.

B-trees also handle ranges and sorting (created_at > …, ORDER BY), which is why they're the default. Hash indexes find exact matches only, and specialised indexes exist for text search, locations and arrays.

Recap

Interview questions