Learn System Design Database Indexing
DatabasesDatabase 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.
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.
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.
leaf 1
leaf 2
leaf 3
leaf 4
leaf 5
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.)
Bucket 0
Bucket 1
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.
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)
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 Is the table big enough to care?
- 2 Text search? Inverted
- 3 Location? Geospatial
- 4 Otherwise: B-tree
Use
Test yourself
Which index?
Answer from the diagrams above. Nothing is saved or sent anywhere.
Your score
0 / 4
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.