LSM Compaction Merge

An LSM tree periodically compacts two sorted runs. The newer run overrides entries from the older run with the same key. Tombstones (Deleted=true) remove keys.

Given two runs sorted by key ascending:

• newer (higher priority)
• older

Merge them into a single sorted value-only result, applying overrides and tombstones. Each input has unique keys. These are the complete history: no overlapping versions, snapshot requirements, or stale replica copies remain outside the two runs. Under that assumption a winning tombstone and its older value can both be omitted. For a partial compaction, deletion markers would need to be retained. The later multi-way exercise returns a stored run and models marker retention. Do not mutate the inputs.

Types

type Entry struct {
    Key     string
    Value   string
    Deleted bool
}

Function signature

func CompactRuns(newer []Entry, older []Entry) []Entry

Example

newer = [{Key:"b", Value:"2"}, {Key:"c", Deleted:true}]
older = [{Key:"a", Value:"1"}, {Key:"c", Value:"3"}]

output = [{Key:"a", Value:"1"}, {Key:"b", Value:"2"}]