An SSTable here is an array of { key, value } sorted ascending, with
tombstones as { key, deleted: true }. Four functions.
What to implement
buildSparseIndex(table, every) — one entry every n records. Always
include the first, or a lookup has no lower bound to start from.
sparseGet(table, index, key) — find the last index entry at or below the
target, then scan forward. Stop the moment you read a key greater than the
target: in sorted data, passing it proves it is not there. A test counts record
reads, so scanning the whole table fails even though it returns the right
answer.
mergeTables(tables, dropTombstones) — merge sorted tables into one.
tables is ordered oldest first, so a later table wins a duplicate key. Stream
it: one cursor per table, repeatedly take the smallest key. Concatenating
everything and sorting produces the right output and defeats the purpose — the
point is that a merge never needs more memory than one entry per table, which is
how engines merge files far larger than RAM.
rangeScan(table, index, startKey, endKey) — live keys in [start, end),
starting from the index rather than from zero.