Implement an LSM/B-Tree Range Scan

Problem Implement an ordered key-value store that supports point lookups and range scans. put(key, value) and get(key) handle single keys; scan(lo, hi) returns all keys in [lo, hi] in sorted order.

Input / Output

• Input: a sequence of put, get, and scan(lo, hi) operations.
• Output: get returns the value or absent; scan returns the in-range keys in ascending key order.

Constraints

• Range queries must be efficient (no full scan of the keyspace).
• Discuss how the design changes for a read-heavy vs write-heavy workload.

Example

• put(5,'a'); put(1,'b'); put(9,'c'); scan(2, 9) -> keys [5, 9] in order.