CSE Roadmap

Core tier · about 2 hours · 5 parts

Part 5 of 5 · 3 min read

Exercises

Easy

Easy 1: Name the slow path (15 minutes)

State what a database must do to answer a filtered query when no index exists on the filtered column.

Done when: a full table scan is correctly named.

Hint

A full table scan, reading and checking every row.

Easy 2: Name the two index parts (15 minutes)

Name the two main parts of a typical index structure.

Done when: the search tree and the leaf nodes are both correctly named.

Hint

The search tree and the leaf nodes.

Easy 3: State the trade-off (15 minutes)

State what an index costs in exchange for faster lookups.

Done when: extra storage and write-maintenance cost are both mentioned.

Hint

Extra storage for the index structure itself, plus extra work to maintain it on every write.

Medium

Medium 1: Predict scan cost growth (25 minutes)

Explain why a full table scan's cost grows directly with the size of the table, using the orders table as an example.

Done when: the explanation correctly ties scan cost to reading every row, regardless of how few rows actually match.

Hint

Every row must be read and checked, so doubling the table roughly doubles the scan's cost.

Medium 2: Decide if an index helps (25 minutes)

A query filters WHERE customer_id = 42, and an index exists on customer_id. A second query filters WHERE placed_on = '2026-01-01', with no index on placed_on. State which query can avoid a full scan.

Done when: only the first query is correctly identified as avoiding a full scan.

Hint

Only the first query, filtering on the indexed customer_id column, can avoid a full scan.

Medium 3: Trace a lookup through the structure (30 minutes)

Describe, step by step, how a lookup for customer_id = 42 travels through an index's search tree to reach the correct leaf node.

Done when: the description correctly shows the search tree narrowing the range level by level until exactly one leaf node is reached.

Hint

Each level of the search tree picks the branch covering the range containing 42, narrowing down until one leaf node remains.

Hard

Hard 1: Explain why the search tree holds no data (30 minutes)

Explain why the internal levels of an index's search tree do not themselves store the indexed values and row pointers.

Done when: the explanation correctly notes the search tree's only job is narrowing down which leaf node to check, with the actual entries living only in the leaf nodes.

Hint

Keeping the search tree free of actual data keeps it small and fast to traverse; the real entries only need to live in one place, the leaf nodes.

Hard 2: Compare an index lookup to a full scan at scale (35 minutes)

A table has 100 million rows. Explain, in general terms, why an index lookup on this table stays fast while a full table scan becomes very slow.

Done when: the explanation correctly ties the search tree's narrowing behavior to a cost that grows far more slowly than the table's size, unlike a full scan.

Hint

The search tree narrows the search in only a handful of steps even as the table grows, while a full scan's cost keeps growing in direct proportion to the row count.

Hard 3: Explain why an index on the wrong column does not help (40 minutes)

A table has an index on customer_id, but a report filters WHERE placed_on = '2026-01-01'. Explain why this index provides no benefit for that specific query.

Done when: the explanation correctly notes the index only maps customer_id values to rows, so a filter on a different, unindexed column still requires a full table scan.

Hint

The index only maps values of the column it was built on to row locations; a condition on an entirely different column gives the index nothing to match against, so a full scan still runs.