Why Indexes Exist

The problem: finding a needle in a haystack

Imagine a students(id, name, department, gpa, email) table with 1,000,000 rows. Now run:

sql
SELECT * FROM students WHERE email = 'jane.doe@example.com';

Without any extra help, the database engine has exactly one option: a full table scan. It reads every single row, one at a time, checks whether email matches, and moves on. On average it has to inspect around 500,000 rows before finding the match (and if no row matches, it must read all 1,000,000 to be sure). For a table this size, that could mean reading gigabytes of data from disk for a single lookup.

What an index actually is

An index is a separate, auxiliary data structure that the database maintains alongside the table. Conceptually, it stores the indexed column's values in sorted (or otherwise organized) order, with each value pointing back to the physical location of the corresponding row(s) in the table. It is very similar to the index at the back of a textbook: instead of flipping through every page to find "transactions," you look up "transactions" in the alphabetically sorted index and jump straight to page 214.

If students.email has an index, the same query becomes: look up 'jane.doe@example.com' in the sorted structure (which takes only a handful of comparisons, not a million), find the pointer, and jump directly to that row. What was an O(n) operation becomes something close to O(log n) or better.

The trade-off

Indexes are not free lunches:

• Extra storage: the index itself is a data structure that must be stored on disk, potentially doubling the space used by that column's data (plus pointers).
• Slower writes: every INSERT, UPDATE, or DELETE that touches an indexed column must also update the index structure, not just the table. More indexes mean more work per write (this is explored fully in 20.14).
• Maintenance overhead: indexes can become fragmented over time and may need periodic reorganizing.

In exchange, you get dramatically faster reads on the indexed column(s) — often the difference between a query taking milliseconds versus seconds or minutes on a large table.

Edge cases

• A table with only a handful of rows (say, 50) gains almost nothing from an index — a full scan of 50 rows is already essentially instant, and the index's overhead may make writes net-negative (see 20.15).
• An index only helps queries that actually use the indexed column in a way the index supports (equality, range, sorting, depending on index type) — an index on email does nothing for a query filtering on department alone.
• Indexes speed up reads but the engine's query optimizer ultimately decides whether to use an index at all, based on statistics like selectivity (20.12) and cardinality (20.13) — having an index doesn't guarantee it will be used.

Interview-style Q&A

Q: Why not just index every column to be safe? A: Because every index adds storage cost and write overhead. Indexing indiscriminately can make bulk inserts and updates painfully slow while providing no benefit to queries that never filter on those columns.

Q: What's the fundamental trade-off an index makes? A: It trades write speed and storage for read speed — data is duplicated into an organized side-structure so that lookups avoid touching (most of) the actual table.

Key takeaway: an index exists to let the engine skip past irrelevant rows instead of examining every one — the classic full-scan-vs-lookup trade-off that underlies every other topic in this chapter.