《大规模分布式计算深入解析》2.3 LSM 点查与扫描

分开点查过滤和范围扫描的归并成本。

分开点查过滤和范围扫描的归并成本。

实现机制

点查按序号和 key 范围查内存表及文件,遇可见墓碑即可阻断较旧值。重叠 L0 文件可能使一个键需要检查多份。

范围查从多个有序迭代器归并内部键及版本。若 k 路都活跃,堆归并每步约 O(log k),实际还受缓存、压缩和输出行影响。

本章流程图见 2.1 MemTable、SST 与层级 。

验证

构造两个重叠 L0 文件,其中一条墓碑覆盖低层旧值,手推点查和范围输出。

下载实验包 · 本卷目录 · 系列导读

一手资料

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图