Building SaarDB Part 2: Why LSM Trees Replace WAL for Disk Storage

SaarDB's initial design relied on a Write Ahead Log (WAL) and an in-memory map, but this approach hits two key limits as data grows: the in-memory map is bounded by RAM, and replaying a large WAL on every restart becomes increasingly slow. The WAL also accumulates stale values for the same key, wasting space and complicating reads. Reading directly from the WAL during lookups is equally problematic, since entries are unsorted and finding the latest value for a key requires a full linear scan. To solve this, the author proposes moving older data from memory to disk in a structured, searchable format — but variable-length entries make binary search on disk non-trivial. This sets the stage for adopting Log-Structured Merge (LSM) trees as the solution to efficient on-disk key-value storage.