LSM Tree

mutable 和 immutable 数据结构

不可变的数据结构有一个巨大的优势：可压缩，更新的时候不需要预留额外空间（不在原地更新，原地更新更大的数据会引发重分配，需要进行碎片整理）

使用顺序写，append-only 是保持数据结构的不可变性的秘诀

不同的数据库对于不可变数据结构读写会有不同的实现方式 有的数据库会把旧数据设置为过期或者设置删除标志，但是触发清理的时候可能会大大降低读写的性能

不可变读写文件的时候不需要加 segment lock 进行保护，大大简化了并发访问的锁。随着顺序写的文件大小不断增大，需要对文件群进行合并和重写，会有专门的进程对数据进行清理防止性能下降

LSM 是可变结构，常见的 B 树及其变种是不可变结构

log structure merge tree

为磁盘顺序读而优化，节点可以全部被数据占用。 允许不可变的可合并的文件 只是概念，并不是具体的实现

Sorted string table

SSTable 是一种有序的不可变字典，专门为顺序读写而优化 原地修改会导致文件重写