Here is the article.

阅读目录

• 背景知识
• The Base LSM Algorithm
• Basic Compaction
• Levelled Compaction
• 关于 LSM 的一些思考
• Beyond Levelled LSM
• 延伸阅读

Log Structured Merge Trees(LSM) 原理

十年前，谷歌发表了 “BigTable” 的论文，论文中很多很酷的方面之一就是它所使用的文件组织方式，这个方法更一般的名字叫 Log Structured-Merge Tree。

LSM是当前被用在许多产品的文件结构策略：HBase, Cassandra, LevelDB, SQLite,甚至在mangodb3.0中也带了一个可选的LSM引擎（Wired Tiger 实现的）。

LSM 有趣的地方是他抛弃了大多数数据库所使用的传统文件组织方法，实际上，当你第一次看它是违反直觉的。