SSTable Iterators: Seek & Next

A point lookup only needs a single key. Range queries (SELECT * WHERE id BETWEEN 100 AND 200) need to walk through many keys in order. The LSM engine exposes an iterator over each SSTable; the merge iterator (next lesson) walks them all in lock-step.

The Iterator API

This API is the contract that LevelDB, RocksDB, and BadgerDB all expose. Range queries are built on top of it.

Seek Implementation

Within an SSTable, seek(k) is two binary searches:

1. Binary search the index for the data block whose range covers k.
2. Read that block (from cache or disk).
3. Binary search within the block to find the smallest key >= k.

Cost: typically one cache check or one disk read. The iterator then walks forward via next() until it leaves the block, at which point it loads the next block.

Block Iterators

Inside a block, entries with prefix compression can't be random-accessed — the unshared bytes need the previous key for context. Solution: restart points every N entries (LevelDB default: N=16). The block trailer holds an array of restart offsets; binary search jumps to the nearest restart, then linear-walks forward.

block layout:
  entry 0 (full key)           <- restart 0
  entry 1 (prefix-compressed)
  ...
  entry 15 (prefix-compressed)
  entry 16 (full key)          <- restart 1
  ...

Range Scan Cost

A range scan over [start, end] on a single SSTable:

• 1 seek (1 disk read worst case)
• Walk forward, possibly reading additional blocks as we exit each one
• Stop when current key > end

For a long range, we read every block that overlaps the range. For 1 GB range with 4 KiB blocks, that's 256K block reads — but they're sequential, so the OS readahead pulls them in batches at near-bandwidth speeds.

Snapshot Iterators

A snapshot iterator pins a sequence number. For each visited key, it returns the largest version with seq <= snapshot. Multiple versions of the same key are visited as the iterator walks the underlying entries; it must skip versions newer than the snapshot.

Reverse Iteration

Going backward is harder: prefix-compressed blocks need to be decoded forward to materialize each key. RocksDB's reverse iteration is significantly slower than forward (typically 2-3x). For applications that need backward scans, choosing a key encoding that scans forward (e.g. reversed timestamps for "newest first") is the optimization.