Database Indexing Explained

Problem What is an index in a database, and how does it help?

Be ready to discuss

• What it is: an auxiliary structure — commonly a B-tree/B+ tree, sometimes a hash, GIN, or bitmap index — built over one or more columns so the engine can locate matching rows without scanning the whole table.
• The payoff: turns an O(n) full table scan into an O(log n) descent for WHERE, JOIN, and ORDER BY predicates; a B+ tree's linked leaves also make range scans and sorted output cheap.
• The cost: extra storage plus slower writes, since every insert/update/delete must maintain each index — over-indexing is a real penalty on write-heavy workloads.
• Composite indexes and the leftmost-prefix rule: an index on (a, b) serves filters on a or a+b, but not on b alone.
• Covering indexes and index-only scans: when the index holds every column the query needs, the table lookup disappears entirely.
• When an index is useless or harmful: low-selectivity columns (a boolean flag), predicates wrapping the column in a function (WHERE lower(email) = ... needs an expression index), leading wildcards in LIKE, and small tables where a scan wins.
• Clustered versus non-clustered/secondary indexes, and what that means for physical row order and lookup cost.
• Choosing indexes from real query patterns and confirming with EXPLAIN ANALYZE rather than indexing every column that appears in a WHERE.