Database Indexing Explained

Imagine looking up "replication" in a 600-page technical book. You could read every page from the start, or you could turn to the index at the back, find the entry, and go straight to page 412. Database indexing works on exactly the same idea. An index is a separate, sorted structure that tells the database where to find rows matching a value, so it does not have to read the whole table. Used well, indexes turn queries that take seconds into ones that take milliseconds. Used carelessly, they waste memory and slow down every write.

What happens without an index

Suppose you have a customers table with two million rows and you run:

SELECT id, name FROM customers WHERE email = 'priya@example.com';

If there is no index on email, the database performs a full table scan: it reads every row and checks the email column. On a small table that is fine. On two million rows it means reading a lot of data from disk or memory to return a single customer, and it gets worse as the table grows.

Add an index and the picture changes:

CREATE INDEX idx_customers_email ON customers (email);

Now the database looks up the value in the index, finds a pointer to the matching row, and fetches only that row.

How a B-tree index works

Most relational databases, including MySQL (InnoDB), PostgreSQL and SQL Server, use the B-tree (balanced tree) as their default index type. Think of it as a sorted, multi-level directory:

• The root page holds a few boundary values, such as "A–F go left, G–M go middle, N–Z go right".
• Each level below narrows the range further.
• The leaf pages at the bottom hold the actual indexed values in sorted order, with a reference to each row.

Because the tree stays balanced, finding any value takes only a few page reads, even for tables with hundreds of millions of rows. And because the leaves are sorted, a B-tree is also efficient for ranges (BETWEEN, >, <), prefix matches (LIKE 'pri%') and ORDER BY on the indexed column.

What a B-tree cannot help with is a leading wildcard such as LIKE '%@gmail.com'. The database cannot use sorted order when it does not know how the value starts. For that kind of search, full-text indexes or a dedicated search engine are better tools.

Types of indexes you will meet

Composite indexes and column order

A composite index is sorted by its first column, then by the second within each first value, and so on, like a phone book sorted by surname and then first name. This leads to the leftmost prefix rule: the index helps queries that filter on its first column, or its first and second, but not queries that only filter on the second.

CREATE INDEX idx_orders_cust_date ON orders (customer_id, order_date);

-- Uses the index
SELECT * FROM orders WHERE customer_id = 17;
SELECT * FROM orders WHERE customer_id = 17 AND order_date >= '2024-01-01';

-- Cannot use it efficiently
SELECT * FROM orders WHERE order_date >= '2024-01-01';

A good rule of thumb is to put columns tested with equality (=) first and the column used for a range or sort last.

Covering indexes

Normally the database finds a match in the index, then makes a second trip to the table to read the remaining columns. If the index already holds every column the query asks for, that second trip disappears. For example:

CREATE INDEX idx_orders_cust_date_total ON orders (customer_id, order_date, total);

SELECT order_date, total FROM orders WHERE customer_id = 17;

In MySQL's EXPLAIN output this shows up as Using index; PostgreSQL reports an Index Only Scan. PostgreSQL also offers INCLUDE to add non-searchable columns to an index purely for this purpose.

The cost of indexes

Indexes are not free. Every time a row is inserted, updated or deleted, each affected index must be updated too. Indexes also take disk space and compete for memory with your data. Signs you have too many:

• Several indexes that start with the same column, such as (customer_id) and (customer_id, order_date). The shorter one is usually redundant.
• Indexes that monitoring shows are never used.
• Write-heavy tables, such as event logs, where inserts slow noticeably as indexes are added.

Indexes on columns with very few distinct values, such as a boolean is_active flag where most rows are true, rarely help on their own. The database may decide a full scan is cheaper anyway.

Database indexing: how to decide what to index

1. Start from real queries. Use the slow query log or your database's statistics views to find queries that run often or slowly.
2. Read the execution plan. Run EXPLAIN (or EXPLAIN ANALYZE) and look for full scans on large tables and expensive sorts.
3. Index foreign keys. Columns used in joins, such as orders.customer_id, almost always deserve an index. PostgreSQL does not create these automatically.
4. Test with production-like data. An index that looks pointless on 1,000 test rows can be essential on 10 million.
5. Review periodically. Queries change as the product evolves; yesterday's essential index may now be dead weight.

The PostgreSQL indexes documentation and the MySQL reference manual both cover the details for their engines. If your application has outgrown guesswork, our database management service includes index reviews as part of performance tuning, and our web application development team designs indexes alongside the queries that need them.

Key takeaways

• Database indexing lets the database find rows without reading the whole table.
• B-tree indexes handle equality, ranges, prefix searches and sorting, but not leading wildcards.
• In composite indexes, column order decides which queries benefit.
• Every index slows writes and uses memory, so index based on real queries, not guesses.