Indexes
Auxiliary structures (usually B+ trees) that make predicates cheap at the cost of writes and space.
Level: intermediate
What is it?
An index is a data structure maintained with a table so a predicate (equality, range) can find rows without a full scan. Clustered indexes are the table; secondary indexes point at keys or row ids. Hash indexes help equality, not ranges.
Why does it matter?
The difference between 10 ms and 10 s. Also the difference between a fast write and a slow one: every index is extra work on INSERT/UPDATE/DELETE.
Mental model
The card catalog, not the shelves. You still have to maintain both when a book moves.
How it works
- B+ tree: ranges and ordered scans. The default.
- Selectivity: an index on 'gender' is often useless; an index on 'email' is not.
- Covering: if the index has every column you need, you never touch the heap.
- Write amplification: each extra index is another structure to update.
Real-world usage
- OLTP lookups
- Joins (nested loop + index)
- Unique constraints
Common mistakes
- Indexing every column
- Prefix wildcards (LIKE '%foo') that cannot use a B-tree
- Forgetting composite index column order
Interview questions
Why does an index slow writes?
Each insert/update/delete must maintain the index structure (splits, leaf writes) in the same transaction.
Leftmost prefix rule?
A composite index (a,b,c) supports predicates on a, a+b, a+b+c — not b alone.