Indexes: how a B-tree makes lookups fast

Step 1 Understand it

Why you need it. Without an index, WHERE order_date = '2024-02-12' must read every row and check it: a full table scan. On 100 million rows that is slow, and it gets slower as the table grows. An index turns it into a few quick steps.

Watch it happen

Picture it

flowchart TD
  R["root page<br/>dates before 2024-02-01 · from 2024-02-01"] --> B1["branch<br/>Jan dates"]
  R --> B2["branch<br/>Feb and Mar dates"]
  B2 --> L1["leaf: 2024-02-02 → order 105"]
  B2 --> L2["leaf: 2024-02-12 → order 106"]
  B2 --> L3["leaf: 2024-02-20 → order 107"]

The idea

A B-tree index keeps the column's values in sorted order, in a shallow tree: a root page points to branch pages, which point to leaf pages holding each value and the row it belongs to. To find a value, the database walks from the root down — about 3 or 4 steps even for millions of rows — instead of reading everything. The primary key is indexed automatically. Indexes speed up WHERE, JOIN … ON, ORDER BY and MIN/MAX on the indexed column. The cost: every INSERT, UPDATE and DELETE must also update every index, and indexes take space.

The shape of it

CREATE INDEX index_name ON table_name (column);
CREATE UNIQUE INDEX index_name ON table_name (column);
DROP INDEX index_name;

Words in lower case are the parts you fill in.

How it works, step by step

1. Without an index on order_date, the plan says SCAN orders: every row is read.
2. CREATE INDEX idx_orders_date ON orders(order_date) builds a sorted list of dates, each pointing to its row.
3. Now the plan says SEARCH orders USING INDEX idx_orders_date (order_date=?): the database jumps to the date.
4. A lookup by the primary key uses the table's own key: SEARCH … USING INTEGER PRIMARY KEY.
5. For 10 rows the difference is invisible; for 100 million it is the difference between a full read and a handful of page reads.

Analogy

The index at the back of a textbook. To find "photosynthesis" you don't read every page; you look it up alphabetically and jump to page 214. A full table scan is reading the book cover to cover.

Where the analogy breaks

A book index never changes once printed. A database index must be updated on every write — so a table with ten indexes is slow to write to. Index what you search by, not everything.

Worked examples

EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE order_date = '2024-02-12';

CREATE INDEX idx_orders_date ON orders(order_date);
EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE order_date = '2024-02-12';

EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE order_id = 105;

Must-know points

• An index is a sorted structure (usually a B-tree) pointing back to the rows.
• It helps WHERE, JOIN … ON, ORDER BY and GROUP BY on the indexed columns.
• Primary keys and UNIQUE constraints get an index automatically; foreign keys usually don't — index them yourself.
• Every index slows down writes and uses space. Index the columns you filter and join on.
• An index helps most when it narrows the search to a small share of the rows (high selectivity).
• B-trees versus LSM trees, and indexing at scale, are in the System Design tab, Phase 3.

Common mistakes

• Indexing every column "just in case", which slows every write.
• Forgetting to index foreign keys, so joins and deletes on the parent table are slow.
• Indexing a column with only a few values (like status) and expecting it to help a query that matches half the table.

In other databases

• PostgreSQL also has hash, GIN (for arrays, JSON and full-text) and BRIN (for huge, naturally ordered tables) indexes. MySQL InnoDB stores the table itself in primary-key order (a clustered index).

Step 2 Go further (free, optional)

Optional. The notes above are written to be enough on their own. These free resources give a second explanation and more practice.

• Watch

  How database indexes work (video)

  YouTube search, free

• Read

  Use The Index, Luke — a guide to database performance for developers

  Markus Winand, free

• Read

  W3Schools — SQL CREATE INDEX

  short page with a try-it editor, free

Step 3 Practise

Try each one yourself first: out loud, or written and run in the practice box below, which saves every query you run. Then open the answer and compare.

1. ExplainSay what it does and when to use it, in plain words, with no notes.

   Explain an index using the textbook analogy, and say what it costs.

   Show answer

   An index is like the index at the back of a textbook. To find "photosynthesis" you don't read every page; you look the word up in the sorted list and jump to page 214. Without an index, the database has to read the whole table (a full scan), like reading the book cover to cover. With one, it searches a sorted copy of the column (a B-tree) and follows a pointer straight to the matching rows.

   What it costs:
   • Slower writes: every INSERT, DELETE, and UPDATE of the indexed column must also update the index. A book's index is printed once; a database's is kept up to date all the time.
   • Space: the index is a second copy of the column, on disk and in memory.
   So you index the columns your important queries filter, join or sort on, not every column.

2. Writefrom a blank page, then run it

   Create an index that would help SELECT * FROM employees WHERE dept_id = 1;, and check the plan before and after.

   Show answer

   Before, the plan is SCAN employees: every row is read. Create an index on the filtered column, run the same EXPLAIN QUERY PLAN, and it becomes a SEARCH using the new index.

   (With 8 rows a scan is just as fast; the plan matters when the table has millions.)

   sqlCopy

   CREATE INDEX idx_employees_dept ON employees(dept_id);
   EXPLAIN QUERY PLAN SELECT * FROM employees WHERE dept_id = 1;

   Try it

   1 row

   id	parent	notused	detail
   3	0	61	SEARCH employees USING INDEX idx_employees_dept (dept_id=?)

3. Predictsay it before you run it

   Will SELECT * FROM customers WHERE customer_id = 3 use an index without you creating one? Why?

   Show answer

   Yes. customer_id is the primary key, and a primary key is always indexed: the database needs that to check uniqueness on every insert. In SQLite an INTEGER PRIMARY KEY is the row's own id (the rowid), so the plan searches straight to it.

   sqlCopy

   EXPLAIN QUERY PLAN SELECT * FROM customers WHERE customer_id = 3;

   Try it

   1 row

   id	parent	notused	detail
   2	0	33	SEARCH customers USING INTEGER PRIMARY KEY (rowid=?)

4. Edge casesSay what happens with NULLs, ties, duplicates or no rows at all, and fix it.

   A status column has only four values and 50% of rows are 'delivered'. Would an index on status help WHERE status = 'delivered'? What about WHERE status = 'pending'?

   Show answer

   WHERE status = 'delivered': probably not. Half the table matches, so the index would find half a million row pointers (in a million-row table), and fetching each row one by one, jumping around the disk, is slower than simply reading the whole table in order. A good optimiser, with statistics, ignores the index and scans.

   WHERE status = 'pending': yes, if pending orders are rare (say 1%). The index jumps straight to the few matching rows. This is the case where an index on a column with few values can pay off.

   The usual answer for "a rare value of a common column" is a partial index, which only holds the rows you search for: CREATE INDEX idx_orders_pending ON orders(order_date) WHERE status = 'pending';. It is tiny and cheap to maintain.

   (SQLite only knows how values are spread after you run ANALYZE. Without it, it will happily use an index on status for 'delivered' too.)

Step 4 Interview-ready, then prove it

Your interview answer

About 20 to 40 seconds, said out loud.

An index is a separate sorted structure, typically a B-tree, mapping column values to row locations, so the database can find matching rows in logarithmic time instead of scanning the table. I index columns used in selective WHERE filters, join keys — especially foreign keys — and ORDER BY, and I keep in mind the trade-off: every index adds work to inserts, updates and deletes, and uses storage.

Follow-up questions

Tick each check when you can do it without notes