CSE Roadmap

Core tier · about 3 hours · 5 parts

Part 5 of 5 · 3 min read

Exercises

Easy

Easy 1: Name the ordering property (15 minutes)

State whether a B+-tree's keys are stored in sorted order or in arbitrary order across its leaf nodes.

Done when: sorted order is correctly named.

Hint

Sorted order.

Easy 2: Name what links leaves together (15 minutes)

Name the structure that links a B+-tree's leaf nodes together in sorted order.

Done when: the leaf chain is correctly named.

Hint

The leaf chain.

Easy 3: Name what happens to a full leaf (15 minutes)

State what happens when a new key must be inserted into an already-full leaf node.

Done when: a leaf split, dividing entries roughly in half, is correctly described.

Hint

The leaf splits into two leaf nodes, each holding roughly half the original entries.

Medium

Medium 1: Explain why ordering helps range queries (25 minutes)

Explain why a B+-tree's sorted leaf order makes a range query such as a BETWEEN clause efficient.

Done when: the explanation correctly ties efficiency to finding the range's start once, then following the leaf chain forward.

Hint

The range's start is found once via the tree, then the rest of the matching rows are read by walking the leaf chain forward.

Medium 2: Distinguish internal nodes from leaf nodes (25 minutes)

Explain the difference in what internal nodes store compared to what leaf nodes store in a B+-tree.

Done when: internal nodes are correctly described as routing-only, with leaf nodes correctly described as holding the actual key and row-pointer entries.

Hint

Internal nodes hold only keys and child pointers for routing; leaf nodes hold the real key and row-pointer entries.

Medium 3: Trace a split propagating upward (30 minutes)

Describe what happens if, after a leaf split adds a new key to its parent internal node, that parent node is also already full.

Done when: the description correctly shows the split propagating one level higher, splitting the parent node too.

Hint

The parent node splits too, adding a new key one level higher, which can keep propagating upward if that level is also full.

Hard

Hard 1: Explain why the tree stays balanced (30 minutes)

Explain why a B+-tree's leaves all stay at the same depth from the root, even after many years of inserts.

Done when: the explanation correctly ties this to splits propagating upward whenever a node fills, rather than any leaf being allowed to grow deeper than the others.

Hint

Every split happens by dividing a full node and promoting one key upward, which keeps every leaf the same number of levels from the root rather than letting one branch grow deeper.

Hard 2: Compare a lookup cost before and after many splits (35 minutes)

A table starts with a few thousand rows and a shallow B+-tree, then grows to a hundred million rows over several years, with many leaf splits along the way. Explain why a single lookup's cost grows only slightly, not in direct proportion to the row count.

Done when: the explanation correctly notes the tree's depth grows very slowly (logarithmically) as splits propagate, so a lookup only needs a few more levels of traversal even at vastly larger size.

Hint

A B+-tree's depth grows logarithmically with the number of rows, so going from thousands to a hundred million rows adds only a few extra levels to traverse.

Hard 3: Explain why range scans avoid retraversing the tree (40 minutes)

Explain, step by step, why a range scan covering a thousand matching rows does not need to walk down from the root a thousand times.

Done when: the explanation correctly describes finding the range's starting leaf once via the internal nodes, then reading the remaining matching rows purely by following the leaf chain forward.

Hint

The internal nodes are used once to locate the first matching leaf; every subsequent matching row is reached purely by following the leaf chain's pointers forward, with no further tree traversal needed.