LSM Log-Structured Merge
LevelDB，HBase，Google BigTable，Cassandra，InfluxDB 

将大量的随机写转换为顺序写，提升写性能
写优化

WAL write ahead log
顺序写 持久化 挂掉重启后 使用 WAL恢复数据

MemTable  
通常用 SkipList 实现

Immutable Memtable 
内存中只读的 MemTable
避免将 MemTable 中的内容序列化到磁盘时阻塞写

SSTable
MemTable 中的数据在磁盘上的有序存储
为了加速查找 加入索引

index   
key offset  快速定位到指定的 k-v 数据。

合并 

更新操作
多个 SSTable ，存在多个 相同的 key 
合并时删除过期的值

删除  删除标记  合并时才做物理删除


Compaction
多个 SSTable 合并 

分级合并

读取效率不高
MemTable   
Immutable Memtable 
多级sstable

读取优化
LevelDB  Mainfest 文件
记录SSTable 文件的一些关键信息 Level 层数，文件名，最小 key 值，最大 key 值等


布隆过滤器(Bloom filter)
可以判断key一定不在集合中， 避免无效的查找

时间序列数据库