CSE Roadmap

Common tier · about 2 hours · 5 parts

Part 3 of 5 · 1 min read

Buffering writes in memory, then flushing sequentially

Writes accumulate in memory and are flushed as one large, sorted, sequential file.

Think of a cashier handling receipts. Instead of re-filing each one into a sorted drawer right away, the cashier drops receipts into a tray all day, then sorts and files the whole tray in one pass at closing time.

In plain words: a log-structured merge-tree, or LSM-tree, buffers incoming writes in memory first, in a sorted in-memory structure, rather than modifying an on-disk page immediately. Once that in-memory structure grows large enough, its entire contents are written to disk in one pass, as a single new sorted file. Writing one large sequential file is far cheaper than scattering many small random writes, which is the central trade an LSM-tree makes compared to a B+-tree.

A worked example. The sensor-logging system from the earlier example buffers a batch of readings in memory, then flushes that whole batch to disk as one sequential file, instead of updating many scattered index pages.

The key lines. No new SQL; this buffering and flushing happens inside the storage engine automatically.

LSM-tree

An LSM-tree (log-structured merge-tree) buffers writes in a sorted in-memory structure and periodically flushes that structure to disk as a single new sorted file, trading scattered random writes for large sequential ones.

Example: the cashier's end-of-day batch filing, done once in a sorted pass rather than constantly re-filing one receipt at a time, mirrors an LSM-tree's flush.