LSM树用内存表加WAL兼顾写入速度与崩溃安全

要让传入写入首先满足[[SSTable按键排序换来高效合并与稀疏内存索引]]要求的”按键排序”， 最实际的办法是先在内存里维护一棵平衡树（如红黑树，称为内存表memtable）——插入 可以任意顺序，读取时天然按排序顺序输出。完整流程是：写入先加入内存表；内存表长大 超过阈值（通常几兆字节）后，把它整体高效地写成一个新的SSTable文件（因为树里的数据 已经是排序好的），随后新的写入切换到一个新的内存表实例；读取时依次查内存表、最近的 磁盘段、再下一个较旧的段；后台不断运行合并和压缩流程，组合段文件、丢弃被覆盖或 删除的值。这个方案唯一的弱点是：如果数据库崩溃，内存表里尚未落盘的最近写入会丢失。 解法是额外维护一份磁盘上的预写式日志（WAL）：每次写入立即被追加到这份日志（不要求 排序，它唯一的用途是崩溃后重建内存表），一旦对应的内存表已经成功写成SSTable，这份 日志就可以被丢弃。这套算法正是LevelDB、RocksDB以及受Google Bigtable启发的Cassandra、 HBase等存储引擎（统称LSM树，日志结构合并树）的核心思路：即使数据集远大于可用内存 依然能正常工作，因为数据按排序存储所以范围查询高效，又因为磁盘写入始终是连续的 所以能支持很高的写入吞吐量。

结构图：

flowchart TD
    A[写入请求] --> B[追加到WAL: 未排序, 仅用于崩溃恢复]
    A --> C[写入内存表memtable: 排序的平衡树]
    C -->|超过阈值大小| D[整体写成新SSTable文件]
    D --> E[切换到新内存表实例]
    D -->|落盘成功| F[对应WAL可丢弃]
    G[读取请求] --> H[先查内存表]
    H --> I[再查最近的磁盘SSTable段]
    I --> J[依次查更老的段]
    K[后台合并压缩流程] -.持续组合段文件, 丢弃覆盖/删除的值.-> I