《Hbase权威指南》深入学习hbase架构(1)：LSM-Tree

    hbase内部是使用Log-Structured Merge-Tree说索引的，即LSM-tree，当然是为hbase做过优化的。
    LSM-tree是一个优秀的算法，思想来源于日志文件系统，本身是为提高B-树在更新插入数据时的性能而提出来的，主要优点就是通过将很多小文件的存取转换为连续的大批量传输，使得对于文件系统的大多数存取都是顺序性的，从而提高磁盘带宽利用率；故障恢复速度快。它对数据写入主要分以下三个阶段：
    1、数据的写入是以log追加的方式进行按顺序被保存到logfile文件，具有索引；
    2、一旦数据被保存到了logfile文件，会被立即保存到一块儿叫的内存缓冲区的memsotre——缓存的数据也是就说排序的，memsotre中保存最近更新的数据以响应客户端的快速查询；
    3、当内存中的memsotre大到一个阀值的时候，缓存数据会被以key -> record对的形式刷新到磁盘，生成一个新的存储文件持久化数据。
    这个新生成的存储文件和B-数很像，但是是为顺序磁盘查询优化过的，特别是为single-page数据页和multi-block数据块做了优化，以方便范围查找。由于memstore中的数据每刷新一次生成一个store文件，store文件会随着时间的推移越来越多，系统对这些文件采用一种叫rolliong merge即滚动合并的模式，由后台线程将这些文件合并成一个大的store文件——文件中的数据总是按key排序存储的，这样只需经过很少的磁盘查找就可以查到结果。
    在查找数据时，首先会在memstore中的数据中查找，如果查找到则直接返回结构，否则接下来回查找保存在磁盘上的store文件中的数据，返回将结果返回——查的到或查不到。
    删除是一个特殊的更新操作，执行一个delete操作时，这个要删除的数据会被标记为delete marker被保存起来；当查询时会过滤掉标记为“删除”的key的数据。只有在后台线程异步的重写的数据页数据时，标记为“删除”的数据才会被删除。
    下图为LSM-Tree内部多数据页合并过程：
   

                               内部多数据页合并图