What is a database index? How database indexes work and when to use them

A database index is a separate data structure — usually a balanced tree, most commonly a B-tree — that stores a sorted copy of the indexed columns together with a pointer to the actual row. When you look up a row by an indexed column, the database descends the tree in a handful of steps instead of reading every row of the table. The trade-off is real: every INSERT, UPDATE, and DELETE must also maintain every index on the table, so indexes cost write speed and disk space in exchange for faster reads. This guide walks through how indexes work, the clustered vs non-clustered distinction, and when an index is worth creating — and when it is not.

What happens without an index

Imagine a users table with one million rows and a query that fetches a single row by email:

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

Without an index on email, the database cannot know where the matching row is, so it must read the table from the first row to the last and compare email on every row until it finds a match. This is called a full table scan, and on a large table it means reading (potentially) a million rows. A full scan is correct but slow, and it becomes useless the moment the table grows.

An index changes this: it keeps the email values sorted in their own structure, with a pointer from each value back to the corresponding row. To satisfy the query, the database searches the sorted index, finds ada@example.com, follows the pointer, and reads only that one row. Instead of a million comparisons, the lookup takes roughly the depth of the tree — a few dozen steps even for huge tables.

How a B-tree index works

Most relational databases index with a B-tree — more precisely a B+ tree variant. A B-tree is a multi-way balanced tree: a root node points down to branch nodes, branch nodes point down to leaf nodes, and the leaf level holds the index keys in sorted order together with a pointer to each row. "Balanced" means every leaf sits at the same shallow distance from the root, so any value — common or rare — is found in the same small number of steps regardless of how many rows there are.

Because the leaves are sorted, a B-tree index accelerates more than exact equality lookups:

• Equality: WHERE email = 'x'
• Range: WHERE age BETWEEN 18 AND 25, WHERE price < 100
• Prefix search: WHERE name LIKE 'Ada%' (a leading wildcard, '%da', cannot use the index)
• Ordering: ORDER BY created_at
• Joins: matching rows between two tables on the indexed column

PostgreSQL's documentation notes that any data type that can be sorted into a well-defined linear order can be indexed by a B-tree — which is why it is the default index type and covers the vast majority of use cases.

Clustered vs non-clustered indexes

The single most important distinction in indexing is clustered vs non-clustered, and it comes down to where the data actually lives.

Clustered index. The leaf level of a clustered index is the table data — the rows are physically stored on disk in the order of the index keys. Clustered indexes are great for range queries and ordered reads, because once you find the start of a range, the rest of the matching rows are physically adjacent. But because the rows can be laid out in only one order, a table can have at most one clustered index. In MySQL's InnoDB engine the primary key is always the clustered index; SQL Server clusters the primary key by default.

Non-clustered index. A non-clustered index is a completely separate B-tree that stores the sorted key columns plus a pointer back to the row — either a physical row locator or, in clustered-table engines, the clustered key value. The underlying table rows stay in their own natural order, so a table can have many non-clustered indexes, each tuned to a different query pattern.

In practice a typical table has one clustered index (often the primary key) and several non-clustered indexes for the queries that matter most.

Composite and covering indexes

You are not limited to a single column. A composite index covers several columns in a fixed order, for example (last_name, first_name). Composite indexes obey the leftmost-prefix rule: a query can use the index when it filters on the first column, or the first and second, but not on the second column alone. So an index on (last_name, first_name) helps WHERE last_name = 'Lovelace' and WHERE last_name = 'Lovelace' AND first_name = 'Ada', but not WHERE first_name = 'Ada' on its own.

A covering index (in SQL Server, an index with included columns) holds every column the query needs inside the index itself, so the database can answer the query without ever going back to the table — a "covering" or index-only scan. This is the fastest possible read, at the cost of a wider index.

The trade-offs: writes, storage, and maintenance

Indexes are not free. Every index on a table must be updated on every write to that table, so:

• Write overhead. Each INSERT, UPDATE, and DELETE now has to maintain every index along with the table. A table with many indexes slows down writes and can slow down transactions.
• Storage. Each index is its own structure on disk. A wide or covering index can rival the table itself in size.
• Selectivity. An index only pays off when the query is selective — when a value matches a small fraction of rows. Indexing a column where most rows share the same value (like a boolean that is true 99% of the time) rarely helps, because the optimizer may decide that scanning the table is cheaper.
• Function calls. Wrapping the indexed column in a function, as in WHERE LOWER(email) = 'ada@example.com', usually prevents the index from being used unless a functional index exists for that expression.

The practical guideline is to index the columns that appear in your most important WHERE, JOIN, and ORDER BY clauses, keep the number of indexes modest, and drop indexes that queries never use.

How to verify an index is working

After creating an index, confirm the query planner actually uses it. In PostgreSQL and MySQL you prefix a query with EXPLAIN ANALYZE (or just EXPLAIN) and read the plan:

EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'ada@example.com';

The plan shows whether the engine chose an index scan or a sequential scan (table scan). If a query you expect to be fast is still doing a sequential scan, the index may not be selective enough, or the query may be written in a way the index cannot serve (for example, a leading wildcard or a function call on the column).

FAQ

What is the difference between a clustered and a non-clustered index?

A clustered index determines the physical order in which a table's rows are stored on disk — its leaf level is the data — and a table can have only one. A non-clustered index is a separate sorted structure that stores the key columns plus a pointer back to the row, and a table can have many of them. Clustered indexes suit range and ordered reads; non-clustered indexes support many different query patterns on the same table.

Why do database indexes slow down writes?

Every time a row is inserted, updated, or deleted, the database must also update every index that covers the affected columns. Indexes speed up reads by trading write cost and storage for that speed — the more indexes a table has, the more work each write has to do.

When should I not create an index?

Avoid an index when the column has low selectivity (most rows share the same value, so the query still matches most of the table), when the table is tiny and a full scan is already fast, or when the column is rarely used in WHERE, JOIN, or ORDER BY. Too many unused or low-value indexes add write overhead and consume storage without helping reads.

Why is my index not being used?

Common reasons the optimizer skips an index: the query is not selective enough (matching too large a fraction of rows), the column is wrapped in a function (WHERE LOWER(email) = ...), a LIKE pattern starts with a wildcard ('%ada'), or the query filters on a column that is not the leftmost column of a composite index. Running EXPLAIN shows whether the planner chose an index scan or a sequential scan.