2、leveldb设计原理--LSM

概念

LSM（Log-Structured Merge Tree）

原理

特点

• 把随机写转化成顺序写，写入速度快；
• 读数据可能需多次磁盘IO；

数据操作流程

写数据

1. 追加写WAL日志；
2. 更新内存中的MemTable结构；

读数据

1. 尝试从MemTable中查询数据，如找到即返回；未找到则到下一层中去查找；
2. 尝试从InmemTable中查找数据；
3. 尝试从level0层的SSTable文件中查找数据；
4. 使用二分法从levelN层的SSTable文件中查询数据；
5. 如都未查找到数据，则返回数据不存在；

数据合并（compaction）