What is an Index

An index is a data structure that lets a database find rows without scanning the entire table. Without an index, a query like SELECT * FROM users WHERE email = 'x' must read every row — a full table scan. With an index on the email column, the database jumps directly to the matching row. The difference is O(n) versus O(log n).

How it works

The most common index type is a B-tree (or B+ tree). A B-tree is a balanced, sorted tree where each node is a page. The root node points to intermediate nodes, which point to leaf nodes containing the actual indexed values and pointers back to the table rows. A lookup traverses from root to leaf — typically 3-4 levels deep, meaning 3-4 page reads.

Hash indexes map keys to row locations through a hash function. They are O(1) for exact-match lookups but cannot answer range queries (WHERE age > 30). PostgreSQL supports hash indexes; InnoDB does not.

Composite indexes cover multiple columns. An index on (last_name, first_name) can efficiently answer queries filtering on last_name alone or on both columns, but not on first_name alone. Column order matters.

Every index has a cost. When you INSERT or UPDATE a row, the database must also update every index on that table. This means writes are slower. Indexes also consume disk space — sometimes more than the table itself. A table with ten indexes updates ten separate data structures on every write.

The query planner decides whether to use an index or scan the table. If a query returns most of the table's rows, a full scan is actually faster than an index lookup because sequential I/O beats random I/O.

Why it matters

Indexes are the single most impactful tool for database performance. A missing index turns a millisecond query into a seconds-long scan. Too many indexes slow down writes and waste storage. Learning when to add an index — and when not to — is the core skill of database tuning.

See How Indexes Work for the full B-tree walkthrough and indexing strategies.