An index is a secondary data structure that turns a full-table scan into a targeted lookup. Without one, finding a row means reading every page; with one, the database navigates directly to the rows it needs. Interviewers probe indexing to see whether you understand the physical reality beneath SQL: disks, pages, and the logarithmic structures that keep queries fast as tables grow to billions of rows.
How storage works: pages and the buffer pool
Databases do not read individual rows from disk. They read pages (typically 8 KB or 16 KB), the smallest unit of I/O. Pages are cached in the buffer pool in RAM. The entire game of indexing is minimizing the number of pages fetched from disk, because a random disk read (even on SSD) is orders of magnitude slower than a RAM access. An index that lets you touch three pages instead of thirty thousand is the difference between a 1 ms and a 1 s query.
Why B+ trees dominate
The default index in PostgreSQL, MySQL/InnoDB, Oracle, and SQL Server is the B+ tree. It is a balanced tree optimized for block storage:
- High fan-out: each node holds hundreds of keys, so the tree stays shallow — a billion rows fit in about 3-4 levels. That means 3-4 page reads to find any row.
- All values live in the leaves: internal nodes hold only keys for navigation. Leaves hold the actual pointers (or rows).
- Leaves are linked: a doubly linked list connects leaf pages, making range scans (
WHERE age BETWEEN 20 AND 40) trivial — find the start, then walk the linked list. - Always balanced: every leaf is at the same depth, so lookups have predictable cost. Inserts and deletes trigger node splits and merges to preserve balance.
The following widget lets you insert keys into a B+ tree of order 4, watch nodes split when they overflow, and run a range scan across the leaf-linked list.
B+ tree index
Insert keys to watch node splits; scan a range along the linked leaves.
The reason a plain binary search tree is not used on disk is fan-out: a BST branches two ways per node, so a billion rows need ~30 levels — 30 random page reads. A B+ tree with fan-out 400 needs about 3. Height, times page-read latency, is the query cost.
Hash indexes: O(1) but limited
A hash index stores keys in a hash table, giving expected O(1) equality lookups — faster than a B+ tree for WHERE id = 42. But it has a fatal limitation: hashing destroys order, so hash indexes cannot serve range queries or ORDER BY. They only handle equality. Most systems default to B+ trees precisely because they handle equality and ranges and sorting with one structure. Use a hash index only when you have pure equality lookups and know you will never need ordering.
| Property | B+ Tree | Hash Index | |----------|---------|-----------| | Equality lookup | O(log n) | O(1) expected | | Range / BETWEEN | Yes (leaf scan) | No | | ORDER BY support | Yes | No | | Prefix match (LIKE 'abc%') | Yes | No | | Default in most DBs | Yes | Rarely |
Clustered vs non-clustered indexes
This distinction is a favorite interview question.
- A clustered index determines the physical order of rows on disk — the table is the index. There can be only one per table (rows can only be sorted one way). In InnoDB, the primary key is always the clustered index, and the leaf nodes hold the full row.
- A non-clustered (secondary) index is a separate structure whose leaves hold the indexed key plus a pointer back to the row (either a row-id or, in InnoDB, the primary key). Looking up a column through a secondary index therefore often costs a second lookup into the clustered index — a "bookmark lookup."
Covering indexes and the index-only scan
If an index contains every column a query needs (in its key or as included columns), the database answers the query from the index alone, never touching the table. This is a covering index and the resulting index-only scan is one of the highest-leverage optimizations you can mention:
-- If we have INDEX(customer_id, order_date, total),
-- this query is answered entirely from the index:
SELECT order_date, total
FROM orders
WHERE customer_id = 42;
Composite indexes and the leftmost-prefix rule
A composite index on (a, b, c) is sorted by a, then b, then c. It can serve queries filtering on a, on a and b, or on all three — but not a query filtering on b alone, because the data is not sorted by b at the top level. This leftmost-prefix rule explains why column order in a composite index matters enormously. Put the most selective, most frequently filtered equality column first.
When indexes hurt
Indexes are not free. Every INSERT, UPDATE, and DELETE must also update every affected index, so write-heavy tables pay a tax per index. Indexes consume disk and buffer-pool memory. And a low-selectivity index (say, a boolean is_active column that is 95% true) is often ignored by the optimizer because scanning the table is cheaper than bouncing between index and heap. Good indexing is about selectivity: index columns that narrow the result set dramatically.
What interviewers actually probe
- "Why a B+ tree and not a binary tree or a hash?" Fan-out keeps it shallow; leaves are linked for ranges; hashes can't range.
- "What does the primary key index look like?" In InnoDB it is the clustered index holding full rows; secondary indexes point back to it.
- "Your query has an index but it's still slow — why?" Low selectivity, a leftmost-prefix violation, a function on the column (
WHERE YEAR(d) = 2020can't use an index ond), or an implicit type cast. - "How would you speed up this exact query?" A covering composite index in the right column order for an index-only scan.
The mental model to carry into the interview: an index is a sorted map from key to row-location, and every query-tuning question is really about whether the optimizer can walk that map instead of scanning the heap.