In this lesson, you will learn how the structural differences between B-Trees and LSM-trees dictate their unique approaches to maintaining data durability during updates.
The B-Tree In-Place Update Model
B-Trees are designed for in-place updates. When you modify a record, the storage engine locates the specific page on disk where that data resides, loads it into memory, modifies it, and eventually writes it back to the same physical location.
Because this is a random-access pattern, durability is achieved through the Write-Ahead Log (WAL). Before the page is modified in place, the engine must flush the change to the sequential WAL. If the system crashes mid-write, the engine uses the WAL to ensure the page is consistent upon restart. The trade-off here is high I/O overhead due to the need for random writes and full-page writes to avoid "torn pages."
The LSM-Tree Append-Only Model
In contrast, Log-Structured Merge-Trees (LSM-trees) treat updates as immutable events. An LSM-tree never modifies an existing file on disk. Instead, when an update occurs, it is appended to an in-memory structure (the MemTable) and later flushed to a new, sorted file on disk called an SSTable (Sorted String Table).
-- Conceptual update flow:
-- LSM-tree appends a new version (tombstone or new value)
INSERT INTO kv_store VALUES ('key1', 'new_value_v2');
Durability in an LSM-tree is inherently tied to the sequential nature of its logs. Because every write is an append, the storage engine minimizes random I/O. Durability is maintained by ensuring the MemTable is backed by a WAL, but the "update" itself becomes a background process (compaction) that merges these immutable files over time.
Durability Comparison
- B-Trees focus on state consistency. They protect the "truth" of the current page through complex mechanisms like double-write buffers and WALs to ensure an in-place update isn't corrupted during a power failure.
- LSM-trees focus on log integrity. They treat the stream of updates as the primary durable record. Because files are immutable, the engine simply needs to ensure the append-only logs are flushed to persistent storage before acknowledging a commit.
Key Takeaway: While B-Trees provide durability by protecting the integrity of existing disk pages via WALs, LSM-trees achieve durability by treating all updates as immutable, sequential appends that are later reconciled through background merges.