LSM-TREE和SSTable

一、什么是LSM-TREE

LSM Tree 是一种高效的写优化数据结构，专门用于处理大量写入操作
在一些写多读少的场景，为了加快写磁盘的速度，提出使用日志文件追加顺序写，加快写的速度，减少随机读写。但是日志文件只能遍历查询。不支持随机查询，提出使用LSM-TREE。除了利用磁盘顺序写之外，还划分了内存+磁盘多层的合并结构

LSM-TREE(log structured tree) 就是多层的SSTable
1、什么是SSTable
SSTable就是存放在磁盘的一个数据块，里面存放可变数组长度的kv数组。SSTable内部按照key进行排序


LSM-TREE类似于ES
写数据
写数据先写在内存的Memtable，Memtable写满后才写入磁盘。
当每层的磁盘上的SSTable的体积超过一定的大小或者个数，会周期的进行合并。此步骤也称为Major Compaction。这个阶段会真正的清除掉被标记删除掉的数据（类似ES段合并）。合并完后进入下一层，因为SSTable内部都是有序的。因此使用mergeSort算法可以快速合并 O(n)复杂度。
查询
1、先在内存里面查询，如果查询到就返回。
2、从上到下，从左到右。遍历每一层级的SSTable的布隆过滤器，快速判断数据在不在此SSTable。（最坏情况需要遍历所有SSTable的filter）
3、SSTable内部有序，进行二分查找
4、刚写入的数据在上面层级，历史数据经过合并落入下层。因此LSM-TREE非常适合时序数据库（这种只查询最近写入的热数据）的场景

一、influxdb和ES都是准实时，都有段合并。 为什么不用倒排索引

influxDb属于写多读少，ES适用读多写少的场景
influxdb序列数据写多读少适用于LSM-TREE 。influxdb根据tag查找序列 适用于倒排索引
influxdb两种结构都使用了

二、LSM-TREE 分层结构和B+数很类似，有什么区别？

1、LSM-Tree的设计思路是，将数据拆分为几百M大小的Segments（SSTable），并是顺序写入，SSTable太大对于随机读写不友好。B+Tree则是将数据拆分为固定大小的Block或Page, 一般是4KB大小。block块小就适用于随机读写。
2、B+树支持随机读写，因此插入更新，都是实时的。而LSM-TREE更新和ES类似（先删除再新增）准实时。
3、B+树是全局有序的，每一层节点页内部数据 和节点之间 数据都是全局有序。
而SSTable是局部有序，只有SSTable内部有序，SSTable无序。只有层级下沉段合并的时候，才会进行mergeSort形成新的SSTable

LSM-TREE的应用场景：

levelDB, rocksdb influxDb等