Lesson 3.2 · 15 min
Indexes
Search, range-scan and split a real B+tree, find the break-even point between an index and a full scan, and see which queries a composite index can serve.
The idea in plain words
An index is like the index at the back of a book: instead of reading every page to find a word, you look it up and jump to the right page. It makes finding things fast, but every new page must be added to the index too.
The problem it solves
Without help, finding rows that match a condition means reading the whole table. That is fine for 1,000 rows and far too slow for 100 million.
How it works
- An index is a separate, sorted copy of one or more columns, with a pointer back to each row.
- Because it is sorted, the database can jump to the matching values in a few steps, like a binary search.
- It then follows the pointers to fetch only those rows.
- Every insert, update and delete must also update each index, so indexes slow writes and use space.
Example
A users table has 100 million rows. Finding email = ‘asha@example.com’ without an index reads every row. With an index on email, the database walks about 4 levels of a tree and reads one row: milliseconds instead of minutes.
Key terms
- Index
- A separate sorted structure that points from column values to the rows that have them.
- B+tree
- The tree most databases use for indexes: few levels, so any lookup takes only a few reads.
- Full table scan
- Reading every row because no index helps the query.
- Composite index
- One index over several columns, used from the leftmost column onwards.
- Write cost
- Every insert or update must also change each index on the table.
In this lesson you'll learn
- How a B+tree finds one row in a few page reads, scans ranges, and splits pages on insert.
- When an index stops paying off and a full scan is cheaper.
- How composite indexes and the leftmost-prefix rule decide which queries can use them.
Sections
- Theory: inside a B+tree
- Theory: index or scan?
- Theory: composite indexes
- Design: in the interview
- Check yourself
Cheat sheet
| B+tree lookup | ≈ log₃₀₀(N): 4 levels for 1B rows |
|---|---|
| Composite (a, b, c) | seek on a leftmost prefix |
| After a range column | no more seeking |
| Covering index | no table reads at all |
| Each index | +1 tree write per insert |
The interactive simulations and the quiz load with JavaScript.