A sparse index stores one entry per data block rather than one entry per record. Each entry records a key (typically the last or first key in the block) and the byte offset of that block on disk. This dramatically reduces index size — instead of indexing millions of records, the index only tracks thousands of blocks.

Sparse vs. dense index

A dense index has one entry for every key in the data file. It allows direct lookup of any key but can become very large. A sparse index has one entry per block (or page), requiring the reader to scan within a block after locating it. The tradeoff:

• Dense index: O(log n) lookup where n = number of records. Large index, may not fit in memory.
• Sparse index: O(log B) lookup where B = number of blocks, then O(block_size) scan within the block. Much smaller index, easily fits in memory.

For SSTables, the sparse approach is preferred because data blocks are small (4-64 KB) and scanning a single block is fast. Meanwhile, the index itself stays tiny enough to be cached entirely in memory.

Lookup algorithm

1. Bloom filter — first, check whether the key might exist in this SSTable at all. If the Bloom filter says "definitely not", skip the file entirely.
2. Binary search the sparse index — find the largest index entry whose key is less than or equal to the target key (or the smallest entry whose key is greater than or equal to the target). This identifies the data block.
3. Read and scan the data block — load the block from disk (one I/O operation) and scan sequentially for the target key. Since the block is sorted, you could also binary search within it, though sequential scan is often faster for small blocks due to CPU cache friendliness.

Two-level indexing

For very large SSTables (gigabytes), even the sparse index can become large. A two-level index solves this:

• Top-level index — a small index (fits in memory) that points to index blocks.
• Index blocks — each index block covers a range of data blocks and is itself stored on disk.
• Data blocks — the actual key-value data.

Lookup: binary search the top-level index to find the right index block, read that index block, binary search it to find the right data block, then read and scan the data block. This adds one extra I/O but enables indexing terabyte-scale SSTables.

Index block caching

In practice, frequently accessed index blocks are cached in the block cache (a separate LRU cache from the buffer pool). Since the sparse index is read on nearly every lookup, it has high temporal locality and stays resident in cache. The combination of Bloom filter + cached sparse index means most point lookups require at most one disk read (for the data block).