# LSM Tree Compaction Sort

# LSM Tree Compaction Sort

LSM tree compaction sort organizes sorting as a sequence of merges across levels in a Log Structured Merge (LSM) tree. Data is inserted in batches, stored as sorted runs, and periodically merged into larger sorted structures.

Sorting emerges as a byproduct of compaction. Each level maintains sorted order, and merges ensure global ordering across levels.

## Model

Assume:

* data arrives in batches
* memory buffer of size $M$
* disk organized into levels $L_0, L_1, \ldots$
* each level stores sorted runs

Each level is larger than the previous by a factor $T$ (size ratio).

## Core Idea

1. Accumulate records in memory
2. Sort and flush as a run to disk
3. Merge runs across levels when a level exceeds capacity
4. Continue until data stabilizes

Each compaction step merges sorted runs into a larger sorted run.

## Algorithm

```text id="t6y8pq"
lsm_sort(stream):
    mem = empty buffer
    levels = []

    for record in stream:
        insert into mem

        if mem is full:
            run = sort(mem)
            add_to_level(levels, 0, run)
            clear mem

    flush remaining mem
    compact all levels

    return merge_all_levels(levels)
```

Compaction:

```text id="x2k9af"
add_to_level(levels, i, run):
    ensure level i exists

    append run to levels[i]

    if size(levels[i]) exceeds threshold:
        merged = merge(levels[i])
        clear levels[i]
        add_to_level(levels, i + 1, merged)
```

## Example

Suppose memory holds 3 elements and input is:

$$
[8, 3, 5, 1, 9, 2, 7]
$$

### Step 1: Flush runs

* [8, 3, 5] → [3, 5, 8] → level 0
* [1, 9, 2] → [1, 2, 9] → level 0
* [7] → [7] → level 0

### Step 2: Compaction

Level 0 has multiple runs:

merge:

$$
[3,5,8], [1,2,9], [7] \rightarrow [1,2,3,5,7,8,9]
$$

store at level 1

## Correctness

Each flushed run is sorted. Compaction merges sorted runs using a standard merge procedure that preserves order. Each level stores data in sorted form.

When all levels are merged or queried with a merge procedure, the resulting sequence is globally sorted.

No elements are lost or duplicated because compaction only merges existing runs.

## Complexity

Let:

* $N$ be total elements
* $B$ be block size
* $T$ be size ratio between levels

I/O cost:

$$
O\left(\frac{N}{B} \log_T \frac{N}{M}\right)
$$

Each element may be rewritten multiple times during compaction.

CPU cost:

$$
O(N \log k)
$$

per merge, where $k$ is number of runs merged.

## Tradeoffs

| parameter             | effect                                   |
| --------------------- | ---------------------------------------- |
| larger $T$            | fewer levels, more expensive compactions |
| smaller $T$           | more levels, cheaper compactions         |
| aggressive compaction | better read performance                  |
| lazy compaction       | better write throughput                  |

## When to Use

LSM compaction sort is appropriate when:

* data arrives continuously
* write throughput is more important than immediate sorting
* storage is append-friendly
* eventual sorted order is acceptable
* system resembles a database or log store

It is widely used in key-value stores and storage engines.

## Comparison

| method              | behavior                  |
| ------------------- | ------------------------- |
| external merge sort | batch sorting             |
| buffer tree sort    | batched insertion         |
| LSM compaction      | continuous merge and sort |

## Implementation Sketch

```python id="u3k7qn"
import heapq

def merge_runs(runs):
    heap = []
    iters = [iter(r) for r in runs]

    for i, it in enumerate(iters):
        try:
            heapq.heappush(heap, (next(it), i))
        except StopIteration:
            pass

    result = []

    while heap:
        val, i = heapq.heappop(heap)
        result.append(val)
        try:
            heapq.heappush(heap, (next(iters[i]), i))
        except StopIteration:
            pass

    return result
```

```python id="h9q2wr"
def lsm_sort(data, mem_size):
    levels = []
    mem = []

    def add(level, run):
        while len(levels) <= level:
            levels.append([])
        levels[level].append(run)

        if len(levels[level]) > 2:
            merged = merge_runs(levels[level])
            levels[level] = []
            add(level + 1, merged)

    for x in data:
        mem.append(x)
        if len(mem) >= mem_size:
            add(0, sorted(mem))
            mem = []

    if mem:
        add(0, sorted(mem))

    return merge_runs([run for level in levels for run in level])
```

## Notes

LSM tree compaction reframes sorting as a continuous process. Instead of sorting once, data is gradually organized through merges. This approach trades extra write cost for high ingestion throughput and scalability.