LSM
LSM
为什么会有LSM树
传统的关系型数据库是用btree作为存储结构，能高效的进行查找，但是保存在磁盘中时它会有一个明显的缺陷，那就是逻辑上相离很近但是物理
上缺相隔很远，这就可能造成大量的磁盘随机读写。随机读写比顺序读写慢很多，为了提升IO性能，我们需要一种能将随机操作变为顺序操作的机制，于是就有了LSM树，LSM树能让我们进行顺序写磁盘，从而大幅度提升写操作。
LSM树的数据结构
三个重要组成部分
Memtable
Memtable时在内存中的数据结构，用于保存最近更新的数据，会按照key有序的组织数据，可以是用红黑树也可以是用跳表（Hbase）,因为数据是暂时保存在内存中的，所以要通过WAL（write ahead logging，预写式日志）保证数据可靠性
Immutable Memtable
当MemTable达到一定大小后，会转化为Immutable MemTable,Immutable Table时Memtable转为SSTable的一种中间状态，写操作由MemTable处理，在转存过程中不阻塞数据更新操作
SSTable(Sorted String Table)
有序键值对集合，时LSM树组在磁盘中的数据结构,为了加快SSTable的读取，可以通过key的索引以及布隆过滤器来加快key的查找。
合并操作
size-tiered策略
size-tiered策略是hbase采用的合并策略，具体内容是当某个规模的集合达到一定的数据量时，将这些集合合并为一个大的集合，比如有5个50个数据的集合，那么将他们合并我一个250个数据的集合，这种策略有一个缺点是当集合达到一定的数量后，合并操作会变得十分的耗时。
leveled策略
leveled策略是LevelDB和rocksdb采用的合并策略，size-tiered策略因为会产生大数据量的集合，所以会造成突发的IO和CPU资源，所以leveled策略使用了分层的数据结构来代替原来的大数据集合。
leveled策略将集合的大小限制在一个小的范围内如5MB，而且将集合划分为不同的层级，每个层级的集合宗大小是固定且递增的。如第一层为50mb，第二层为500mb，当某一层的数据集合大小达到上限是，就会从这一层中选出一个文件盒下一层合并，或者直接提升到下一层，如在合并中发现了数据冲突，则丢弃下一层的数据，因为低层的数据总是更新的。同时leveled策略会限制，除第一层外，其他的每一层的键值都不会重复，这是通过合并时剔除冗余数据实现的，以此来加速在同一层内数据的线性扫描速度。