Step by step
The example above, written out — the same steps the animation plays.
- 1No index on email. The rows are stored in the order they were added. With no index, the only way is to check them one by one.
- 2Check row 1. kiran@mail.com ≠ priya@mail.com.
- 3Check row 2. asha@mail.com ≠ priya@mail.com.
- 4Check row 3. ravi@mail.com ≠ priya@mail.com.
- 5Found — after reading all 16 rows. A full table scan reads every row: on 1,000,000 rows that is 1,000,000 reads.
- 6With an index on email. The index is a separate B-tree of emails kept in sorted order, each pointing to its row.
- 7Read the root page. Separators: gita@mail.com, meera@mail.com, ravi@mail.com. "priya@mail.com" sorts into child 3 of 4.
- 8Read leaf 3. "priya@mail.com" is here, with a pointer to its row.
- 9Fetch row 15. Follow the pointer straight to row 15. 2 index pages + 1 row instead of 16 rows. On 1,000,000 rows a B-tree is only ~3–4 levels deep.
What's happening?
- Without an index, `WHERE email = …` has to read every row — a full table scan.
- With an index on email, the database reads the B-tree's root, follows one branch to a leaf, and finds a pointer to the row.
- A B-tree is very wide and shallow, so even a million rows need only three or four page reads.
Complexity
- Time
- O(log n) lookup with an index · O(n) full scan without
- Space
- Extra storage for every index, updated on every write
Where you'll meet it
Every login (WHERE email = ?), every "my orders" page (WHERE user_id = ?), and every slow-query fix starts with checking which index the query uses (EXPLAIN).
Common mistake
Indexing every column. Each index speeds up some reads but slows every INSERT and UPDATE, because the index has to be updated too.
FAQ
Why didn't the full scan stop at the first match?
Without a UNIQUE index the database can't know there is only one match, so it keeps reading.
What does EXPLAIN show?
Whether a query uses an index ("Index Scan") or reads the whole table ("Seq Scan"), and roughly how many rows it expects to read.
When does an index not help?
When the query reads most of the table anyway, wraps the column in a function (WHERE lower(email) = …), or filters on a column the index doesn't lead with.