Database indexes: how they work and when to create them

When a query that used to answer instantly starts taking seconds, the most common cause is a missing index. At the same time, people who discover indexes tend to create them everywhere, slowing down writes and wasting space. Understanding how they really work lets you put them where they are needed and only there.

The problem they solve

Without indexes, to find customers with a given surname the database has to read every row of the table and check it. This is called a full scan, or full table scan. On a thousand rows you will not notice; on ten million you will.

An index is a separate structure containing the values of one or more columns, sorted, each with a reference to the corresponding row. The classic analogy is the index at the back of a book: instead of leafing through every page to find a topic, you look up the entry in alphabetical order and go straight to the page it points to.

What a B-tree index looks like

The most common structure in relational databases is the B-tree, or a variant of it. It is a balanced tree in which:

• the root and intermediate nodes hold separator values indicating which branch to follow;
• the leaves hold the sorted values and the pointers to the rows;
• all leaves sit at the same depth.

Because each node holds many values, the tree is very wide and shallow. Even with millions of rows, a few levels, and therefore a few reads, are enough to reach the value you want. And since the leaves are sorted and linked together, the index is efficient for ranges too: «all orders between 1 and 15 March» is found by descending to the first value and walking the leaves to the last.

What an index speeds up

A B-tree index on a column helps with:

• equality: WHERE email = 'anna@example.com';
• ranges: WHERE order_date BETWEEN '2025-03-01' AND '2025-03-15';
• sorting: ORDER BY order_date, because the values are already in order;
• joins: the foreign key column used to join tables;
• prefix searches: WHERE surname LIKE 'Ros%'.

It does not help with searches that start with a wildcard, such as LIKE '%ossi', because alphabetical order starts at the beginning of the string. Different structures exist for these cases, such as full-text search indexes.

Composite indexes and column order

An index can contain several columns. In that case the order matters a great deal:

CREATE INDEX idx_orders_customer_date
  ON orders (customer_id, order_date);

This index is sorted first by customer and, within each customer, by date. Like a phone book sorted by surname and then by first name, it works for:

• WHERE customer_id = 42
• WHERE customer_id = 42 AND order_date >= '2025-01-01'
• WHERE customer_id = 42 ORDER BY order_date

But it is of little help for WHERE order_date >= '2025-01-01' on its own, just as a list sorted by surname does not help you find everyone called Maria. The practical rule is to put columns used for equality first and columns used for ranges or sorting after them.

The cost of indexes

Indexes are not free:

1. Slower writes. Every INSERT, UPDATE or DELETE must also update every index on the table.
2. Disk and memory space. An index can take up a significant fraction of the table itself, and it works best when it fits in memory.
3. Maintenance. Unused indexes still have to be updated and included in backups.

That is why a table receiving many writes and few reads should be indexed cautiously, while a table queried constantly and rarely updated can afford more indexes.

Selectivity: when an index does not help

An index is effective when it filters a small number of rows relative to the total. On an «active» column with only two values, where 95% of rows are true, fetching active records through the index is slower than reading the table. The database optimiser knows this and often ignores the index. Some databases instead allow partial indexes, which contain only the rows of interest, for example only those with active = false.

How to decide which indexes to create

A practical method:

1. start from real queries, not assumptions: slow query logs are the best source;
2. check the execution plan to see whether the query performs a full scan;
3. create the most targeted index possible and check the plan again;
4. periodically look for indexes that are never used, which many databases report in their statistics, and consider removing them.

Primary keys and UNIQUE constraints already create an index automatically. Foreign keys, in many databases, do not: indexing them is often the first useful step.

In short

• An index is a sorted copy of some columns that avoids reading the whole table.
• A B-tree is shallow and handles equality, ranges and sorting well.
• In composite indexes, column order determines which queries benefit.
• Every index slows writes and takes space: it must be justified by real queries.
• Foreign keys are often the first candidates for indexing.