Database Indexing

An index is a separate, sorted structure the database keeps next to a table so it can find rows without reading all of them. It is the single biggest lever you have on read performance. It also has a cost, so you need to know which kind of index to create, and for which queries.

Why indexes exist#

Picture a users table with 10 million rows and this query:

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

Without an index, the database reads every row and checks the email. That is a full table scan, $O(n)$:

With an index on email, the database searches a sorted structure and jumps straight to the right row, $O(\log n)$.

It works like the index at the back of a textbook. To find "deadlock" you don't flip every page. You look up "deadlock → page 142" and go there.

Here is a small table, stored in insertion order:

And a separate, sorted index on email:

The index stores the indexed column's values in sorted order, each with a pointer back to its row. In practice the "sorted list" is a B-tree, explained in Read Heavy Indexing.

Types of index#

Primary vs secondary#

• Primary index: built on the primary key. Declaring PRIMARY KEY creates it for you. It is unique.
• Secondary index: any other index you create. A table can have many, unique or not.

CREATE TABLE users (
  id    INT PRIMARY KEY,  -- primary index, created automatically
  email VARCHAR(255),
  name  VARCHAR(255)
);

CREATE INDEX idx_users_email ON users (email);  -- secondary
CREATE INDEX idx_users_name  ON users (name);   -- secondary

You get the primary index for free. Every other index is a decision based on your query patterns.

Clustered vs non-clustered#

This is the most important distinction to understand.

A clustered index stores the table's rows in the order of the index key. The table is the index. A table can only have one, because rows can only be physically ordered one way.

Here is a table clustered on id:

• Looking up id = 3: the row is right there.
• WHERE id BETWEEN 2 AND 4: the rows are next to each other, so it's one sequential read.

A non-clustered index is a separate structure that points back to the rows, like the textbook index separate from the pages.

A non-clustered index on email, sitting next to the same table (still clustered on id), looks like this:

Looking up alex@... takes two steps: find it in the index, then fetch the row from the table. That second step is called a bookmark lookup or table lookup.

Databases differ here. MySQL's InnoDB always clusters the table on its primary key. SQL Server lets you choose the clustered index. PostgreSQL stores tables as an unordered heap, so all of its indexes are effectively non-clustered (its CLUSTER command reorders a table once, but doesn't keep it ordered).

Composite (multi-column)#

An index on several columns, sorted by the first column, then the second, and so on. Column order matters.

CREATE INDEX idx_name_age ON users (last_name, first_name, age);

The index entries are sorted like this:

The leftmost prefix rule: the index helps only when the query filters on a leading prefix of its columns.

A phone book sorted by last name, then first name, makes "Adams" and "Adams, Bob" easy to find. Finding every "Bob" means reading the whole book.

Covering#

If an index contains every column a query needs, the database answers from the index alone and never touches the table.

Take this query:

SELECT email, name FROM users WHERE email = 'alex@example.com';

CREATE INDEX idx_users_email_name ON users (email, name);

The query is now "covered" by the index.

Summary#

Here are all six kinds in one place:

Which index for which query#

Start from the query, then pick the index that serves it:

The composite and covering rows come from queries like these:

-- Composite (customer_id, created_at)
WHERE customer_id = 123 AND created_at > '2025-01-01'

-- Composite (category, price)
WHERE category = 'electronics' AND price BETWEEN 100 AND 500

-- Covering (status, email, name)
SELECT email, name FROM users WHERE status = 'online'

Why "equality first, range last"? With (customer_id, created_at), all of one customer's rows are together and sorted by date, so the range is one contiguous slice. With (created_at, customer_id), the date range spans every customer and the database has to filter through all of them.

Why only one clustered index? If orders are clustered on created_at for time-range queries, you still need a non-clustered index on order_id for direct lookups.

Covering indexes are worth their extra storage for queries that run thousands of times a second and return only a few columns.

The same ideas in DynamoDB#

DynamoDB has no CREATE INDEX in the SQL sense, but the same concepts map across:

Key takeaways#

• An index is a separate sorted structure (usually a B-tree) that turns $O(n)$ scans into $O(\log n)$ lookups.
• A clustered index stores rows in key order (one per table, great for ranges). Non-clustered indexes point back to rows (many per table, one extra hop).
• Composite indexes follow the leftmost prefix rule. Put equality columns first and the range column last.
• A covering index includes every column a query needs, so the table is never touched.
• Index for your actual query patterns. Every index has a write cost (see Indexing Trade-offs).