Indexes
Think of a thick phone directory, sorted by surname. Finding "Sharma, Asha" takes you a few seconds: open near the middle, jump toward S, narrow down. Finding everyone who lives on MG Road takes all afternoon, because the book is not sorted by street. You would have to read every page.
A database index is that sorted directory, and it has exactly the same limits. It makes lookups by the sorted columns fast, does nothing for any other column, and has to be kept up to date every time someone moves house.
A table has one index on (city, created_at). Which of these can use it: WHERE city = 'Pune'; WHERE created_at > '2026-10-01'; WHERE city = 'Pune' AND created_at > '2026-10-01'?
What an index actually is#
An index is a separate, sorted structure that holds the indexed column values and, for each one, a pointer to where the full row lives. Almost every relational database uses a B-tree (strictly, a B+ tree) for this: a short, wide tree whose bottom level holds every value in sorted order, and whose upper levels are signposts that tell you which way to go.
"Short and wide" is the point. Each page of the tree holds hundreds of keys, so even a huge table needs only a few levels. Watch a lookup.
Multiply the table by a thousand and the tree grows by about one level. That is the whole magic of indexes: lookup cost barely grows while the data does. The root and upper levels are read on every lookup, so they stay in the buffer pool, and in practice a lookup often touches disk once or not at all.
Composite indexes and the leftmost rule#
An index can cover several columns, such as (city, created_at). The tree is sorted by
city first, and within each city by date, exactly like a directory sorted by surname and
then first name.
That ordering decides which queries it helps. You can use it from the left: city alone, or city and date together. You cannot jump into the middle: a query on date alone has no city to start from, the same way a directory sorted by surname cannot find every "Asha".
The rule of thumb for column order: columns you filter with equality first, then the one
you filter by range or sort by. (status, created_at) serves "pending orders from today".
(created_at, status) mostly does not.
Covering indexes#
If every column a query needs is inside the index, the database can answer from the index
alone and never visit the table. This is a covering index, and Postgres shows it as an
"Index Only Scan". For a hot query like "the last 20 order ids and totals for this
customer", an index on (customer_id, created_at, total) can make it several times faster.
Indexes are not free#
Every index is a second copy of some of your data, sorted, and every write has to update it.
- Writes get slower. An insert into a table with eight indexes is nine writes. Heavy write tables with many indexes are a classic cause of slow inserts.
- Storage grows. Indexes on a big table can be as large as the table itself.
- Low selectivity columns rarely help. An index on
is_active, where 95% of rows are true, does nothing forWHERE is_active = true: reading the whole table is cheaper than following millions of pointers.
When your index is ignored#
| Choice | What you gain | What you pay | Pick it when |
|---|---|---|---|
| B-tree index | Fast equality and range lookups, and sorted output for ORDER BY. | Slower writes and extra storage for every index you add. | The default for almost every column you filter, join or sort by. |
| Composite index | Serves multi column filters and sorts in one structure. | Only usable from the leftmost column, so the order is a design decision. | Queries that always filter on the same leading column. |
| Covering index | Answers the query without touching the table at all. | A wider index, so more storage and slower writes. | A small number of very hot read queries. |
Joining orders.customer_id to customers.id, or deleting a customer and checking their
orders, means looking up orders by customer_id. Postgres does not index foreign key
columns automatically, and an unindexed foreign key on a large table turns every such join
or delete into a full scan.
Checkpoint#
1. An index on (city, created_at) exists. Which query cannot use it efficiently?
2. Why is a B-tree lookup still fast on a table of billions of rows?
3. You add an index on is_deleted (true for 2% of rows). WHERE is_deleted = false is still a full scan. Why?
- A B-tree lookup is 3 to 5 page reads on tables from millions to billions of rows.
- Composite indexes work from the left. Equality columns first, then range or sort.
- Every index slows every write. Index what you query, not what you might.
- Functions, leading wildcards and type mismatches silently disable an index.
An index is a separate sorted structure, usually a B-tree, holding the indexed values and pointers to rows. Because each page holds hundreds of keys, the tree is only a few levels tall, so a lookup is a handful of page reads even on billions of rows, and it also makes range queries and sorting cheap. Composite indexes are sorted by the first column, so they only serve queries from the left: equality columns first, then the range or sort column. A covering index answers a query without touching the table. Indexes cost write speed and storage, do nothing for low selectivity columns, and get skipped when you wrap the column in a function, use a leading wildcard or compare different types.