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 run, applying overrides and tombstones.

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"}]