What are Indexes?

There are two ways for a database to find a row: read every row in the table and check each one, or look the answer up in a small sorted structure built for that purpose (an index). The first way is simple and slow. The second way is what keeps real systems fast.

An index is a data structure that stores the values of one or more columns in sorted order, along with a pointer to the full row. Think of it as a table of contents for your data. You do not read the whole book to find one chapter. You read the table of contents, and it tells you which page to turn to.

A Library Catalog

A library catalog is a register that lists the books in a library. It works like a database table with four columns: book title, writer, subject, and date of publication.

Most libraries keep two catalogs. One is sorted by title. The other is sorted by writer name. That way you can start from a writer whose work you enjoy, or from a title you already know.

Those two catalogs are indexes for the library's collection of books. Each one is a sorted list that is easy to search by one piece of information. The books themselves never move.

What an Index Actually Stores

When you create an index on a column, the database stores two things for every row: the value in that column, and a pointer to where the full row lives.

Say we have a Books table with a title, a writer, and a subject. An index on the Title column is a sorted list of titles, and next to each title is a pointer back to the complete row.

The index is much smaller than the table, because it holds one or two columns instead of all of them. Small and sorted is exactly what makes it fast to search.

What Changes When a Query Uses an Index

Without an index, the database has to read every row in the table and test each one against your WHERE clause. This is called a full table scan. On a table with ten million rows, the database reads ten million rows to return one.

With an index, the database searches the sorted index instead, finds the matching entry, and follows the pointer straight to the row. Most databases store the index as a B-tree, a tree structure that stays balanced as data is added, so a lookup takes only a few steps even on a very large table.

Two things get better:

1. Fewer disk reads. The database touches a few index pages and one data page instead of the entire table. Disk reads are the slowest part of most queries.
2. Free sorting. The index is already in order, so a query that asks for results sorted by the indexed column can skip the sorting step entirely.

Selectivity Decides Whether an Index Helps

Selectivity is how good a column is at narrowing the search. A column with many distinct values, such as an email address, is highly selective: one value matches one row out of millions.

A column with few distinct values is not selective. An index on a gender column, or on a status column that holds only active and inactive, points at half the table. Reading half the table through an index is slower than just scanning the table, because each pointer is a separate jump. Databases know this, and their query planners will often ignore such an index.

The rule of thumb: index the columns you filter on when that filter throws most of the table away.

Indexes at Large Scale

The same idea applies far beyond a single relational table. Imagine a dataset of many terabytes where each record is only about one kilobyte. You cannot iterate over that much data in any reasonable time, so an index is not an optimization, it is a requirement.

A dataset that large is also spread across several physical machines. Something has to tell the system which machine holds the record you want. An index is the usual answer.

Indexes Make Writes Slower

An index is a second copy of some of your data, and copies have to be kept in step.

Every time you insert a row, the database writes the row and then updates every index on that table. The same is true for updates and deletes. Five indexes on a table means one insert becomes six writes.