LSM-treeLog-structured merge

将写入积累后批量生成有序文件，后台逐步合并。

有序归并示意：输入已排序；归并排序还需从原始输入建立有序段，可递归划分或自底向上合并。

常见操作#

L 为磁盘层数，r 为实际访问的 sorted runs 数，k 为输出记录数；参数依压实策略变化。

操作	时间复杂度	条件与说明
写入	WAL 追加 + MemTable 更新	以启用 WAL 的持久化路径为例，配置可关闭 WAL；内存结构、刷盘和后续 compaction 工作也须计入。
点查找	过滤器检查 + 候选文件索引 / 数据块读取	层数、L0 文件重叠、Bloom 误判和缓存命中共同决定读放大。
范围扫描	定位各路起点 + 多路有序归并	访问 r 路候选时，每个输出可有 $O(\log r)$ 堆维护；墓碑和旧版本可能带来额外扫描。
删除	写入墓碑，稍后压实回收	逻辑删除并不立即释放全部磁盘空间。
压实	读取、归并并重写参与的文件	成本取决于读取 / 重写字节数与比较次数；应同时报告读、写和空间放大。