SYSTEM DESIGN SERIES · TOPIC 10 OF 23+ · part of the 09 → 10 → 11 chain
1. Full Scan vs Index Lookup
Same question, two very different amounts of work (looping)
✗ No index: check row 1, row 2, row 3… one at a time
✗ The match could be the very last row - you don't know until you get there
✗ Cost grows with table size: O(n)
✓ With an index: descend a small sorted tree - a few hops
✓ Land almost directly on the matching row
✓ Cost barely grows with table size: O(log n)
2. What an Index Actually Is
A separate, sorted structure that points back to the real row
A sorted copy of just the indexed column(s) + a pointer back to the full row
Without one, the only option is scanning every row, every time
The pointer-back is one extra hop - unless the index already has everything the query needs
An index is data too - every write (topic 09) must keep it in sync
📖 Analogy: the index at the back of a textbook. You don't reread every page - you jump to a page number, then flip there directly.
3. B-Tree vs Hash Index
B-Tree
Keeps keys in sorted order
Handles <, >, BETWEEN, ORDER BY
O(log n) - the default choice almost everywhere
VS
Hash
No ordering - just key → bucket
O(1) average, but exact-match only
Can't do ranges, can't sort, can't do "starts with"
☎️ Analogy: B-Tree is a phone book - sorted, so "everyone between Smith and Suarez" is easy. Hash is a locker number keyed to your ID - instant, but only if you know the exact key.
4. The Write Cost of Every Index
One write, updating the table AND every index on it
Every INSERT / UPDATE / DELETE touches the table and every index on it
More indexes = slower writes, faster (specific) reads
Don't index every column "just in case" - each one has a real, ongoing cost
5. Composite Indexes - Leftmost Prefix
An index on (A, B, C) doesn't mean what people assume
Sorted by A first, then B within each A, then C within each B
Usable for queries on A, or A+B, or A+B+C - in that order
A query on B alone, or C alone, can't use this index at all
6. When the Index Gets Skipped
An index existing doesn't mean the query will actually use it
Function-Wrapped Column
Leading Wildcard %search
Low-Cardinality Column
Implicit Type Cast
Too Many Indexes to Pick From
An unused indexstill costs every write, for zero read benefit
Always check the query plan. "There's an index on that column" and "this query uses that index" are two different facts.
7. Clustered vs Non-Clustered
Clustered:
✔ The table's rows ARE physically sorted by this key
✔ Only one per table - there's only one physical order
✔ Reading a range off it is nearly free
An Index Trades Write Cost for Read Speed - Spend It Deliberately
Non-Clustered:
✔ A separate structure, pointing back to the row
✔ A table can have many of these
✔ Extra hop to fetch the row, unless it's covering
💡An index keeps one extra copy in sync with the table. Keeping full copies in sync across machines is Replication - topic 11, next.