LSM-Tree (日志结构合并树)

     LSM-Tree（日志结构合并树）是一种高效处理写操作的存储结构，广泛应用于NoSQL数据库如LevelDB和RocksDB。其核心思想是将随机写入转换为顺序写入，提升吞吐量。以下是其原理及Java实现示例：

### **LSM-Tree 原理**
1. **结构组成**：
   - **MemTable**：内存中的有序结构（如跳表），用于快速写入。
   - **Immutable MemTable**：MemTable写满后转为只读，准备刷盘。
   - **SSTable（Sorted String Table）**：磁盘上的有序文件，由MemTable刷入生成，多个SSTable分层存储。

2. **写入流程**：
   - 数据先写入MemTable。
   - MemTable满后转为Immutable MemTable，异步刷入磁盘生成SSTable。
   - 磁盘SSTable按层级组织，通过合并（Compaction）消除冗余数据。

3. **读取流程**：
   - 依次查找MemTable、Immutable MemTable和各层SSTable。
   - 使用布隆过滤器减少无效磁盘访问。

4. **合并（Compaction）**：
   - 合并多个SSTable，保留最新数据，减少文件数量，提升读取效率。

---

### **Java 示例代码**
```java
import java.io.*;
import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;

public class LSMTree {
    private ConcurrentSkipListMap<String, String> memTable = new ConcurrentSkipListMap<>();
    private ConcurrentSkipListMap<String, String> immutableMemTable = null;
    private List<File> sstables = new ArrayList<>();
    private static final int MAX_MEMTABLE_SIZE = 1000;

    // 写入数据
    public synchronized void put(String key, String value) {
        memTable.put(key, value);
        if (memTable.size() >= MAX_MEMTABLE_SIZE) {
            switchMemTable();
        }
    }

    // 切换MemTable并刷盘
    private void switchMemTable() {
        immutableMemTable = memTable;
        memTable = new ConcurrentSkipListMap<>();
        flushToSSTable(immutableMemTable);
        immutableMemTable = null;
    }

    // 将数据写入SSTable文件
    private void flushToSSTable(ConcurrentSkipListMap<String, String> data) {
        String filename = "sstable_" + System.currentTimeMillis() + ".txt";
        File file = new File(filename);
        try (BufferedWriter writer = new BufferedWriter(new FileWriter(file))) {
            for (Map.Entry<String, String> entry : data.entrySet()) {
                writer.write(entry.getKey() + "," + entry.getValue());
                writer.newLine();
            }
            sstables.add(file);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    // 读取数据
    public String get(String key) {
        String value = memTable.get(key);
        if (value != null) return value;

        if (immutableMemTable != null) {
            value = immutableMemTable.get(key);
            if (value != null) return value;
        }

        // 从最新SSTable开始查找
        for (int i = sstables.size() - 1; i >= 0; i--) {
            value = searchInSSTable(sstables.get(i), key);
            if (value != null) return value;
        }
        return null;
    }

    // 在SSTable中查找键
    private String searchInSSTable(File file, String key) {
        try (BufferedReader reader = new BufferedReader(new FileReader(file))) {
            String line;
            while ((line = reader.readLine()) != null) {
                String[] parts = line.split(",", 2);
                if (parts[0].equals(key)) {
                    return parts.length > 1 ? parts[1] : null;
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        return null;
    }

    // 合并SSTable文件
    public void compact() {
        if (sstables.size() < 2) return;

        List<File> oldFiles = new ArrayList<>(sstables);
        sstables.clear();
        TreeMap<String, String> mergedData = new TreeMap<>();

        // 按旧到新顺序合并，保留最新值
        for (File file : oldFiles) {
            try (BufferedReader reader = new BufferedReader(new FileReader(file))) {
                String line;
                while ((line = reader.readLine()) != null) {
                    String[] parts = line.split(",", 2);
                    String key = parts[0];
                    String value = parts.length > 1 ? parts[1] : null;
                    mergedData.put(key, value);
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        // 写入新文件并清理旧文件
        String filename = "sstable_merged_" + System.currentTimeMillis() + ".txt";
        File mergedFile = new File(filename);
        try (BufferedWriter writer = new BufferedWriter(new FileWriter(mergedFile))) {
            for (Map.Entry<String, String> entry : mergedData.entrySet()) {
                writer.write(entry.getKey() + "," + entry.getValue());
                writer.newLine();
            }
            sstables.add(mergedFile);
            for (File f : oldFiles) {
                f.delete();
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        LSMTree lsm = new LSMTree();
        // 示例操作
        lsm.put("key1", "value1");
        lsm.put("key2", "value2");
        System.out.println(lsm.get("key1")); // 输出 value1
    }
}
```

### **代码说明**
1. **写入优化**：使用跳表（`ConcurrentSkipListMap`）作为MemTable，写满后转为Immutable并刷盘。
2. **读取流程**：依次检查内存表和SSTable文件，确保获取最新数据。
3. **合并策略**：简单合并所有SSTable，生成新文件并删除旧文件，保留最新键值。

### **优化方向**
- **分层存储**：引入层级结构，每层数据量逐层递增，合并策略更精细。
- **布隆过滤器**：快速判断键是否存在于SSTable，减少IO。
- **索引优化**：为SSTable维护内存索引，加速查找。

LSM-Tree通过顺序写入和定期合并，在高写入场景下表现优异，适合日志系统、时序数据库等应用。