LSM-Tree 的结构与写入流程
哪些公司问过
答案要点
- 写入先顺序追加 WAL,再写入内存有序结构 MemTable(常用跳表)
- 更新和删除都是追加写,删除写入墓碑标记
- MemTable 满后转为只读,后台刷成磁盘上有序且不可变的 SSTable
- 后台 Compaction 分层合并,清理旧版本与墓碑,代价是写放大
- 值分离(如 WiscKey)在 LSM 中只存 key 和值位置,大 value 写入值日志
易错点
- 认为 LSM 写入会原地更新磁盘上的数据
- 忽略 L0 文件之间 key 范围可能重叠
- 以为删除会立即释放空间,忽略墓碑要等 Compaction 清理
- 只讲写入快,不讲读放大、写放大和空间放大的权衡
面试官常见追问
- LSM 树的读取过程是怎样的?
- 为什么要用 WAL,如何保证一致性?
- Leveled 和 Tiered 合并策略有什么区别?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。