Key-Value Store With Prefix Scan

Build a small key-value store with a range-style query:

put(key, value)
get(key)        -> value, or null
delete(key)     -> true if the key existed
scan(prefix)    -> every key starting with prefix, in sorted order

Keys are strings; scan("") lists every key. Keep point operations fast and make scan proportional to the number of matching keys plus a logarithmic search, not to the size of the store.

put("a", 1) · put("ab", 2) · put("b", 3)
scan("a")  ->  ["a", "ab"]      get("zzz")  ->  null      delete("a")  ->  true