Indexes
How database indexes turn full table scans into a few hops: B-trees, hash and LSM indexes, composite column order, covering indexes, and what every index costs on writes.
On this page
The problem: one login, ten million rows
A users table has 10 million rows. Every login runs:
SELECT id, password_hash FROM users WHERE email = 'priya@example.com';
Without help, the database reads every row and compares the email: a full table scan. At roughly 200 bytes a row that is about 2 GB of data per login. Even if it is all cached in memory, scanning takes hundreds of milliseconds of CPU; from disk it takes seconds. At 500 logins per second the database spends all its time scanning and nothing else gets through.
Without an index, the database checks every row
- Imagine a table with ten million users, and you need the one with a particular email. Without help, the database checks every single row, one by one. That is a full table scan.
The idea: a sorted copy of one column, pointing at the rows
An index is a separate data structure that keeps the values of one or more columns in sorted order, each with a pointer to its row. Because it is sorted, the database can jump to the right place, like opening a dictionary near "P" instead of reading from page one.
A sorted index finds any key in a few hops, even among millions
- An index is like the index at the back of a book: a separate, sorted list of email addresses, each pointing to where its row lives.
- Because the index is sorted, the database can jump straight to the right spot, like finding a word in a dictionary. Most databases store it as a B-tree: a few hops from the top reach any key among millions.
- That is the magic: with an index, lookups grow very slowly. Ten times more rows adds just a step or two, not ten times the work.
CREATE UNIQUE INDEX idx_users_email ON users (email);
The login query now reads a handful of index pages and one row: about a millisecond instead of seconds. And UNIQUE also enforces that no two users share an email, which is often the first reason to add an index.
How a B-tree index works
Almost every relational database (PostgreSQL, MySQL's InnoDB, SQL Server, Oracle) uses a B-tree (strictly, a B+ tree) by default. It is a shallow, wide tree of fixed-size pages (8 KB in Postgres, 16 KB in InnoDB):
- The root and internal pages hold sorted keys that act as signposts: "keys below
mgo left,mtotgo here…". One page holds hundreds of signposts. - The leaf pages hold every key in order, with a pointer to the row (or, in InnoDB's primary key, the row itself). Leaves are linked to their neighbours, so a range like
BETWEEN 'a' AND 'c'walks along them.
Worked example: how deep is the tree?
The number of children per page is the fan-out. With a fan-out of about 500:
| Rows | Levels needed | Pages read per lookup |
|---|---|---|
| 500 | 1 | 1 |
| 250,000 | 2 | 2 |
| 125 million | 3 | 3 |
| 62 billion | 4 | 4 |
Growing from 10 million to 1 billion rows adds about one level. The top levels are read constantly, so they stay in memory; a lookup usually costs one or two disk reads at most, about 0.1 ms each on an SSD. That is why lookups grow so slowly with table size (logarithmically, in the jargon).
Three kinds of index
| Index | How it works | Good at | Weak at | Found in |
|---|---|---|---|---|
| B-tree | Sorted tree of pages, updated in place | Equality, ranges, ORDER BY, prefixes | Random writes cost page updates; pages split as they fill | Default in Postgres, MySQL, SQL Server |
| Hash | Hash of the key → bucket | Exact-match lookups, O(1) | No ranges, no sorting, no prefixes | Postgres USING hash, in-memory stores, Redis itself |
| LSM-tree | Writes go to memory, then flush to sorted immutable files that are merged in the background | Very high write rates | Reads may check several files; background merging uses disk and CPU | Cassandra, RocksDB, ScyllaDB, HBase |
LSM-trees in a little more detail
A log-structured merge tree (LSM-tree) never updates data in place:
- A write is appended to a write-ahead log on disk (for durability) and inserted into a sorted in-memory table, the memtable.
- When the memtable fills (tens of MB), it is written out in one go as a sorted, immutable file, an SSTable.
- Reads check the memtable, then SSTables from newest to oldest. A Bloom filter per file (a compact bit array that can say "definitely not here") lets most files be skipped.
- Compaction merges SSTables in the background, dropping overwritten values and tombstones (markers that record a delete).
Turning random writes into sequential ones is why LSM-based stores absorb hundreds of thousands of writes per second. The price is read amplification (several files per read) and write amplification (each value is rewritten several times by compaction).
Composite indexes: column order matters
A composite index sorts by the first column, then the second
- An index can also cover several columns, called a composite index. Order matters: an index on city then signup date helps “users in Pune who joined this week”, just like a phone book sorted by surname, then first name.
A composite index covers several columns, sorted by the first, then the second within each first value, like a phone book sorted by surname then first name.
CREATE INDEX idx_users_city_signup ON users (city, signup_date);
| Query | Uses the index? | Why |
|---|---|---|
WHERE city = 'Pune' | Yes | Leftmost column |
WHERE city = 'Pune' AND signup_date > '2026-11-01' | Yes, fully | Jump to Pune, then scan a date range inside it |
WHERE signup_date > '2026-11-01' | Not efficiently | Dates are sorted only within each city, so the planner would have to visit every city's slice |
WHERE city = 'Pune' ORDER BY signup_date DESC LIMIT 20 | Yes, no sort step | Rows come out of the index already in order |
This is the leftmost prefix rule. Two practical guidelines follow:
- Put columns tested with equality first, then the one column used for a range or sort. An index on
(signup_date, city)would serve the second query poorly: the range on the date comes first, so the city can't narrow the scan. - Within the equality columns, order to match the most queries you can serve with one index. "Most selective first" matters less than matching the queries.
Covering indexes
A covering index contains every column the query needs, so the database answers from the index alone and never visits the table (an index-only scan).
-- the query
SELECT city, signup_date, name FROM users WHERE city = 'Pune' AND signup_date > '2026-11-01';
-- PostgreSQL 11+ / SQL Server: add non-key columns to the leaf pages
CREATE INDEX idx_city_signup_cov ON users (city, signup_date) INCLUDE (name);
For a query returning 5,000 rows scattered across the table, this can turn 5,000 random page reads into a few dozen sequential ones. Two details worth knowing: in InnoDB every secondary index already contains the primary key, so queries needing only indexed columns plus id are covered for free; and in Postgres an index-only scan still checks a visibility map to confirm rows are visible, so it works best on tables that are vacuumed regularly.
What indexes cost
Every write must update every index
- But indexes are not free. Every insert or update must also update every index on that table, and each index takes extra disk space. Index the columns you search by, not everything.
| Cost | Size of it |
|---|---|
| Writes | Each insert updates the table plus every index: a table with 6 indexes does about 7 structure updates per insert. Updating an indexed column means deleting and re-inserting its index entry. |
| Space | An index on a few columns is often 10–30% of the table's size; many indexes can exceed the table itself. |
| Memory | Indexes compete with data for the buffer cache. An index that doesn't fit in memory turns lookups into disk reads. |
| Planner choices | More indexes, more plans to consider; occasionally the planner picks a worse one. |
A useful rule: index for your slow and frequent queries, check with EXPLAIN (or EXPLAIN ANALYZE, which runs the query) that the index is used, and drop indexes nothing uses (Postgres tracks this in pg_stat_user_indexes).
Primary key choice and page splits
In InnoDB the table itself is stored as a B-tree ordered by the primary key (a clustered index). With an auto-increment id, new rows always go at the right-hand end and pages fill neatly. With a random UUID (v4), each insert lands on a random page, which must be in memory and may split in two when full: more I/O, half-empty pages, and a bigger index. Time-ordered ids such as UUIDv7, ULIDs or Snowflake-style ids keep inserts near the end while staying globally unique. Postgres stores rows in an unordered heap, so the effect there is limited to the primary key index itself, but it still exists.
When not to add an index
- Write-heavy tables with few reads, such as an audit log that is only read during investigations: every index slows every write.
- Small tables of a few thousand rows: a scan is already fast, and the planner will often ignore the index.
- Analytics over most of the table: if a query reads 40% of rows, a scan (or a column-oriented warehouse) is better.
- Low-selectivity columns on their own (see the box above).
In the interview
An orders table (200 M rows) has these frequent queries: (1) a customer's latest 20 orders; (2) orders with status pending older than 10 minutes, for a retry job; (3) one order by id. Which indexes do you create, in what column order, and why?
Compare with our answer
- (3) is the primary key on
id: no extra index. - (1)
(customer_id, created_at DESC): equality on customer, then the sort column, so the query reads 20 entries in order with no sort step. AddINCLUDE (total, status)if the list page needs only those, to make it covering. - (2) a partial index
ON orders (created_at) WHERE status = 'pending': pending orders are a tiny fraction, so the index stays small and the job reads only them in age order. A composite(status, created_at)also works but indexes every status. - Mention the write cost: two secondary indexes on a write-heavy table are acceptable; check with
EXPLAIN ANALYZE.
A strong answer mentions: equality column before the sort/range column · avoiding a sort with index order · a partial index for the rare status · covering with INCLUDE where it helps · the write cost of each extra index.
A team adds CREATE INDEX ON users (signup_date, country). Their dashboard query WHERE country = 'IN' AND signup_date >= '2026-01-01' is still slow, and their mobile login query WHERE LOWER(email) = ? also scans, though email has an index. What's wrong?
Compare with our answer
- The composite index has the range column first. The database can use it for the date range, but within that range rows are sorted by date, not country, so it reads every country's rows from 2026 and filters. Reorder to
(country, signup_date). LOWER(email)applies a function to the column, so the plain index onemailcan't be used. Create an expression index onLOWER(email)or store emails already lowercased (with a unique index on that).- Build the new indexes with
CREATE INDEX CONCURRENTLYso writes aren't blocked, then drop the unused old one. - Verify both with
EXPLAIN ANALYZE.
A strong answer mentions: equality before range in composite indexes · functions on columns defeat plain indexes · expression indexes or normalised storage · building indexes without blocking writes · checking the plan with EXPLAIN.
- Index = sorted copy of some columns with pointers to rows. Turns a full scan into a few page reads.
- B-tree (default): equality, ranges, sorting; fan-out ~hundreds → 3–4 levels for billions of rows.
- Hash: exact match only. LSM-tree: memtable + SSTables + compaction + Bloom filters, built for heavy writes (Cassandra, RocksDB).
- Composite: leftmost prefix rule. Equality columns first, then one range/sort column.
- Covering: all needed columns in the index → index-only scan (
INCLUDEin Postgres 11+). - Costs: every index on every write, disk space, buffer memory. Drop unused ones.
- Index ignored when: functions on the column, leading
%wildcard, type mismatch, wrong column order, stale stats. - Low-cardinality column → partial index. Big table →
CREATE INDEX CONCURRENTLY. Random UUID keys → page splits; prefer time-ordered ids.
1. A query filters WHERE tenant_id = ? AND created_at > ? ORDER BY created_at. Which index serves it best?
Equality first, then the range and sort column: the index jumps to the tenant and reads its rows already sorted. With the date first, every tenant's rows in the range are read and filtered.
2. A table has 500 million rows and a B-tree index on its primary key with a fan-out around 500. Roughly how many index levels does a lookup traverse?
500² = 250,000 and 500³ = 125 million, so 500 million needs 4 levels. The wide fan-out is why B-trees are so shallow; a binary tree would need about 29.
3. A metrics service writes 300,000 points per second and reads recent points per series. Which storage structure fits the write load best?
LSM-trees turn random writes into sequential flushes, which suits very high write rates. B-trees update pages in place, and hash indexes can't serve range reads by time.
4. A query uses WHERE LOWER(email) = 'a@b.com' and an index exists on email. The plan shows a full scan. What is the best fix?
A function applied to the column hides it from a plain index. An expression index (or normalised storage) matches the query exactly.
5. An events table receives 20,000 inserts per second and has 9 secondary indexes, most added for one-off reports. Inserts are slowing down. What is the most effective step?
Every insert updates the table plus 9 indexes. Removing unused ones cuts write work directly; run the occasional reports on a replica or a warehouse instead.
6. A jobs table has a status column where 99% of rows are done and 1% are pending. The worker polls for pending jobs. Which index is the best fit?
A partial index holds just the 1% that matter, stays small, and serves the poll in order. A plain index on status works but is mostly entries for 'done' that nobody reads.
7. Why can a covering index make a query much faster?
With every needed column in the index, the database does an index-only scan and never fetches each row from the table, avoiding many scattered page reads.
Score 60% or more and the lesson is marked complete.