1
package lsm
2

3
import "sort"
4

5
// KVEntry 键值条目，Value 为 nil 表示墓碑（已删除）
6
type KVEntry struct {
7
    Key   string
8
    Value *string // nil = tombstone
9
    Seq   int     // 序列号，越大越新
10
}
11

12
// Memtable 内存有序表，写入的第一站
13
type Memtable struct {
14
    entries map[string]KVEntry
15
    size    int
16
}
17

18
func NewMemtable() *Memtable {
19
    return &Memtable{entries: make(map[string]KVEntry)}
20
}
21

22
func (m *Memtable) Put(key, value string, seq int) {
23
    m.entries[key] = KVEntry{Key: key, Value: &value, Seq: seq}
24
    m.size++
25
}
26

27
func (m *Memtable) Delete(key string, seq int) {
28
    m.entries[key] = KVEntry{Key: key, Value: nil, Seq: seq}
29
    m.size++
30
}
31

32
// Flush 将 memtable 刷写为有序段
33
func (m *Memtable) Flush() []KVEntry {
34
    result := make([]KVEntry, 0, len(m.entries))
35
    for _, e := range m.entries {
36
        result = append(result, e)
37
    }
38
    sort.Slice(result, func(i, j int) bool {
39
        return result[i].Key < result[j].Key
40
    })
41
    m.entries = make(map[string]KVEntry)
42
    m.size = 0
43
    return result
44
}
45

46
// LSMTree 简化的 LSM 树实现
47
type LSMTree struct {
48
    memtable       *Memtable
49
    runs           [][]KVEntry // L0 有序段，新在前
50
    seq            int
51
    flushThreshold int
52
    maxRuns        int
53
}
54

55
func NewLSMTree(flushThreshold, maxRuns int) *LSMTree {
56
    return &LSMTree{
57
        memtable:       NewMemtable(),
58
        flushThreshold: flushThreshold,
59
        maxRuns:        maxRuns,
60
    }
61
}
62

63
func (t *LSMTree) Put(key, value string) {
64
    t.memtable.Put(key, value, t.seq)
65
    t.seq++
66
    if t.memtable.size >= t.flushThreshold {
67
        t.flushMemtable()
68
    }
69
}
70

71
func (t *LSMTree) Get(key string) (string, bool) {
72
    // 先查 memtable
73
    if e, ok := t.memtable.entries[key]; ok {
74
        if e.Value == nil {
75
            return "", false // 墓碑
76
        }
77
        return *e.Value, true
78
    }
79
    // 再查有序段（从新到旧）
80
    for _, run := range t.runs {
81
        if e := binarySearch(run, key); e != nil {
82
            if e.Value == nil {
83
                return "", false
84
            }
85
            return *e.Value, true
86
        }
87
    }
88
    return "", false
89
}
90

91
func (t *LSMTree) flushMemtable() {
92
    run := t.memtable.Flush()
93
    t.runs = append([][]KVEntry{run}, t.runs...)
94
    if len(t.runs) > t.maxRuns {
95
        t.compact()
96
    }
97
}
98

99
func (t *LSMTree) compact() {
100
    merged := make(map[string]KVEntry)
101
    // 从旧到新遍历，新值覆盖旧值
102
    for i := len(t.runs) - 1; i >= 0; i-- {
103
        for _, e := range t.runs[i] {
104
            merged[e.Key] = e
105
        }
106
    }
107
    // 过滤墓碑并排序
108
    result := make([]KVEntry, 0)
109
    for _, e := range merged {
110
        if e.Value != nil {
111
            result = append(result, e)
112
        }
113
    }
114
    sort.Slice(result, func(i, j int) bool {
115
        return result[i].Key < result[j].Key
116
    })
117
    if len(result) > 0 {
118
        t.runs = [][]KVEntry{result}
119
    } else {
120
        t.runs = nil
121
    }
122
}

1
// 键值条目，value 为 null 表示墓碑
2
interface KVEntry {
3
  key: string;
4
  value: string | null; // null = tombstone
5
  seq: number;
6
}
7

8
// 简化的 LSM 树
9
class LSMTree {
10
  private memtable = new Map<string, KVEntry>();
11
  private runs: KVEntry[][] = []; // L0 有序段
12
  private seq = 0;
13

14
  constructor(
15
    private flushThreshold = 4,
16
    private maxRuns = 4,
17
  ) {}
18

19
  put(key: string, value: string): void {
20
    this.memtable.set(key, { key, value, seq: this.seq++ });
21
    if (this.memtable.size >= this.flushThreshold) {
22
      this.flushMemtable();
23
    }
24
  }
25

26
  get(key: string): string | undefined {
27
    // 先查 memtable
28
    const memEntry = this.memtable.get(key);
29
    if (memEntry) return memEntry.value ?? undefined;
30
    // 再查有序段
31
    for (const run of this.runs) {
32
      const entry = this.binarySearch(run, key);
33
      if (entry) return entry.value ?? undefined;
34
    }
35
    return undefined;
36
  }
37

38
  private flushMemtable(): void {
39
    const sorted = [...this.memtable.values()].sort(
40
      (a, b) => a.key.localeCompare(b.key),
41
    );
42
    this.runs.unshift(sorted); // 新段在前
43
    this.memtable.clear();
44
    if (this.runs.length > this.maxRuns) this.compact();
45
  }
46

47
  private compact(): void {
48
    const merged = new Map<string, KVEntry>();
49
    // 从旧到新，新值覆盖旧值
50
    for (let i = this.runs.length - 1; i >= 0; i--) {
51
      for (const entry of this.runs[i]) {
52
        merged.set(entry.key, entry);
53
      }
54
    }
55
    const compacted = [...merged.values()]
56
      .filter((e) => e.value !== null) // 移除墓碑
57
      .sort((a, b) => a.key.localeCompare(b.key));
58
    this.runs = compacted.length > 0 ? [compacted] : [];
59
  }
60
}