An index is a separate data structure that keeps values and row locations in order, much like the index at the back of a book. Many databases use B+ trees to find rows among millions of records by reading only a few pages.
A simulator comparing B+ tree lookups and full table scans
1. Choose a value and a lookup method
The tree above is an index on the id column. The five boxes below are table pages containing the actual rows. Notice that the table pages are not sorted.
Three properties of a B+ tree
First, each node contains several sorted keys and pointers to children between them. A node represents a disk page, so one read can compare hundreds of keys, keeping the tree shallow. Second, row locations appear only in the leaves. Third, leaves are linked horizontally: for a range condition (BETWEEN, >, <), find the first leaf and then follow the links.
An index is not always faster
Fetching each indexed row may require a separate table-page read. If many rows match, a full scan can be faster. Widen the range to see the table-page count approach that of a full scan. The query optimizer estimates this cost when deciding whether to use an index.
Interview topic: when an index cannot help
Applying a function or arithmetic to a column (WHERE YEAR(joined_at) = 2024, WHERE price * 2 > 100) can prevent an ordinary index on that column from being used for a lookup. LIKE '%term'A leading wildcard has a similar effect. A composite index on (a, b) is sorted by a first, so filtering only by b may not give an efficient lookup (the leftmost-prefix rule). More indexes also mean more work on INSERT, UPDATE, and DELETE, slowing down writes.