| LSM-Tree（Log Structured Merge Trees，日志结构合并树）与前面介绍的存储结构有所不同，前面的存储结构在描述如何序列化逻辑数据结构，而LSM-Tree描述的则是为了满足高效、高性能、安全地读写的要求，如何有效地利用内存和磁盘存储。LSM-Tree的观点是由Patrick O'Neil在1996年率先提出的。LSM-Tree算法思想主要用于解决日志记录索引的问题，这种应用的特点是数据量大、写速率高（2000条／秒），又要建立有效的索引来查找日志中的特定条目。Patrick O'Neil的做法是，在内存里维护一个相同的B树，当内存中的B树达到阈值时，批量进行滚动合并。
|
|
|
| 而LSM-Tree的典型例子就是Google的Bigtable。下面将结合Bigtable具体解释LSM-Tree的工作原理。
|
|
|
| 当初Google设计Bigtable的原因有两个，一是Google需要存储的数据种类繁多，二是海量的服务请求。Google的需求是：数据存储可靠性、高速数据检索与读取、存储海量的记录、可以保持记录的多个版本。Bigtable中的合并／转储引擎结构图如下图所示。
|
|
|
|
|
|
|
| 用户的操作首先写入到MemTable中，当内存中的MemTable达到一定的大小，需要将MemTable转储到持久化存储中生成SSTable文件。这里需要注意，除了最早写入的SSTable存放了最终结果以外，其他的SSTable和MemTable存放的都是用户的更新操作，比如对指定行的某个列加一操作，删除某一行等。每次读取或者扫描操作都需要对所有的SSTable及MemTable按照时间从老到新进行一次多路归并，从而获取最终结果。
|
|
|
| 如果要确保数据不能丢失，为了应对服务器遇到不可抵抗外力因素造成宕机的情况，LSM有两次持久化过程：一次是log，以append形式对所有的update操作先进行日志记录，一旦出现意外情况，即可以恢复log中的内容到MemTable；第二次是swap，在MemTable达到阈值的时候直接转储到磁盘上形成新的SSTable。
|
|
|
