Indexes

As a table grows, finding rows gets slow. An index fixes that.

Full table scan

You look up one email, but there is no index on email. The database can't know where that email is, so it reads every row. This is a full table scan. With 10 million rows, it reads 10 million rows, and it gets slower as the table grows.

How an index works

An index is like the index at the back of a book. It keeps one column's values in sorted order, each with a pointer to its row. Because the values are sorted, the database can jump close to the one it wants, instead of reading everything. Most databases store an index as a B-tree, a tree of sorted pages. Finding one value among millions takes only a few steps, and doubling the table adds very little work.

The cost of an index

Every insert, update, or delete must also change each index on the table, so writes get slower. Each index also takes disk space and memory.

Which columns to index

Index the columns your common queries search by, join on, or sort by. An index helps most when a value matches only a few rows, like an email. A yes/no column that matches half the rows helps little; the database may read the whole table anyway. Most databases index the primary key for you.

Composite indexes

A composite index covers more than one column, like (last name, first name). It is sorted by the first column, then by the second, like a phone book. It helps a search by last name, or by both names. It does not help a search by first name alone, because those names are spread all over. This is the leftmost prefix rule.

Remember

• No index: the database reads every row.
• An index is a sorted lookup: fast reads, slower writes, more space.
• Index what you search, join, or sort by.
• A composite index only helps when the query uses its first column.