0700: LSM-Tree 原理

Log-structured Merge Tree 和 B+Tree，是实现通用数据库的唯二选择。 LSM-Tree 虽然可以和 B+Tree 比较，却不是一个具体的数据结构，而是一种用“合并数据结构”来替代“更新数据结构”的方法。你可能会被名字误导，因为它的原理跟 tree 和 log 都没有关系！

目前实现的数据库有2层：MemTable 和 SSTable。 MemTable 通过 log 来实现持久化，而 SSTable 本身不会被修改，只会被新的文件替换。查询时合并结果，上层的 MemTable 优先级更高。更新时数据先进入到上层的，再到下层。

现在2层的结构，可以扩展成k层，这就是要实现的 LSM-Tree。每层具体是什么，无关 LSM-Tree 的原理。我们的要求是每层是个按 key 排序的 KV，可以是数组、树形结构。如果没有排序的要求，甚至可以是哈希表。所以 LSM-Tree 是一个数据结构的集合，而不是一个具体的数据结构。

level 1     [x=1, z=3]
level 2     [a=8, y=2, z=(deleted)]
...
level k     [a=0, b=2, c=3, d=4, z=456]

具体细节可以看完整版教程。