Database Indexes

Why indexes matter

Finding one customer by email in a table of 10 million rows without an index means checking all 10 million. With a B-tree index on email, the database walks a tree three or four levels deep and lands on the row. It is the same reason a book has an index at the back.

• 10,000,000rows checked by a full scan
• ~4tree levels walked with a B-tree index (with hundreds of keys per page)

CREATE INDEX idx_users_email ON users (email);

EXPLAIN SELECT id, name FROM users WHERE email = 'priya@example.com';
-- Look for an index scan on idx_users_email, not a sequential (full) scan.

B-trees

A B-tree keeps keys sorted in fixed-size pages (often 8 or 16 KB). Each inner page holds hundreds of keys pointing to child pages, so the tree is very wide and very shallow. A lookup reads one page per level; a range query (WHERE created_at BETWEEN …) finds the start and then walks along the leaf pages in order.

LSM trees

Databases built for heavy writes (Cassandra, RocksDB, and the storage engines inside many others) often use a log-structured merge tree. Writes go to an in-memory sorted table and an append-only log; when the memory table fills, it is flushed to disk as an immutable sorted file. Background compaction merges files and drops old versions.

Composite and covering indexes

A composite index sorts by several columns, like a phone book sorted by last name, then first name. It helps queries that use its columns from the left.

CREATE INDEX idx_orders_customer_date ON orders (customer_id, created_at);

-- Uses the index: filters on the first column
SELECT * FROM orders WHERE customer_id = 7;

-- Uses the index fully: first column equal, second column range, already sorted
SELECT * FROM orders WHERE customer_id = 7 AND created_at > '2026-01-01' ORDER BY created_at;

-- Cannot seek with it: skips the first column
SELECT * FROM orders WHERE created_at > '2026-01-01';

A covering index contains every column the query needs, so the database answers from the index alone without visiting the table. Some databases let you add extra columns for this (INCLUDE in PostgreSQL and SQL Server).

When an index hurts

• Writes get slower: every insert, update and delete must also update every index on the table.
• Storage grows: indexes can be as large as the table.
• Low selectivity: an index on a column with two values (is_active) rarely helps; reading half the table through an index is slower than a scan.
• Functions hide the column: WHERE LOWER(email) = … cannot use a plain index on email (use an expression index, or store it normalised).
• Leading wildcards: LIKE '%gmail.com' cannot use a B-tree; consider a search engine or a reversed column.

Common mistakes

• Adding an index on every column "just in case", slowing every write.
• Building a composite index in the wrong column order for the queries that use it.
• Wrapping indexed columns in functions or casts in WHERE clauses.
• Guessing instead of reading the query plan.

Interview questions

Try answering out loud before you open each one.

Check yourself

Related topics

• SQL TuningDatabases
• SQL vs NoSQL: How to ChooseDatabases

Further reading

• Use The Index, Luke: SQL indexing and tuning Markus Winand
• PostgreSQL documentation: Indexes PostgreSQL