Log-Structured Merge Trees[以下简称LSM Tree]是一种能够支持海量数据的索引结构，但是，千万不要被它的名字迷惑，LSM Tree虽然可以算是索引，但跟B-Tree这种树状结构的索引算法没有半毛钱关系。

Google发表的BigTable论文，其文件组织方式合索引使用的就是Log-Structured Merge Tree。LSM-Tree这个方法还是基于一个经典的硬件常识或者说现状，磁盘[包括机械硬盘和SSD]的随机操作慢，顺序读写快，这二种操作在大数据环境下存在巨大的差距。当然了，论文阐述的理论并不复杂，但是能在分布于全球的成千上万台机器部署BigTable系统，其工程实力可见一斑。

MemTables

MemTables是LSM Tree在内存中的部分，通过类似平衡树的数据结构实现[比如，红黑树或者AVL树]。MemTable的意义在于，利用内存的高性能[相对于硬盘，要快很多]来维护一个sorted的数据结构，方便快速进行增删改查的操作。所以对于写操作，LSM Tree只需更新内存中的MemTables。

SSTables

SSTables，又称Sorted String Table，是LSM Tree在硬盘中的部分，一般通过key-value store来实现。它的作用在于，当内存中的MemTable大到一个阈值[一般情况下是几个megabyates]，整个MemTable就会以key-value pairs的形式写入硬盘，因为MemTable已经是排序好的结构，并且是顺序写入，所以会非常高效。

随着时间推移，系统会有多个SSTables，他们会按先后顺序倒序排列，也就是最晚生成的SSTable排在最前面。对于读操作，LSM tree会先从内存数据开始访问，如果在内存中访问不到，再从SSTable中按顺序查找。

Offline Merge and Compaction

对于多个SSTables，LST Tree会定期进行合并和压缩的工作，由于文件本身有序，合并操作会相对高效，并且可以有效减少磁盘文件个数，这样可以更快的完成读操作。HBase使用size-tiered compaction的方式，具体就是较新和较小的SSTable会依次合并到较旧和较大的SSTable中，而LevelDB和RockDB使用的是leveled compaction，也就是根据key range会分成多个小的SSTables，然后不同的数据会根据range移动到不同的level[这就有点像B-Tree了]来加速索引。

Further Optimization

所以还是那个经典的解决方法，将随机读写尽量变成顺序读写，一个方法就是简单的将数据添加到文件[要append，不要update]。这个策略经常被使用在日志文件[Log-Structured名字就是这么来的]，因为他们是完全顺序的，所以可以提供非常好的写操作性能，大约等于磁盘的理论速度。

但是，也有一些问题，首先，如果系统在数据还没有被写入硬盘前就崩溃了，那内存中的内容也会彻底失去，对于这个问题，大部分具体实现会通过维护一个独立的log来备份这些内存数据到磁盘，用来在系统崩溃使恢复数据，防止数据丢失。

其次，从SSTables中读数据需要full scan。最坏情况是，需要找的key并不存在，那默认情况下就会要遍历整个数据，在大规模数据的情况下非常不利。这时，可以配合使用Bloom Filter先来确定key是否存在。