Learn System Design Database Indexing

Databases

Database indexing: pick the index from the query

An index is a map that tells the database which page to read, so it doesn't have to read all of them. There are only 4 kinds worth knowing for interviews, and each one exists because the others can't answer a certain kind of question.

4 index types 5 interactive diagrams ~8 min

1 · Why indexes exist

The real cost is reading pages from disk

Rows live on disk in pages. Without an index, WHERE age = 51 means loading every page into memory and checking each row. That's a full table scan. Grow the table and see what happens.

Full table scan
B-tree index

Bars use a log scale, or the index bar would be invisible. Assumes about 100 rows per page and 100 keys per index node.

2 · B-tree, the default

Sorted keys, one path down

A B-tree keeps keys in order. The root says which way to go, and the leaves hold the sorted keys, linked left to right. That one property, sorted order, is why it handles exact matches, ranges and sorting all at once.

root 27405162

leaf 1

12 18 23

leaf 2

27 31 35

leaf 3

40 44 47

leaf 4

51 55 58

leaf 5

62 67 73

Leaves link to their right neighbour: leaf 1 → leaf 2 → … → leaf 5

Pages read:

3 · Hash index

Fastest for one key, useless for a range

A hash index runs the key through a hash function and jumps straight to a bucket. That's great for email = ?. But hashing scrambles the order on purpose, so a range has to open every bucket. (Want the bucket mechanics in more detail? See the HashMap page.)

Where hash wins

In-memory key-value stores like Redis. Every lookup is "give me this exact key", and nobody asks for a range.

Why SQL databases default to B-tree

A B-tree is nearly as fast for exact matches and also handles ranges and ORDER BY. One index covers more future queries.

4 · Geospatial index

"Near me" is two numbers at once

A B-tree sorts on one value. A location is latitude and longitude, so the obvious fix, one B-tree per column, finds the right answer the slow way. Switch between the three approaches and count how many places each one has to read.

latitude index longitude index 60 61 70 62 63 72 b0 b1 c0

Places read

—

Actually nearby

4

  • You
  • Result
  • Read, then thrown away
  • Never touched

Geohash

Turns a location into a string, and nearby places share a prefix. Because it's a string, a normal B-tree can index it. One catch: two places on either side of a cell border can have different prefixes, which is why you search the neighbouring cells too. The labels here are simplified; real geohashes look like 9q8yy.

Quadtree

Splits the map into four squares, and keeps splitting any square that gets too crowded. Dense downtown areas end up as tiny squares and empty areas stay as big ones.

R-tree

Instead of a fixed grid, it draws boxes around groups of nearby objects and nests them. It also works for shapes, like delivery zones, not only points. PostGIS uses this approach.

5 · Inverted index

Find a word anywhere in the text

A B-tree on name sorts by the first letter. "Tony's Pizza Place" sits under T, so LIKE '%pizza%' has to read every row. An inverted index flips it around: every word points to the rows that contain it. Elasticsearch, Lucene and Postgres full-text search all work this way.

B-tree on name (sorted)

  • Blue Bottle Cafe
  • Corner Cafe & Pizza
  • Pizza Hut Express
  • Sushi Express
  • Tony's Pizza Place

The sorted order doesn't help. All 5 rows get scanned.

Inverted index (word → rows)

blue [3]
bottle [3]
cafe [3, 4]
corner [4]
express [2, 5]
hut [2]
pizza [1, 2, 4]
place [1]
sushi [5]
tonys [1]

Rows returned

  • #1Tony's Pizza Place
  • #2Pizza Hut Express
  • #3Blue Bottle Cafe
  • #4Corner Cafe & Pizza
  • #5Sushi Express

6 · In the interview

Read the query, then name the index

Nobody will ask you to draw a B-tree split. They want to see you spot which query is slow and pick the index that fixes it. Pick a query.

  1. 1 Is the table big enough to care?
  2. 2 Text search? Inverted
  3. 3 Location? Geospatial
  4. 4 Otherwise: B-tree

Use

Test yourself

Which index?

Answer from the diagrams above. Nothing is saved or sent anywhere.

Question 1 of 4 Score: 0
You need users aged 40 to 60. Which index makes this efficient?

Keep going

Next up: choosing the database these indexes live in.

This page is built from the ideas in this system design video on database indexing. Watch it for the spoken walkthrough.