Database Indexes

Two hundred million users, one login query#

SELECT id, password_hash
FROM users
WHERE email = ?;

Inspecting the whole table for every login is unacceptable. An index maintains extra data that gives this query a faster path to matching rows.

B-tree intuition: searchable order#

A B-tree-style index keeps keys in a searchable order, supporting equality, range conditions, and ordered traversal. Interview depth means explaining why order helps - not implementing page splits or calculating exact disk operations.

A composite index serves a query shape#

CREATE INDEX messages_conversation_created
ON messages(conversation_id, created_at);

SELECT * FROM messages
WHERE conversation_id = ?
ORDER BY created_at DESC
LIMIT 50;

The leading conversation key narrows the data; creation time provides order within that conversation. (created_at, conversation_id) is not equivalent for every query. Exact prefix and ordering rules depend on the database and index type.

Selectivity and specialized paths#

An email is usually selective. country = 'US' may match most rows in a mostly-US dataset, so scanning another access path may cost less than using that index.