Database Indexes (B-tree).

🐛The symptom

Your users table has 2M rows. This ran in 3ms last month:

SELECT * FROM users WHERE email = 'a@b.com';

Today it takes 900ms. Nothing in the query changed. What happened?

🔎Reasoning through it

Run EXPLAIN (Postgres) or EXPLAIN in MySQL:

EXPLAIN SELECT * FROM users WHERE email = 'a@b.com';
-> Seq Scan on users  (cost=0.00..48000 rows=1)

"Seq Scan" = the DB is reading all 2M rows one by one to find one match. The index on email was never created (or got dropped in a migration). Add it:

CREATE INDEX idx_users_email ON users(email);

Re-run EXPLAIN -> "Index Scan". Back to ~1ms.

💡The concept: what an index actually IS

An index is a separate, sorted data structure (usually a B-tree) that maps column values -> row locations. Instead of scanning 2M rows, the DB does binary search: ~21 steps for 2M rows (log2). That's the difference between 900ms and 1ms.

Mental model: a book index. To find "photosynthesis" you don't read every page — you jump to the P section. The tradeoff: the index takes disk space and must be updated on every INSERT/UPDATE/DELETE. Indexes make reads fast and writes slightly slower.

⚠️The gotchas that trip up intermediates

1. Indexes only help if the query can USE them. This kills your index:

WHERE lower(email) = 'a@b.com'   -- function on the column = Seq Scan

Fix: index the expression -> CREATE INDEX ... ON users(lower(email));

2. Leading-column rule for composite indexes. An index on (last_name, first_name) helps:

WHERE last_name = 'Ng'
WHERE last_name = 'Ng' AND first_name = 'A'

…but NOT:

WHERE first_name = 'A'   -- can't skip the leading column

Think of a phone book sorted by last then first name — useless if you only know the first name.

3. LIKE with a leading wildcard can't use a normal B-tree:

WHERE email LIKE '%@b.com'   -- Seq Scan
WHERE email LIKE 'a@%'       -- Index Scan (prefix is fixed)

4. More indexes ≠ better. Each one slows writes and eats space. Index the columns you actually filter/join/sort on — not every column "just in case".

🎯Your exercise

Take a slow query in any project you have. Run EXPLAIN (or EXPLAIN ANALYZE) in front of it. Find one "Seq Scan" on a big table, add the right index, and re-run EXPLAIN. Reply with the before/after plan — bonus if you spot a query that CAN'T use its index because of gotcha #1 or #2.