概念介绍

LSM-Tree 被是一种面向写多读少应用场景的数据结构 ，被 Hbase、RocksDB 等强力 NoSQL 数据库采用作为底层文件组织方式。

简单的LSM-Tree 包含 2 层树状数据结构：

• Memtable 并完全驻留在内存中（假设 T0）

• SStables 存储在磁盘中（假设 T1）
  

• 记录会先从 memtable T0 组件中读取，如果没有，则会从 SStables T1 组件中读取

• 新记录被插入到 memtable T0 组件中。 如果插入导致 T0 组件超过某个大小阈值，则会从 T0 中删除连续的条目段并将其合并到磁盘上的 T1 中。

LSM-Tree

Memtable

MemTable是在内存中的数据结构，用于保存最近更新的数据，会按照Key有序地组织这些数据，LSM树对于具体如何组织有序地组织数据并没有明确的数据结构定义，例如Hbase使跳跃表来保证内存中key的有序。

因为数据暂时保存在内存中，内存并不是可靠存储，如果断电会丢失数据，因此通常会通过WAL(Write-ahead logging，预写式日志)的方式来保证数据的可靠性。

SSTables (Sorted String Table )

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

数据合并

由于我们将数据作为 SSTable 存储在磁盘中，假设有 N 个 SSTable，每个表的大小为 M，那么最坏情况读取时间复杂度是 O(N* Log(M) )，因此，随着 SSTable 数量的增加，读取时间复杂度也会增加。
另外，当我们刚刚刷新数据库中的 SSTable 时，多个 SSTable 中存在相同的 Key，LSM 会使用Compactor，Compactor 在后台运行，合并 SSTables 并删除具有相同行的多行，并添加带有最新数据的新键，并将它们存储在新的合并/压缩的 SSTable 中。

goleveldb 中LSM树实现

• https://github.com/justinethier/keyva/
• https://github.com/syndtr/goleveldb