SST Files

Build your understanding from first principles

Section 1 of 7

The Problem

Why not just append to a file?

data.log

(append-only)

000:banana="yellow fruit"(oldest)

001:apple="red fruit"

002:cherry="small red fruit"

003:date="brown sweet fruit"

004:apple="green fruit (updated!)"(newest)

Append:=

Just append data to a file. Every write adds a new line to the end. Fast for writes — but finding data is the problem.

To find a key, scan from the end backwards. Worst case: scan the entire file.

Search for a key:

Key Insight

Append-only logs are O(n) for reads — we scan linearly. With 1 million entries, we might scan all 1 million just to find one key. We need a better way to organize data for faster lookups.

What if we sorted the data? Then we could use binary search...

Loading section...