Index Fundamentals
Concept. An index maps a search key, such as artist, to the data pages containing matching rows. It replaces a full-table scan with a small number of IOs.
Intuition. Without an index, WHERE artist = 'Beatles' scans all 160,000 pages of the 10 TB Songs table. With an index on artist, the database looks up "Beatles lives on page 47," reads page 47, and returns the matching songs. Same answer, 80,000× fewer IOs. Same idea as the index in paper books. If we want to find the word 'threads' in a UNIX book, we don't scan all pages. We lookup the index at the back of the book and find the pages with 'threads'.
How paper books use indexes
Figure: Index finds topics quicklyA Python programming book has a Quicksort section on page 201 in its sorting chapter. The separate alphabetical index lists Binary search, Functions, Loops, Quicksort, and Variables. Quicksort points to pages 201 and 208; the arrow leads to page 201. The chapters remain in teaching order.
Figure 1. A separate index points into chapter-ordered pages. A Python programming book organizes its chapters for teaching, not alphabetically by topic. Its back-of-book index sorts topics: “Quicksort” points to pages 201 and 208.
Figure: Sorted pages need only a range indexA dictionary page 128 contains dragon, draw, and dream. A small range index maps door–dozen to page 127, dragon–dream to page 128, and dress–dry to page 129. Since the words are sorted, the index need not list every word. This is an Oxford English Dictionary analogy, not a reproduction of its index.
Figure 2. Sorted pages need only a range index. Think of the Oxford English Dictionary: its words are already alphabetical. An index can store each page’s word range rather than every word. To find “draw,” choose the dragon to dream range, then search page 128.
What an Index Stores
This page defines what every index stores. The next four pages each show a different way of organizing those (key, page#) pairs: hash indexes for equality, B+Trees for ranges, SSTables for immutable writes, and LSM trees for write-heavy workloads.
Note: We call these as lookup keys (or just keys) to denote what we are looking for. These don't have to be primary keys or foreign keys (like we saw in SQL schemas in M1).
Data and index live on disk in 64 MB pages. A data page holds whole rows: a Songs row with its audio and metadata is roughly 10 MB, so 1 M songs is 10 TB, about 160,000 pages. An index page holds only (search_key, page#) pairs of 8 to 20 bytes, so 1 M of them is 20 MB, a single page. The pointer (e.g, the page 47) half of each pair, is the compact coordinate that helps us jump to the row.
Figure: Index keys and pointers, not whole rowsTable size vs index size: on the left the Songs table is a 10 TB file of 160,000 pages storing whole rows. On the right the artist index is a 20 MB file of one page storing only (artist, page#) pointers. Size bars beneath show 10 TB vs 20 MB at the same horizontal scale. Both the table and the index live on disk and are shown green; the size difference is carried by the bar widths, not by colour. Color key: green is on-disk storage; the 10 TB table bar versus the 20 MB index sliver shows the roughly 500,000x size difference.
Figure 3. The Songs table stores 10 MB rows (10 TB, 160,000 pages). The artist index stores 20-byte pointers (20 MB, one page), 500,000 times smaller. WHERE artist = 'Beatles' without an index scans 160,000 pages. With an index, the database reads one index page, learns Beatles is on page 47, then reads page 47. The query uses two IOs instead of 160,000, 80,000 times fewer for the same answer.
When to Add an Index, and When to Skip It
An index is a tradeoff: faster reads in exchange for extra storage and slower writes. It pays off on columns the query engine uses, and that narrow the result set down to a few rows.
Add an index when
-
Primary keys (indexed automatically in most databases)
-
Foreign keys, because joins walk them constantly
-
High-selectivity columns with many unique values, like
emailoruser_id -
Frequently filtered columns that
WHEREclauses target
Skip the index when
-
Rarely queried columns: you pay the cost without the benefit
-
Low-selectivity columns like a boolean, where the index points at half the table
-
Frequently updated columns, because every write rewrites the index too
-
Small tables (under about 1,000 rows), where a scan is already fast