What Is a Database Index? How It Works and When to Use One

7 min read

A database index is an auxiliary data structure that lets the database engine find rows without scanning the entire table. It trades extra storage and slightly slower writes for dramatically faster lookups, sorts, and joins.

The core idea: avoid the full table scan

Without an index, answering a query like SELECT * FROM users WHERE email = 'a@b.com' forces the engine to read every row in the table and check the condition. This is a full table scan, and its cost grows linearly with table size. On a table of ten million rows, that means reading ten million rows to find one.

An index is a separate structure that stores the indexed column values in a searchable order, alongside a pointer back to the full row. The engine searches the index instead of the table, jumps straight to the matching pointer, then fetches the row. The analogy that holds up well: an index at the back of a book lets you find a topic without reading every page.

How a B-tree index works

The default index type in PostgreSQL, MySQL (InnoDB), SQL Server, Oracle, and SQLite is the B-tree (more precisely, a B+ tree in most implementations). It is a balanced tree of sorted keys. Searching walks from the root down through internal nodes to a leaf, and because the tree stays balanced, any lookup touches roughly the same small number of nodes regardless of where the value sits.

The practical result is that lookups, range scans, and sorted output all become cheap. A B-tree supports more than equality:

  • Equality: WHERE id = 42
  • Range: WHERE created_at > '2026-01-01'
  • Prefix matching: WHERE name LIKE 'Sm%' (a leading wildcard like '%mith' cannot use the index)
  • Ordering: ORDER BY created_at can read the index in order and skip a separate sort step

Because leaf nodes are stored in sorted order, the B-tree also satisfies ORDER BY and GROUP BY on the indexed columns without an extra sort, and it enforces uniqueness for primary keys and unique constraints.

Hash indexes and other types

A hash index stores a hash of the column value and supports only equality comparisons, not ranges or ordering. Conceptually it works like a hash function mapping keys into buckets. Engines also offer specialized types: GIN and GiST in PostgreSQL for full-text, JSON, and geometric data; bitmap indexes in some systems for low-cardinality columns; and spatial indexes for geographic queries. B-tree is the right default for the large majority of cases.

Clustered vs. non-clustered indexes

A clustered index determines the physical order in which rows are stored on disk, so the table itself is the index leaf. A table can have only one clustered index. In SQL Server and MySQL's InnoDB, the primary key is the clustered index by default. A non-clustered (secondary) index is a separate structure that points back to the row's location.

This matters for performance: a lookup on a non-clustered index that needs columns not stored in the index must do an extra fetch to retrieve the full row. PostgreSQL behaves differently — all its indexes are secondary structures pointing into the heap, and it does not maintain a clustered table order automatically.

Composite indexes and the leftmost-prefix rule

A composite (multi-column) index covers several columns in a defined order, for example (last_name, first_name). Column order is significant. A B-tree on (last_name, first_name) efficiently serves queries filtering on last_name, or on last_name and first_name together, but it cannot efficiently serve a query that filters only on first_name. This is the leftmost-prefix rule: an index helps only when the query uses a contiguous prefix of its columns starting from the left.

A related optimization is the covering index: if an index contains every column a query reads, the engine answers entirely from the index and never touches the table. This is sometimes called an index-only scan.

The cost: writes, storage, and maintenance

Indexes are not free. Every index must be kept consistent with the table, so each INSERT, UPDATE to an indexed column, and DELETE has to update the index too. More indexes mean slower writes and more disk and memory consumed. A table with a dozen redundant indexes can spend more effort maintaining them than it saves on reads.

The order in which keys are inserted also matters. Monotonically increasing keys (like auto-increment integers or time-ordered identifiers) append to one end of the B-tree and pack tightly. Random keys scatter inserts across the tree, causing page splits and fragmentation — one reason time-ordered identifiers are often preferred over fully random ones, as covered in UUIDv4 vs. UUIDv7 and UUID vs. ULID vs. CUID.

When to add an index (and when not to)

Good candidates for indexing:

  • Columns frequently used in WHERE clauses, especially with high selectivity (many distinct values, like an email or user ID)
  • Foreign-key columns used in JOIN conditions
  • Columns used in ORDER BY or GROUP BY on large result sets

Cases where an index often does not help:

  • Small tables, where a full scan is already fast
  • Low-cardinality columns like a boolean flag, where the index points at a large fraction of rows anyway
  • Write-heavy tables where the maintenance cost outweighs read gains
  • Queries that wrap the column in a function, such as WHERE LOWER(email) = '...', which prevents a plain column index from being used unless a matching expression index exists

The reliable way to decide is to measure. Run EXPLAIN (or EXPLAIN ANALYZE in PostgreSQL and MySQL) to see whether the planner chooses an index scan or a sequential scan, and how the estimated cost changes. Don't guess at slow queries — read the plan. Tools like a SQL formatter help you read complex statements before profiling them, and a SQL to ORM generator is handy when index definitions live in migration files. To understand why parameterized queries matter alongside indexing, the SQL injection demo shows what unescaped input does to a query.

Key takeaways

An index is a sorted, searchable copy of one or more columns that turns linear scans into near-instant lookups. B-trees are the versatile default; hash indexes serve equality only; clustered indexes set physical row order. Composite indexes obey the leftmost-prefix rule, and every index costs write throughput and storage. Add indexes deliberately, confirm them with the query planner, and remove the ones that earn nothing.

Frequently Asked Questions

It makes matching reads faster but slows writes, because every insert, update, and delete must also maintain the index. Indexes help most on large tables queried by high-cardinality columns; on small or write-heavy tables they can cost more than they save.

A clustered index defines the physical order of rows on disk, so the table is stored as the index, and you can have only one per table. A non-clustered index is a separate structure that points back to the row, and a table can have many of them.

Common reasons include wrapping the column in a function (such as LOWER(email)), a leading wildcard in a LIKE pattern, low column selectivity, or violating the leftmost-prefix rule of a composite index. Run EXPLAIN to see the planner's actual choice.

There is no fixed number; add only indexes that real queries use. Each one adds write overhead and storage, so periodically drop unused or redundant indexes rather than indexing every column defensively.

Most relational databases, including PostgreSQL, MySQL, SQL Server, Oracle, and SQLite, create a B-tree index by default. B-trees support equality, range, prefix, and ordered queries, which covers the large majority of use cases.

Related Guides