SSTable Iterators: Seek & Next

SSTable Iterators: Seek & Next

A single SSTable is a sorted, immutable file of key-value pairs. To support range scans and to be a building block for the multi-source merge iterator you'll write next, an SSTable needs to expose an iterator interface with two primitive operations: Seek(key) and Next(). This lesson is about implementing those primitives correctly and efficiently against sorted, static data.

The interface

• Seek(k) — position an internal cursor at the first entry whose key is >= k. This is how a range scan [start, end] begins: seek to start, then repeatedly call Next until you pass end.
• Next() — advance the cursor by one entry and return the new current entry, or signal "exhausted" if there are no more entries.

Because the SSTable is sorted and immutable, Seek doesn't need to scan linearly — it can binary search the key array, which is exactly why SSTables store an in-memory (or block-level) sparse index of keys: it turns Seek into O(log n) instead of O(n).

bisect_left is the right primitive here: it returns the insertion point that keeps the list sorted and, critically, lands on the first occurrence of target if it's present — which matches the "first entry >= k" semantics Seek needs.

Cursor state and edge cases

A few edge cases separate a correct iterator from a subtly broken one:

• Seeking past the end. If target is greater than every key in the table, bisect_left returns len(data) — the cursor is now "at end," and both Seek and any subsequent Next must report exhaustion rather than indexing out of bounds.
• Next before any Seek. An iterator with no defined starting position shouldn't silently assume "start from the beginning" — that's an easy source of bugs where a caller forgets to seek first and gets data from the wrong logical position. Treat the cursor as invalid until explicitly positioned.
• Repeated Next after exhaustion. Once the cursor is past the last entry, further Next calls must keep reporting "end" rather than wrapping around or throwing — callers (like the merge iterator later) will call Next in a loop and rely on this being stable.
• Scan(start, end) is just sugar over Seek + Next. A full range scan is: binary-search to start, then walk forward with Next-like iteration until the key exceeds end. Implementing it directly (rather than literally calling your Seek/Next functions) is fine for the exercise, but notice it's the same logic — this is intentional, because in the real system, Scan is built on top of Seek/Next.

Why this shape, and where it's going

Every SSTable in your LSM tree will expose exactly this iterator interface, and nothing above it — the merge logic in the next lesson, compaction's k-way merge, and any range query all consume SSTables purely through Seek/Next, never by reading the whole file into memory. That uniformity is what lets you plug an arbitrary number of SSTables (across levels, across compaction inputs) into the same merge algorithm without special-casing "is this the memtable or a file on disk." Get the single-source iterator right here, and the multi-source version is just a heap of these.