Indexes and query plans

Vocabulary

English	Meaning
B-tree	A balanced multiway search tree storing ordered keys and supporting efficient lookup and update.
query plan	The sequence of operations a database chooses to execute a query.

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 PLAN prints 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

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 reads SCAN Course; with INDEX ON Course(credits) it reads SEARCH 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

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