Ordered Iteration

A hash map answers "what is the value of k?" in O(1) — and is helpless at "give me every key between a and c." Hashing deliberately scatters keys across buckets, so the only way to answer a range query is to scan the entire table. That is why every serious storage engine keeps keys in sorted order somewhere:

• Skip list — LevelDB's and RocksDB's memtable structure: probabilistically balanced, cheap concurrent inserts.
• B-tree / B+ tree — Postgres, InnoDB, BoltDB: deterministic balance, page-friendly.
• Sorted run — an SSTable is nothing but a sorted array written to disk.

Sorted keys turn a range query into: find the start in O(log n), then walk forward for the k results you want — O(log n + k) total. Sorted order is also the precondition for the LSM machinery ahead: you cannot merge SSTables in linear time unless each one is already sorted.

Half-open intervals

SCAN start end returns keys with start <= key < end — inclusive start, exclusive end. Half-open ranges compose without gaps or double-counting: SCAN a m plus SCAN m z covers exactly SCAN a z, with m appearing once. Closed intervals cannot be stitched like that.

A prefix scan is a range scan in disguise: every key starting with user: lies in the range ["user:", "user;"), because ; is the very next byte after :. Storage engines without a native PREFIX operator use exactly this trick.

The output contract

The Python idiom (fine at this scale — real engines keep a sorted structure instead of re-sorting on every query):

PREFIX p is the same loop with k.startswith(p) as the filter. Both commands terminate their output with a single blank line — even when nothing matched, in which case the blank line is the entire output. LIST, by contrast, prints the sorted key=value pairs with no trailing blank line. Getting these terminators backwards is the classic failure in this exercise.

Your exercise

Implement PUT, SCAN, PREFIX, and LIST. The grader-caught mistakes, from the real tests: (1) the exclusive bound — after putting a, b, c, the command SCAN a c prints a=1 and b=2 then the blank line; printing c=3 fails the visible test; (2) the empty result — with only keys k1 and k2 stored, SCAN m z must output just one blank line (the hidden test expects OK, OK, then an empty line), and PREFIX zzz behaves the same; (3) overwrites — PUT a 1 then PUT a 2 followed by SCAN a b prints a=2 once, never two lines for one key.