Indexes and query plans
Introduced
Vocabulary
| English | Meaning |
|---|---|
| B-tree | B-tree |
| query plan | query plan |
The sorted shortcut
- A B-tree index keeps keys sorted in a balanced multiway tree: our order-4 teaching tree holds 15 keys in 2 levels — any key in 2 node reads against 15 sequential.
- The query plan is the engine's chosen pipeline:
EXPLAIN QUERY PLANprints it, and the plan — not the query text — prices the work.
{exercise:uni-cs0804-btree}
Practice
A fan-out-100 B-tree of height 3 covers — keys
Difficulty 1/5 · 100 coins + a small bonus on first completion today
m to the h: 100 cubed is a million - 3 reads per lookup.
Fan-out arithmetic
- A node of $k$ keys routes among $k + 1$ children: fan-out $\approx m$ covers $m^h$ entries at height $h$. Fan-out 100: three levels cover $100^3 = 10^6$ keys — a million-row lookup in 3 reads, for every key (splits keep it balanced).
SELECT title FROM Course WHERE credits = 20: unindexed the plan readsSCAN Course; withINDEX ON Course(credits)it readsSEARCH Course USING INDEX idx (credits=?). On 6 rows both are instant; on 6 million it is 3 reads against 6 million.
{exercise:uni-cs0804-plan}
Practice
EXPLAIN QUERY PLAN without an index prints —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The engine says what it will do: SCAN is the full-table read.
The write tax
- Each index adds work to every insert and delete: our schema with 3 indexes writes 4 structures per insert (table + 3 trees). A log table with 5 indexes at 10 million inserts a day maintains 50 million index entries daily.
- Index what you query, drop what you do not, and read the plan, not the query.
WHERE UPPER(name) = …defeats a plain index — the computed column does not match.
{exercise:uni-cs0804-tax}
Practice
A table with 3 indexes costs each insert —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Table + 3 trees = 4 structures: every index is a loan the writes repay.