一. LSM（Log-StructuredMerge-Tree）树

  随着NoSQL系统尤其是类BigTable系统的流行，LSM的文件系统越来越让人熟知。LSM主要用于为那些长期具有很高记录更新（插入和删除）频率 的文件提供低成本的索引机制。LSM树实现了所有的索引值对于所有的查询来说都可以通过内存组件或某个磁盘组件进行访问。LSM减少了磁盘磁壁的移动次数 降低了进行数据插入时磁盘磁壁的开销。LSM在进行需要即时响应的操作时会损失I/O效率，适用于索引插入比查询操作多的情况。

二.LSM-Tree主题思想LSM-Tree主题思想为划分成不同等级的数。

  可以想象一份索引由两棵树组成：一个存在于内存（可以使其他树结构），一个存在于磁盘（如下图）。

  数据首先会插入到内存中的树，为了防止数据丢失，写内存的同时需要暂时持久化到磁盘即输入数据时数据会以完全有序的形式先存储在日志文件中（对应HBase的MemStore和HLog）。当日志文件被修改时，对应的更新会被先保存在内存中来加速查询。

  当内存中树的数据达到阈值时，会进行合并操作。合并操作会从左至右遍历内存中的叶子节点与磁盘中树的叶子节点进行合并，当合并的数据量达到磁盘的存储页的大小时，会将合并的数据持久化到磁盘。同时更新父亲节点对叶子节点的指针（如下图）。    

  之前存在于磁盘的叶子节点被合并后，就到数据并不会被删除，这些数据会复制一份并与内存中的数据一起顺序写到磁盘。

  查找通过合并的方式完成，首先搜索内存存储结构，接下来是磁盘存储结构。

  LSM树所有节点都是满的并按页存储，经过多次的flush会创建很多数据存储文件，后台线程会将小文件聚合成大文件，因此磁盘的寻道操作就会被限制在一 定数目的数据存储文件中，以优化读性能。磁盘上的树结构也可以分割成多个存储文件，因为所有的存储数据都是按照Key有序排列的，因此在现有节点中插入新 的关键字不需要重新排序。

  LSM-Tree属于传输型，在磁盘传输速率上进行文件的排序和合并以及日志操作，可以更好的拓展到更大的数据规模上，因为它会使用日志文件和一个内存存储结构吧随机写操作转化为顺序写，读写独立，不会产生两种操作的竞争。

来自 “ ITPUB博客 ” ，链接：http://blog.itpub.net/30172158/viewspace-2113763/，如需转载，请注明出处，否则将追究法律责任。