Database indexing

How a database index actually works

An index is a second data structure, kept sorted, that lets the database find rows without reading the whole table. The default is a B-tree: balanced, sorted by the indexed column, so it answers =, <, >, BETWEEN, prefix LIKE 'abc%', and ORDER BY from the same shape. A lookup walks from the root down to a leaf in a handful of steps instead of scanning millions of rows.

The cost lives on the write side. Every INSERT, UPDATE, or DELETE has to maintain every index that touches the changed columns. Five indexes on a table means one row write plus five index writes. That is the whole tradeoff: indexes trade cheaper reads for more expensive writes and more disk.

CREATE INDEX idx_users_email ON users (email);
SELECT * FROM users WHERE email = 'a@b.com';   -- index seek
SELECT * FROM users WHERE country = 'PL';       -- full scan, index irrelevant

wrong "add an index and the table gets faster." An index only helps queries whose filter or sort matches its columns. The email index does nothing for a query on country, and it slows down every write to the table regardless.

Composite indexes and column order

An index on several columns is stored like a phone book: sorted by the first column, then by the second within each value of the first, then the third. That ordering gives you the leftmost-prefix rule. An index on (a, b, c) serves filters on a, on a and b, and on all three, but never on b alone or c alone.

Column order is a design decision, not a formality. Two rules cover most cases: put equality columns before range columns, and among equality columns put the more selective one first.

CREATE INDEX ok  ON orders (status, created_at);   -- equality then range
SELECT * FROM orders
WHERE status = 'paid' AND created_at > '2026-01-01';

Flip it to (created_at, status) and the range on created_at comes first, so the index can no longer narrow on status. A range in the middle of the key stops every column after it from acting as a search boundary.

When the index does not help

Selectivity decides everything. An index earns its cost when a query matches a small slice of the table. Index a boolean or a status flag where one value covers most rows, and the planner will often read the table sequentially anyway, because jumping index-to-table for 90% of rows is slower than one clean pass.

Two more traps: a leading-wildcard LIKE '%term' cannot use a normal B-tree, and wrapping the column in a function (WHERE lower(email) = ...) disables the plain index unless you index that exact expression. When a query is slow, read the EXPLAIN before adding anything: a sequential scan on a large table with a selective filter is the signal that an index is missing.

Index structures and the workload each fits

Three structures come up, and the interview wants you to name the workload each one serves. A B-tree stays sorted and updates in place, which gives you ranges and ordered scans, at the price of page splits and random writes (write amplification around 3 to 5 times). A hash index answers equality in one probe but supports no ranges, no ORDER BY, and no prefix: Postgres ships real hash indexes, InnoDB exposes none on disk and only keeps an internal adaptive hash. An LSM-tree buffers writes in a memtable plus a write-ahead log, flushes them as immutable sorted files, and merges those in the background via compaction. Writes are sequential and throughput is high, so it wins the write-heavy log or time-series case, but a point read may check the memtable and several levels, which is why LSM engines lean on Bloom filters to skip levels that cannot hold the key. RocksDB, Cassandra, and LevelDB are LSM; most relational defaults are B-tree.

Clustered, secondary, and covering reads

The clustered-versus-secondary distinction trips people. In InnoDB the table is the primary-key B-tree, so a secondary index stores the primary key as its row locator, and a non-covering secondary lookup walks the clustered index a second time to fetch the row. Postgres keeps the heap separate: every index points at a heap tuple, and even the primary key is a secondary structure.

A covering index carries every column the query needs, so the answer comes from the index and never touches the table. In Postgres you extend the payload without widening the sort key using INCLUDE:

CREATE INDEX idx ON users (country) INCLUDE (email);
SELECT email FROM users WHERE country = 'PL';   -- Index Only Scan, if pages are all-visible

wrong "an index-only scan never reads the table." Postgres consults the visibility map, and if the page is not marked all-visible it fetches the heap tuple to check MVCC visibility. A covering index is necessary, not sufficient, and a table that is not vacuumed loses the benefit.

Reading EXPLAIN when the planner surprises you

The move interviewers grade is diagnosis, not "force the index." Read the plan and compare the estimated rows against actual rows. A large gap means stale statistics or correlated predicates the planner cannot model, so ANALYZE the table before you touch indexes. A seq scan under a low-selectivity filter is correct: matching most of the table beats random index-plus-heap fetches. A Bitmap Index Scan feeding a Bitmap Heap Scan is the planner handling medium selectivity, sorting matches into heap order to cut random I/O. When someone reaches for an index hint before reading the estimate, that is the tell they do not understand what the optimizer is doing.