What is an index and how does it speed up queries?

Q: What is an index and how does it speed up queries?

**Target Audience:** Beginners who have written SELECT queries but never looked at how the database finds rows; anyone preparing for the first indexing question in an interview. **Difficulty:** Medium **Engines:** SQLite 3.45.0 through sql.js 1.10.2 (the runnable examples) and PostgreSQL 16.15 (plans on 100,000 rows, sizes, timings). The ideas hold for MySQL and SQL Server too; their specifics are not covered here. > **How to read this doc:** Every idea is in plain language first, then a `📌 Interview term:` callout gives the precise word an interviewer expects. All plans, sizes and timings are from real runs; the **Verified** section quotes each example output in full. ## 1. Why This Even Matters — A Story First You have a 900-page cookbook and want the recipe for "paneer tikka". Without an index you start at page 1 and read every page until you find it, and then keep going, because there might be a second paneer tikka recipe. With the index at the back, you flip to "P", run your f

The problem

Question presented to candidate: "What is a database index, and how does it actually make a query faster? Walk me through what the database does for WHERE email = ... with and without one, and tell me what an index costs."

What a strong answer should cover:

An index is a separate, sorted data structure (by default a B-tree) that maps column values to the location of the matching rows, so the engine can jump to them instead of reading the whole table
Without an index the engine does a full table scan (SQLite SCAN, PostgreSQL Seq Scan), reading every row; with one it does a search (SEARCH ... USING INDEX, Index Scan) in a few page reads, O(log n)
Indexes also serve ORDER BY, range conditions, joins and MIN/MAX because the entries are kept in order
Costs: extra disk space, slower INSERT/UPDATE/DELETE (every index is maintained on every write), and memory pressure
When an index is not used: a function or expression on the column, a leading-wildcard LIKE, low selectivity (most of the table matches), or a missing leading column of a composite index; prove it with EXPLAIN

Code / implementation expected: Optional — CREATE INDEX and an EXPLAIN / EXPLAIN QUERY PLAN before and after.

Schema used by the examples:

index

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners who have written SELECT queries but never looked at how the database finds rows; anyone preparing for the first indexing question in an interview. Difficulty: Medium Engines: SQLite 3.45.0 through sql.js 1.10.2 (the runnable examples) and PostgreSQL 16.15 (plans on 100,000 rows, sizes, timings). The ideas hold for MySQL and SQL Server too; their specifics are not covered here.

How to read this doc: Every idea is in plain language first, then a 📌 Interview term: callout gives the precise word an interviewer expects. All plans, sizes and timings are from real runs; the Verified section quotes each example output in full.

1. Why This Even Matters — A Story First

You have a 900-page cookbook and want the recipe for "paneer tikka". Without an index you start at page 1 and read every page until you find it, and then keep going, because

The solution is hidden so you can try first

13 min read · 12 sections

Run the code

Edit the query and run it against the tables for this question.

SQLSQLite: SCAN without an index, SEARCH USING INDEX after CREATE INDEX

SQLWhen the index cannot help: a function on the column or a leading wildcard, and the expression-index fix

PostgreSQL, 100,000 rows, no index: Seq Scan reads and discards 99,999 rows

CREATE TABLE big_users AS
SELECT g AS id,
       'user' || g || '@example.com' AS email,
       (ARRAY['US','IN','DE','PT','JP'])[1 + g % 5] AS country
FROM generate_series(1, 100000) AS g;
ANALYZE big_users;

EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
SELECT id, country FROM big_users WHERE email = 'user4242@example.com';

PostgreSQL, same table with an index: Index Scan goes straight to the one row

CREATE TABLE big_users AS
SELECT g AS id,
       'user' || g || '@example.com' AS email,
       (ARRAY['US','IN','DE','PT','JP'])[1 + g % 5] AS country
FROM generate_series(1, 100000) AS g;
CREATE INDEX big_users_email_idx ON big_users (email);
ANALYZE big_users;

EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF)
SELECT id, country FROM big_users WHERE email = 'user4242@example.com';

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.