存储引擎之——B+树和LSM

B+树的优缺点

单次请求涉及的磁盘IO次数少（出度d大，且非叶子节点不包含表数据，树的高度小）；

查询效率稳定（任何关键字的查询必须走从根结点到叶子结点，查询路径长度相同）；

遍历效率高（从符合条件的某个叶子节点开始遍历即可）；

B+树最大的性能问题在于会产生 大量的随机IO ，主要存在以下两种情况：

主键不是有序递增的，导致每次插入数据产生大量的数据迁移和空间碎片；

即使主键是有序递增的，大量写请求的分布仍是随机的；

LSM树（Log Structured Merge Tree）,它并不是一颗很严格的树，它只是一种存储结构，目前HBase、LevelDB、RocksDB这些NoSQL存储的都是采用的LSM树

MenTable

MenTable是内存中的数据结构，用于保存最近更新的数据，会按照key有序的组织这些数据（如何有序的组织数据并没有明确的定义，例如HBase使用跳跃表来保证内存中key的有序）

Immutable MemTable

当MenTable达到一定大小后，会转化成Immutable Memtable。Immutable MemTable是将MemTable便问SSTable的一种中间状态。写操作由新的MemTable处理，在转存过程中不阻塞数据更新操作。

SSTable（Sorted String Table）

有序键值对集合，是LSM数组在磁盘中的数据结构。为了加快SSTable的读取，可以通过建立key 的索引以及布隆过滤器来加快key的查找。

LSM树会将所有的数据插入、修改、删除等操作记录保存在内存中，当此类操作达到一定数据量后，再批量地顺序写入到磁盘中。

这与B+树不同，B+树数据的更新会直接在元数据所在处修改对应的值，但是LSM树的数据更新是日志式的，当一条数据更新是直接append一条更新记录完成的。这样设计的目的就是为了顺序写，不断的将Immutable MemTable flush到持久化存储即可，而不去修改之前的SSTable中的key，保证了顺序写。

因此当MemTable达到一定大小flush到持久化存储变成SSTable后，在不同的SSTable中，可能存在相同的key的记录，当然最新的那条记录才是准确的，这样设计虽然大大提高了写性能，但同时也会带来一些问题：

冗余存储，对于每个key，实际上除了最新那条数据外，其他记录都是荣誉无用的，但是依然占用了存储空间。因此需要进行Compact操作（合并多个SSTable）来清除冗余的记录

读取时需要从最新的倒着查询，直到找到某个key的记录。最坏的情况需要查询完所有的SSTable，这里可以通过前面提到的所有/布隆过滤器来优化查找速度

LSM树的Compact策略

Compact（压缩）操作是十分关键的操作，否则SSTable数量会不断膨胀，在Compact策略上，主要介绍两种基本策略： size-tiered和leveled 。

三个概念：

读放大：读取数据时实际读取的数据量大于真正的数据量。例如在LSM树中需要现在MemTable查看当前key是否存在，不存在继续从SSTable中寻找

写放大：写入数据时实际写入的数据量大于真正的数据量。例如在LSM树中写入时可能触发Compact操作，导致实际写入的数据量远大于该key的数据量

空间放大：数据实际占用的磁盘空间比数据真正大小更多。例如冗余存储，对于应该key来说，只有最新的那条记录是有效的，之前的都是可以回收的

size-tiered策略

size-tiered策略保证每层SSTable的大小相近，同时限制每一层SSTable的数量。如上图，每层限制SSTable为N，当每层SSTable达到N后，则触发Compact操作合并这些SSTable，并将合并后的结果写入到下一层成为一个更大的sstable

因此当层数达到一定数量时，最底层的单个SSTable的大小会变得非常大。并且size-tiered策略会导致空间放大比较严重。即使对于同一层的SSTable，每个key的记录是可能存在多份的，只有当该层的SSTable执行compact操作才会消除这些可以的荣誉记录

leveled策略

leveled策略也是采用分层的思想，每一层限制总文件的大小

但是跟size-tiered策略不同的是，leved会将每一层切分成多个大小相近的SSTable。这些SSTable是在该层是全局有序的，意味着每一个key在每一层之多只有一条，不存在冗余记录。

当有一层超过大小限制时， 会从中选择至少一个文件和下一层有交集的部分进行合并 ，多个不相干的合并是可以并发进行的。

leveled策略相较于size-tiered策略来说，每层内key是不会重复的，这样的话冗余占比较小，因此空间放大问题得到缓解。但是写放大问题会更加突出，compact时将设计level N+1层的全部数据。