How do indexes speed up search?

An index is a separate data structure (usually a tree or a hash structure) where the DB stores sorted references to table rows. Because of this, a search doesn't scan the whole table, it goes through a much smaller, easy-to-traverse set of data.

In plain terms:

#1. Without an index

The database scans rows one at a time (full scan), comparing the value in the needed column and looking for a match. If there's a lot of data, this is slow, because every row has to be read.

#2. With an index

The index's values are already sorted, and the DB searches them like a phone book, with a fast algorithm (e.g. binary search over a B-tree). It finds the right range right away and only then reaches out to the specific table rows.

#3. What it speeds up

• Searches like WHERE column = X
• Range searches: BETWEEN, >, <
• JOINs on indexed columns
• ORDER BY and GROUP BY, if the index covers the column

#4. The cost of the speedup

• An index takes up disk space
• Inserts/updates get a bit slower (the index has to be updated too)

So: an index lets you avoid reading the whole table and quickly find the rows you need through a sorted structure, which is why search operations run much faster.