Storage engines: rows, LSM trees, B-trees
Every storage engine decides when to pay for sorted order: on each write, in the background, or on every read. Say which one the prompt can afford, and the engine follows.
Problems worked on this page, and more to practise
When should I choose an LSM tree over a B-tree?
When writes dominate and most of them are blind, meaning the write does not need to read the old value first. An LSM turns every write into a memory insert and later a sequential file write, so it takes far more writes per disk than a B-tree, which rewrites a whole page for each small change. The price is paid on reads: a key may have to be looked for in several runs, and merges rewrite data in the background. For a read-heavy table with occasional updates, a B-tree answers every lookup from one page and is the better default.
What are read, write and space amplification?
They are the three ratios a storage engine trades against each other. Write amplification is how many bytes reach the disk for each byte the application writes; merges and page rewrites raise it. Read amplification is how many places a read must look, such as the number of runs an LSM asks for one key. Space amplification is how much more disk is used than the live data needs, for example old versions waiting for a merge. No engine minimises all three, and naming which one the prompt can afford is the decision.
Why does an LSM tree need tombstones to delete a key?
Because the runs on disk are never edited. The old value of the key sits in some older run, and the only way to hide it is to write a newer entry that says the key is gone, which is the tombstone. A read that finds the tombstone first stops there. The tombstone itself can only be dropped by a merge that includes the oldest run, because until then an older copy may still exist below it.
What is compaction, and what does it cost?
Compaction merges several sorted runs into one, keeping only the newest version of each key and dropping tombstones when it is safe. It keeps reads short, because fewer runs means fewer places to look. It costs disk bandwidth, because every surviving entry is read and written again. Size-tiered compaction rewrites each byte about once per tier and leaves several runs per tier; leveled compaction keeps one run per level, which is cheaper to read and several times more expensive to write.
How do I delete old data from a time-series store cheaply?
Cut the data into runs by time window, one run per window, and delete a whole run when its window falls out of the retention period. Removing a file costs nothing per point, where deleting point by point would write one tombstone per point and then pay a merge to remove them. The trade-off is granularity: a merged run can only be dropped when its newest point expires, so larger runs hold data a little past the retention.