How does database indexing work?

An index is a separate data structure that lets the database find rows without scanning the whole table. The most common type is a B-tree (or B+ tree), which keeps keys sorted and balanced so lookups, range queries, and ordering run in O(log n) instead of O(n).

Conceptually it is like the index at the back of a book: instead of reading every page, you jump straight to the right one. You index the columns you frequently filter, join, or sort on.

The trade-off is writes and storage: every index must be updated on insert, update, and delete, so over-indexing slows writes and consumes space. Hash indexes suit exact-match lookups, while B-trees also support ranges. In an interview, explain that you add indexes to speed up specific read patterns, measure with the query planner (EXPLAIN), and balance read speed against write cost rather than indexing everything.