How do database indexes work and when should you use them?
A database index is an auxiliary data structure, maintained separately from the table, that allows the query engine to locate rows matching a predicate without scanning every row. The canonical implementation is a B-tree (balanced tree), which keeps keys in sorted order and allows O(log n) lookups, range scans, and ordered traversal. Some databases also support hash indexes (O(1) equality lookups, no range scans), bitmap indexes (efficient for low-cardinality columns in analytical queries), and full-text indexes.
A B-tree index on a column stores the indexed values as keys in the tree, with each leaf node containing a pointer to the physical row (a row ID or clustered key). When the query engine evaluates a WHERE clause or JOIN condition, it can traverse the B-tree in O(log n) rather than performing a full table scan in O(n). On tables with millions of rows, this is the difference between a millisecond and minutes.
When to add an index: index columns that appear frequently in WHERE clauses, JOIN ON conditions, or ORDER BY/GROUP BY clauses. Foreign key columns are almost always worth indexing because JOINs on them are common. Columns with high cardinality (many distinct values) benefit most -- an index on a boolean column with only two distinct values is rarely useful.
When not to add an index: indexes consume disk space and must be updated on every INSERT, UPDATE, and DELETE. Tables that are write-heavy and read-seldom may be hurt more than helped. Very small tables often run faster with a sequential scan than index traversal due to the overhead of random I/O.
Composite indexes -- indexes on multiple columns -- are worth understanding specifically. A composite index on (a, b) supports queries filtering on a, or a and b together, but not b alone (due to the leftmost prefix rule). Column order in composite indexes matters significantly for which queries benefit.
Candidate explains that indexes speed up lookups and that they trade write performance for read speed, but cannot describe the underlying data structure (B-tree) or explain when not to use them.
Candidate describes B-tree structure, explains O(log n) lookup, discusses cardinality and when indexes are and are not beneficial, mentions composite indexes and the leftmost prefix rule, and addresses write overhead trade-offs.
Reading the answer is step one. Explaining it unprompted — under interview pressure — is what actually matters. Get AI-graded feedback on your answer with follow-up probes on your weak points.
Get Graded — Free Assessment