CSE Roadmap

Common tier · about 2 hours · 5 parts

Part 5 of 5 · 3 min read

Exercises

Easy

Easy 1: Name why B+-trees strain under heavy writes (15 minutes)

State what kind of disk access pattern a B+-tree's in-place updates create under very heavy write load.

Done when: scattered, random page writes are correctly named.

Hint

Scattered, random page writes across disk.

Easy 2: Name what an LSM-tree flush produces (15 minutes)

Name the kind of file produced each time an LSM-tree flushes its in-memory structure to disk.

Done when: an SSTable is correctly named.

Hint

An SSTable.

Easy 3: Name what compaction does (15 minutes)

State, in one sentence, what compaction does to a set of SSTables.

Done when: merging several SSTables into fewer, larger ones, discarding outdated entries, is correctly described.

Hint

It merges several SSTables into fewer, larger ones, discarding entries that have been superseded or deleted.

Medium

Medium 1: Explain why sequential writes are cheaper (25 minutes)

Explain why writing one large sequential file is cheaper than scattering many small random writes across disk.

Done when: the explanation correctly ties this to the random-access cost covered in Level 4's storage media page.

Hint

Sequential writes avoid the repeated random-access cost that scattered small writes impose on disk media, as covered in Level 4.

Medium 2: Explain why an SSTable is never modified (25 minutes)

Explain why an LSM-tree never edits an existing SSTable in place after it is written.

Done when: the explanation correctly notes that SSTables are immutable by design, with updates and deletes instead handled by writing new entries that later get merged during compaction.

Hint

SSTables are immutable by design; changes are handled by writing new entries to newer SSTables, which compaction later merges and reconciles.

Medium 3: Explain why lookups can slow down without compaction (30 minutes)

Explain why a lookup can become slower as more SSTables accumulate without compaction running.

Done when: the explanation correctly notes that a lookup may need to check each SSTable, newest first, until it finds the key, so more SSTables mean more files to check.

Hint

Each additional SSTable is one more file a lookup might have to check, newest first, before finding or ruling out a match.

Hard

Hard 1: Choose between a B+-tree and an LSM-tree for a workload (30 minutes)

A system ingests a very high volume of writes continuously but queries individual records only occasionally. Decide whether a B+-tree or an LSM-tree fits better, and explain why.

Done when: an LSM-tree is chosen, with the explanation correctly citing its cheaper sequential-write cost for a write-dominated workload.

Hint

An LSM-tree, since it turns the heavy write volume into cheap sequential flushes rather than many scattered in-place updates.

Hard 2: Explain the read-side cost of choosing an LSM-tree (35 minutes)

Explain the trade-off a system accepts on the read side by choosing an LSM-tree over a B+-tree.

Done when: the explanation correctly notes that reads may need to check multiple SSTables before compaction has merged them, a cost a B+-tree's single-tree lookup does not have.

Hint

Reads may have to check several SSTables, newest first, until compaction has merged them down, unlike a B+-tree's single, always-current structure.

Hard 3: Trace a key's life from write to compaction (40 minutes)

Trace what happens to one key's value from the moment it is written, through being flushed in an SSTable, to eventually being merged by compaction, assuming the key is updated again before compaction runs.

Done when: the trace correctly shows the key buffered in memory, flushed into an SSTable, a newer value for the same key written into a later SSTable, and compaction eventually merging the files and keeping only the newer value.

Hint

The key's first value is buffered then flushed into an SSTable; its update is buffered then flushed into a later SSTable; compaction later merges both SSTables and keeps only the newer value, discarding the superseded one.