DBMS deep dive
Database Indexes (B-Tree, Hash, Composite): deep dive
An index is a sorted copy of some columns plus a pointer back to the row, and on disk it is almost always a B+tree. If you understand page reads, the leftmost-prefix rule and covering indexes, you can predict which queries an index will speed up before you run EXPLAIN.
Why a B+tree is so shallow
Databases read storage in pages, 8 KB in PostgreSQL and 16 KB in InnoDB. An internal B+tree node fills a whole page with keys and child pointers, so one node can have a few hundred children. With a fan-out of about 400, three levels reach 400³ = 64 million leaf entries, and four levels cover tens of billions. A lookup by key therefore costs about 3–4 page reads, and the root and upper levels are almost always cached in memory.
Two details matter in interviews. First, only the leaves hold the full entries, and the leaves are linked to their neighbours, so a range scan finds the first key and then walks sideways without going back up the tree. Second, finding the index entry is often not the expensive part. The expensive part is fetching each matching row from the table (the heap), which can be one random page read per row.
The leftmost-prefix rule in practice
A composite index on (country, city, age) is sorted by country first, then by city within each country, then by age. A query can use the sorted order only for a prefix of those columns, and the scan stops narrowing at the first range condition.
| WHERE clause | How the index (country, city, age) helps |
|---|---|
| country = 'IN' | Seeks on country |
| country = 'IN' AND city = 'Pune' | Seeks on both columns |
| country = 'IN' AND city = 'Pune' AND age > 30 | Seeks on all three, then a range on age |
| country = 'IN' AND age > 30 | Seeks on country only; age is checked per entry because city is skipped |
| city = 'Pune' | No seek; at best a full index scan (or a skip scan in some engines) |
| country = 'IN' AND city > 'M' AND age = 30 | Seeks on country plus a range on city; age is only filtered |
A good rule of thumb is to put equality columns first, then the column used for range or ORDER BY. An index on (user_id, created_at) serves WHERE user_id = ? ORDER BY created_at DESC LIMIT 20 with no sort step. Reversing the column order would not.
Covering indexes and index-only scans
If every column a query needs is in the index, the engine can skip the table entirely. PostgreSQL lets you add non-key payload columns with INCLUDE:
-- Hot query: a user's recent order totals
SELECT created_at, total
FROM orders
WHERE user_id = 42
ORDER BY created_at DESC
LIMIT 20;
-- Key columns give the order; INCLUDE adds payload without affecting sort
CREATE INDEX idx_orders_user_recent
ON orders (user_id, created_at DESC) INCLUDE (total);
-- Partial index: index only the rows you actually query
CREATE INDEX idx_orders_pending ON orders (created_at) WHERE status = 'pending';In PostgreSQL an index-only scan still checks the visibility map, because the index does not store row visibility. On a table that has not been vacuumed recently, it falls back to heap fetches. You can see this as Heap Fetches in EXPLAIN output.
Clustered vs secondary indexes
In InnoDB the table is a B+tree ordered by the primary key, which makes it a clustered index. Secondary index leaves store the primary key, not a physical address, so a lookup through a secondary index walks two trees. That is why a wide primary key such as a UUID string makes every secondary index bigger, and why random UUIDv4 keys cause page splits all over the tree. PostgreSQL tables are heaps. Every index, including the primary key, points to a tuple location (ctid).
Common mistakes
- Creating separate single-column indexes on a and b when queries filter on both. One composite index usually beats a bitmap AND of two indexes.
- Indexing low-selectivity columns such as a boolean on their own. A partial index is usually what you want instead.
- Wrapping the column in a function or cast (
DATE(created_at) = ...), which makes the predicate non-sargable. - Never removing unused indexes. Each one slows down every INSERT and every UPDATE that touches its columns. Check
pg_stat_user_indexes. - Assuming
LIKE '%term'can use a B-tree. Only a fixed prefix can. Use a trigram or full-text index for substring search.
Interview questions
›Why do databases use B+trees instead of binary search trees or hash tables?
A binary tree has a fan-out of 2, so it is about log2(n) levels deep, which means far more page reads. A hash table cannot serve ranges or ORDER BY. A B+tree has high fan-out, stays balanced and keeps its leaves linked, so it serves equality, ranges and sorted output in a few I/Os.
›What is index selectivity, and why does it matter?
Selectivity is the fraction of rows a predicate matches. If a predicate matches a large share of the table, many random heap reads cost more than one sequential scan, so the planner will skip the index.
›How does an index slow down writes?
Every INSERT and DELETE has to update every index, and an UPDATE has to update each index whose columns changed. That means extra page writes, more WAL or redo, and occasional page splits. Write-heavy tables should carry only the indexes their queries really use.
›What is a page split?
When a leaf page is full and a new key belongs inside it, the engine splits the page into two half-full pages and adds a separator key to the parent. Random-order keys cause frequent splits and fragmentation, while ever-increasing keys only append on the right side.
›When would you choose a hash index over a B-tree?
Rarely. Only for pure equality lookups on large keys, where it can be smaller. It cannot do ranges, sorting or prefix matches. In PostgreSQL it has been crash-safe only since version 10, so B-tree is the default choice.