Data Blocks: The Unit of I/O

Why not just index every key?

The previous lesson's SSTable stored SMALLEST/LARGEST for the whole file, but a real SSTable can hold millions of entries — an index with one entry per key would itself be enormous, and you'd have to load the whole thing into memory just to find one row. The fix used by every LSM-based store (LevelDB, RocksDB, Cassandra) is to group entries into fixed-size blocks and index the blocks, not the individual keys. A block (commonly 4KB — matching typical filesystem/disk page sizes) becomes the atomic unit of I/O: to read any key inside it, you read the whole block in one disk operation, then binary-search or scan within it in memory.

This is a deliberate trade: a sparse index over ~1000 blocks is small enough to keep entirely in memory, at the cost of reading (and typically decompressing) a whole block just to get one key out of it. That trade is almost always worth it — RAM for a full index doesn't scale, but RAM for a block-per-few-KB index does.

The packing rule

Given entries already in sorted order, you're greedily packing them into blocks up to a byte budget, MAX:

Two rules do all the work here:

1. A block is never empty — even a single oversized entry (bigger than MAX on its own) gets its own one-entry block rather than being rejected or split. Real systems handle genuinely huge values with a separate "large value" path, but for our purposes: one entry always fits in some block, even if that block exceeds the nominal size target.
2. The boundary is inclusive, not exclusive — an entry that brings the running total to exactly MAX still belongs in the current block. Only strictly exceeding the budget forces a new block. This "estimate, then round up to see if it still fits" pattern shows up constantly in systems code (page allocators, network frame packing, buffer pools) — get comfortable reasoning about <= vs < here, because it's the single most common off-by-one in this exercise.

Why this matters beyond just "smaller index"

Blocking has knock-on effects you'll meet again later in the course:

• Compression operates per-block in real systems (Snappy/LZ4/Zstd) — smaller blocks compress worse (less shared structure to exploit) but decompress faster per-read; larger blocks compress better but cost more to touch for a single-key lookup. 4KB is a historically-tuned sweet spot, not an arbitrary number.
• Caching: a block cache (like RocksDB's block cache) evicts and admits at block granularity, not key granularity — so block size directly determines cache hit rates under a given memory budget.
• The block index you'll build next lesson is sized proportional to block count, not entry count — this is the entire reason blocking exists: it turns an O(entries) index problem into an O(entries / block_size) one.

Edge cases

• The very first entry of a fresh block always gets accepted regardless of its own size (rule 1) — don't reject or split a single entry that exceeds MAX on its own.
• Trailing partial block: if the loop ends mid-block, that partial block still needs to be flushed — a common bug is forgetting the final flush() after the loop.
• Getting the "would push over" check backwards (running > MAX instead of running + size > MAX) silently mis-packs every block by one entry — trace through the worked example by hand before trusting your implementation.