The Block Index & Footer

The sparse index: one entry per block, not per key

Now that your data is chunked into blocks (previous lesson), you need a way to find which block a given key would live in without scanning the file. The answer is a sparse index: a small in-memory table with one entry per block — its smallest key, largest key, and its size/offset on disk. Because it's one entry per block rather than per key, this index is small enough to keep entirely in memory even for a multi-gigabyte SSTable, and it's exactly what real systems (LevelDB's Footer/IndexBlock, RocksDB's index block) load eagerly when a file is opened.

BLOCK <smallest> <largest> <size>
BLOCK <smallest> <largest> <size>
...

Because the source data was written in sorted order and blocks were filled sequentially, this list of blocks is itself sorted and non-overlapping by construction — block i's largest key is always less than block i+1's smallest key. That invariant is what makes binary search valid here.

Binary search over block ranges

The standard technique: keep a parallel array of each block's smallest key, and use bisect_right to find the last block whose smallest key is <= the query key — that's the only block that could possibly contain it, given the non-overlapping invariant.

Why bisect_right and not bisect_left? Because you want the rightmost block whose start is still <= your key — bisect_right gives you the insertion point just past any equal elements, so subtracting 1 lands you on the last block that could start at or before the query key. If idx comes out negative, the query key is smaller than every block's smallest key — an automatic miss, no further check needed.

Once you have a candidate, you still have to verify it — landing in the right slot by binary search doesn't guarantee the key is actually inside that block's range (it might fall in the gap between two blocks, which is exactly the MISS case):

Why this two-step (locate candidate, then verify) matters

This mirrors exactly how a real SSTable reader works end to end:

1. Binary search the in-memory index to find a candidate block — O(log(number of blocks)), no disk I/O.
2. Verify the range, and only if it's a genuine hit, read that one block from disk (a single I/O, decompress if needed) and scan or binary-search within it for the exact key.

The footer of a real SSTable is what ties this all together on disk: it's a small fixed-format trailer at the end of the file (a known, fixed-size region so a reader can always find it without scanning) that points to where the index block itself lives, plus (later in this course) a pointer to the bloom filter. Opening an SSTable means: read the footer, load the index into memory, and you're ready to serve lookups — the multi-gigabyte data section itself is never touched until a specific block is actually needed.

Edge cases

• A query key that falls in the gap between two blocks' ranges (larger than one block's largest, smaller than the next block's smallest) is a legitimate MISS — this is the case the two-step verify exists to catch, since binary search alone would still return some candidate index.
• A query smaller than the very first block's smallest, or larger than the very last block's largest, must also resolve to MISS rather than an index error — check bounds before indexing into blocks.
• Because ranges are non-overlapping and sorted, there's never a need to check more than one candidate block — if this invariant were ever violated (e.g., overlapping blocks from a buggy writer), a single binary search would no longer be sufficient for the correctness guarantee.