You have a table with a million rows and you ask for one person by name. The database could start at row 1 and read on until it finds them. That works, but it is slow. Databases have a trick for this, and it is the same trick as the index at the back of a book: an index.

The slow way: read every row

A table is a list of rows, kept in the order they were added. Nothing says that names are in any helpful order. If you ask for the row where name = 'Kim', the only safe approach is to look at the first row, then the second, and so on until you find a match. Databases call this a full table scan. With 64 rows it is instant. With a million rows it means a million checks for one answer, and busy websites ask thousands of such questions every second.

The fast way: a sorted list that points at rows

An index is a second, separate structure. It holds the values of one column, sorted, and next to each value it stores where that row lives in the table. Because the values are sorted, you can use binary search: look at the middle entry. If your name comes before it alphabetically, throw away the entire second half; if after, throw away the first half. Repeat. Every look cuts the remaining entries in half, so 64 entries need at most 7 looks, and a million entries need at most 20.

Once the index finds the entry, it hands the database the row's position, and the database jumps straight to that row. Try it below. Pick a name, choose a mode, and press Step to watch each look.

Notice what happens when you change the name. Without an index, the number of looks depends on where that row happens to sit: row 3 is quick, row 60 is slow. With the index, the count barely moves, because halving does not care where the name is.

Seeing it in a real database

You do not build indexes by hand. You ask the database to do it with CREATE INDEX. Here is a small Python program using SQLite, the database that ships with Python. It makes 100,000 users, then asks the database how it plans to answer a query, before and after creating an index:

import sqlite3
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE users (id INTEGER PRIMARY KEY, name TEXT, city TEXT)")
db.executemany("INSERT INTO users (name, city) VALUES (?, ?)",
               [(f"user{i}", f"city{i % 50}") for i in range(100000)])

q = "SELECT * FROM users WHERE name = 'user77777'"
for row in db.execute("EXPLAIN QUERY PLAN " + q):
    print(row[3])

db.execute("CREATE INDEX idx_users_name ON users(name)")
for row in db.execute("EXPLAIN QUERY PLAN " + q):
    print(row[3])

print(db.execute(q).fetchall())

Running it with SQLite 3.45.1 printed:

SCAN users
SEARCH users USING INDEX idx_users_name (name=?)
[(77778, 'user77777', 'city27')]

SCAN is the slow read-every-row approach. SEARCH ... USING INDEX is the fast one. The query itself did not change at all; only the database's plan did. Other databases word this differently (PostgreSQL says Seq Scan and Index Scan, for example), but they all offer a command that shows the plan, and reading it is a great habit when a query feels slow.

A small honest correction

The demo used plain binary search on a sorted list because it is easy to see. Real databases, including SQLite, PostgreSQL and MySQL's InnoDB engine, usually store indexes as a B-tree. It is the same idea, cut into pages that match how disks and memory are read, and it also makes adding new rows cheap. The takeaway is identical: a handful of looks instead of millions.

The catch: indexes are not free

An index is extra data stored next to your table, so it uses space. And every time you add, change or delete a row, the database must also update each index on that table to keep it sorted. So more indexes mean slower writes. A reasonable rule of thumb for a beginner: add an index on columns you often search by (WHERE) or join tables on, and do not index everything "just in case". Primary keys are normally indexed for you.

Also, an index only helps when the database can use the sort order. Searching for names that start with "Ki" can often use it (depending on the database and its settings); searching for names that merely contain "im" usually cannot, because there is no sorted order for "contains".

What to remember

A table is read in the order it was stored. An index is a sorted shortcut that points back to the rows. Ask your database for the query plan, and if you see a scan over a big table on a column you search often, an index may be the fix.