Database Indexing

An index is an auxiliary data structure that lets a database locate rows without scanning an entire table, trading extra storage and slower writes for dramatically faster reads. It is the first lever most engineers reach for when queries are slow.

An index maps column values to the locations of the rows that hold them, keeping those entries in a sorted or hashed structure so lookups avoid a full scan. Most relational databases default to a B-tree index, which keeps keys sorted and balanced so both point lookups and range scans stay efficient.

A lookup starts at the root and follows one child per level, so finding a key in a table of n rows costs about log(n) steps instead of scanning all n. The catch appears on writes: every insert, update, or delete must also modify each index that covers the changed columns, and the tree may need rebalancing.

The concrete behavior depends on the underlying Storage Engine Internals: a B-tree index updates in place, while a log-structured engine appends and merges, changing the read/write balance.

Every index accelerates some reads but taxes every write and consumes storage, so more indexes is not better. A common mistake is indexing columns that are rarely filtered on, or maintaining many indexes on a write-heavy table where the write penalty outweighs the read gain. Composite indexes help multi-column filters but only when queries respect the column order.

• State which columns you would index and why, tied to the query pattern.
• Call out the write cost explicitly, and mention that over-indexing a write-heavy table hurts.
• If asked about very large tables, connect indexing to the storage engine and to sharding rather than treating it in isolation.