Database indexes

Why a database finds one customer among millions in milliseconds

A database index is a separate, sorted copy of one or more columns, where each entry points to the row it came from. Without one, the query WHERE email = 'ana@x.com' has to do a full table scan: read every row and check it.

With an index on email, the emails sit sorted in a B-tree, each paired with a row ID, the row's address in the table. The database walks the tree to 'ana@x.com', reads its row ID and fetches just that row.

Like the index at the back of a book, it gives you a page number instead of making you read every page. The price is extra disk space, and every write has to update the index too.

Database indexes

Typing your email into a login box finds your account among millions

When you log in, the site runs something like SELECT * FROM users WHERE email = ?. On a table of 100 million users, a full scan would read every row for every login; an index on email turns it into a few page reads.

PostgreSQL automatically builds a B-tree index for every PRIMARY KEY and UNIQUE constraint. So a UNIQUE email column is fast to search from day one, and new sign-ups are quickly checked for reused emails.

Database indexes

A sorted copy of one column points straight to the right rows

It works because the index is sorted and the table isn't. 'ana@x.com' could sit anywhere among the rows, but each B-tree level cuts the search by a factor of b, like binary search with hundreds of branches.

Sorting also makes ranges cheap: for price BETWEEN 10 AND 20, find 10, then read neighbouring leaves until passing 20. An index on (last_name, first_name) helps queries on last_name, but not on first_name alone.

The cost is on writes: every INSERT, UPDATE or DELETE must also update each index. Indexes help little when most rows match, like is_active true for 95% of rows; one straight scan beats jumping row by row.