How does an index speed up data lookup?

An index speeds up lookups because the database doesn't scan every row in sequence, but instead searches a tree-like structure (most often a B-tree).

#The principle

• Without an index, the database scans row by row, a full scan.
• With an index, it walks sorted keys, quickly landing on the right spot, like looking up a word in a dictionary by its first letter.

#Example

A users table with a million rows. Query:

Without an index, all 1,000,000 rows need to be checked. With an index, the database walks a search tree and takes a logarithmic number of steps, for example ~20 instead of a million.

So an index gives you a direct, fast path to the rows you need, instead of forcing the database to read the entire table.