How does a relational database handle indexing?

An index works like the index at the back of a book. Without it, finding every mention of "photosynthesis" means reading every page. With it, you look up the word in an alphabetical list and jump straight to the right pages. The list takes extra space and must be updated when the book changes, and databases make exactly the same trade.

Why databases need indexes

Take a users table with a million rows and this query:

SELECT * FROM users WHERE email = 'sam@example.com';

With no index on email, the database must do a full table scan: read every row and check each one. With a sorted index, it can home in on the right entry the way you find a word in a dictionary. Halving a million entries again and again reaches a single one in about 20 steps, since 2²⁰ is just over a million. Twenty steps against a million checks is why a query can drop from seconds to milliseconds.

How a B-tree index works

Most relational databases use B-trees (strictly, a variant called the B+ tree) as their standard index. PostgreSQL creates a B-tree whenever you write CREATE INDEX without naming a type, and MySQL's InnoDB engine stores its indexes as B-trees too.

• The tree is short and wide. Each node fills a block of storage, called a page, and holds hundreds of keys, so each node can point to hundreds of children.
• The leaves hold the sorted keys, each with a pointer to its row (or, in some designs, the row itself). The leaves are linked in order, so a range like "all emails starting with s" is a short walk along them.
• The tree stays balanced. When a page fills up, it splits in two and the parent gains a key, so every leaf stays the same distance from the root.

                    [ g | n | t ]                      root
          /        |          |          \
   [ a  c  e ]  [ h  k  m ]  [ p  r  s ]  [ u  w  y ]    leaves, linked in order
        |
    pointer to the row for 'c...'

Because each node branches so widely, the tree is only a few levels deep. With 500 keys per node, three levels cover 500³ = 125 million entries and four levels cover 62.5 billion. Finding any row means reading three or four pages, and the top levels are usually already in memory.

What happens when you run a query

1. Parse: the database checks the SQL and works out which tables and columns it uses.
2. Plan: the query planner (or optimiser) looks at the available indexes and its statistics about the data, estimates the cost of each way to run the query, and picks the cheapest.
3. Search the index: starting at the root, it compares the search value with the keys in each node and follows the right pointer down to a leaf.
4. Fetch the rows: it follows each matching entry's pointer to the table to read the rest of the row, unless the index already holds every column the query needs.
5. Return the result, already in index order if the query sorts by the indexed column.

The planner won't always use an index. If a query matches a large share of the table, reading the table straight through can be faster than jumping back and forth through an index, so the planner chooses a scan. You can see its choice by putting EXPLAIN in front of a query, which shows the plan instead of running it. The SQLite documentation has a clear walk-through of how a planner uses indexes.

Clustered and secondary indexes

Databases differ in where the rows themselves live.

• Clustered index: the table's rows are stored inside the index, in key order. In MySQL's InnoDB, every table has one, and it is normally the primary key. A table can only have one, because rows can only be stored in one order.
• Secondary index: any other index. In InnoDB, each secondary index entry stores the row's primary key, and the database uses that to look the row up in the clustered index. That is why MySQL's documentation advises keeping primary keys short: every secondary index carries a copy.
• Heap tables: PostgreSQL stores rows in no particular order, in a structure called a heap, and every index points into it.

Indexes the database makes for you

Declaring a primary key or a UNIQUE constraint makes the database create a unique index automatically, because checking that no value repeats needs one. Foreign keys vary: MySQL's InnoDB insists on an index on foreign key columns, but PostgreSQL doesn't create one, so joins on an unindexed foreign key can be slow there until you add it.

Creating and using indexes

-- An index on one column
CREATE INDEX idx_users_email ON users (email);

-- A composite index on two columns, in this order
CREATE INDEX idx_people_name ON people (last_name, first_name);

-- See how the database will run a query
EXPLAIN SELECT * FROM users WHERE email = 'sam@example.com';

Composite indexes and the leftmost prefix

A composite index on (last_name, first_name) is sorted by last name, and by first name within each last name, like a phone book. It helps queries on last_name alone, and on last_name with first_name. It doesn't help a query on first_name alone, just as a phone book can't find everyone called Sam. MySQL calls this using the leftmost prefix of the index. So put the column you filter on most often first.

Covering indexes

If an index contains every column a query asks for, the database can answer from the index alone and skip the table. PostgreSQL calls this an index-only scan. For a query that only needs last_name and first_name, the composite index above is a covering index.

Other kinds of index

The cost of indexes

• Slower writes: every insert, update or delete must also update each index on the table. A table with ten indexes does eleven writes for every new row.
• Extra storage: each index is a copy of its columns plus pointers, and can grow as large as the table.
• Maintenance: page splits and deletions leave indexes partly empty over time, so databases occasionally rebuild or tidy them.

So don't index every column. Index the columns you search, join and sort on most, check with EXPLAIN that the index is used, and drop indexes nothing uses. Our Databases course covers the tables, keys and joins that indexes speed up, and the guide to SQL explains the queries themselves.

Common mistakes

• Indexing everything. Every index slows down writes and takes space. Index for the queries you actually run.
• Getting composite index order wrong. (a, b) helps queries on a, or a and b, but not on b alone.
• Wrapping the column in a function. WHERE LOWER(email) = '...' can't use a plain index on email. Use an index on the expression, or store the value already lower-cased.
• Leading wildcards. LIKE '%son' can't use a B-tree, because the start of the value is unknown. LIKE 'son%' can.
• Forgetting foreign keys in PostgreSQL. They aren't indexed automatically, so joins on them can be slow.
• Assuming the index is used. Check with EXPLAIN: the planner may choose a scan.

Read next

Computer Science · DatabasesWhat is a database? Types, software and examplesWhat a database is, how tables, records and fields work, what database software (a DBMS) does, the main types of database and a first SQL query.