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)复杂度。
L0 L1层级的多个SSTable内部局部有序，SSTable之间无序
但是L2层级 及以上。每次段归并时，并不是每m个 并行段归并。而是把上一层级全部SSTable举行多路归并。串行序次天生多个SSTable。多个SSTable之间是全局有序的。
查询
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等
SSTable的应用场景：

levelDB:  kv存储
rocksDB：kv存储
influxDB: 办理 series存储
HBase:列式存储（雷同mysql表）