The Block Index & Footer

The index is what makes an SSTable searchable. Without it, a point lookup would require scanning the whole file.

Layout

[ data blocks ... ][ index block ][ bloom filter ][ footer ]
                                                  ^------ fixed size, last bytes

The footer is fixed-size (LevelDB: 48 bytes). To open an SSTable: stat the file, seek to size - 48, read the footer. The footer tells us where the index and the bloom filter live.

Index Block

The index is itself a block: one entry per data block, sorted by key.

{ separator_key -> data_block_offset, data_block_size }

separator_key is "the smallest key that is >= every key in the data block AND < the smallest key of the next block." A common shortcut: use the first key of each data block. LevelDB uses a shorter synthetic separator (the shortest string s with prev_block.last_key < s <= next_block.first_key) to keep the index compact.

Point Lookup

Total cost: at most 2 disk reads (index block + one data block). If the index is cached, just 1 disk read. With a bloom filter in front (Ch 4), zero reads for misses.

Footer Magic Number

Every SSTable footer ends with a magic number (LevelDB: 0xdb4775248b80fb57). It's how the engine validates "is this a real SSTable, or did someone hand us a JPEG?" If the magic is wrong, the file is rejected without further parsing.

Sealing Order

When writing an SSTable, the engine writes in this order:

1. Data blocks (streaming, in sorted order)
2. Compute and write the bloom filter (knows all keys after data is done)
3. Compute and write the index (knows all block offsets)
4. Write the footer
5. fsync() once at the end

If the system crashes before step 5 completes, the file is incomplete and is deleted on recovery (the live SSTable list — the MANIFEST in LevelDB — only references SSTables whose footers were known-good).

The Manifest

What lists which SSTables are live? A separate metadata file: the MANIFEST (LevelDB/RocksDB), or the VERSION SET. It's the catalog of which SSTables exist at which level, plus current sequence numbers. The manifest is itself appended-to and periodically rewritten — a tiny LSM in its own right.