数据库中非常常用的索引数据结构——B+ 树，在过去很多年里它都是数据库索引的首选实现方式，但是这种数据结构也并不是很完美。因为，每次修改数据都很有可能破坏 B+ 树的约束，我们需要对整棵树进行递归的合并、分裂等调整操作，而不同节点在磁盘上的位置很可能并不是连续的，这就导致我们需要不断地做随机写入的操作，而随机写入的性能是比较差的，这个问题在写多读少的场景下会更加明显。
LSM Tree（Log Structure Merge Tree）是比 B+ 树更适合写多读少场景的索引结构，也广泛应用在各大 NoSQL 中。比如基于 LSM 树实现底层索引结构的 RocksDB、LevelDB。
LSM Tree 的实现原理：
LSM 树包含了三个部分，memtable、immutable memtable、SSTable前两个在内存中（使用预写日志的机制来确保数据的持久性），最后一个在磁盘中。同样，我们会先临时地把数据写在 memtable 中，然后在合适的时机刷入磁盘上的 SSTable 中。
1.Memtable
Memtable 显然是内存中的数据结构，存储的是近期更新的记录值，可以用各种有序高效的数据结构来实现，比如跳跃表、红黑树，不过可以简单的理解Memtable是一个 有序Map。
2.Immutable Table
在 Memtable 存储的元素到达一个数量级之后（大小一般为虚拟内存的页的倍数 4n KB），会把它固化成 immutable table，从字面上理解，就是不可变表。很明显这就是 memtable 的拷贝操作，因为拷贝过程是需要时间的，但同时我们的系统很可能仍然在对外工作，所以创建副本可以很好的地帮助我们避免读写冲突竞争，从而避免阻塞，提高系统性能。
3.SSTable
SSTable 是整个 LSM Tree 的核心，毕竟我们的大部分数据都是存储在磁盘上的，SSTable 就是在磁盘上做持久化的部分。本质其实很简单，就是一段段按照 key 有序排列的键值对，而持久化数据到磁盘最高效的方式就是顺序写一遍（顺序IO），每次内存中的数据immutable table，我们都一次性 dump 成磁盘上的一段自然是比较快的，这样一段段的数据，我们就称为一个个 segment。当然，后面存储的段和前面存储的段，key 可能是重复的，因为后面的段新一些，所以在有重复的时候，最靠后的段中的记录值，就是某个 key 最新的状态。
但很显然，这样的存储会有很多问题，首先数据冗余很大，随着时间推移，磁盘上就会有大量重复的键，其次我们需要遍历每个有序的 segment，查看数据是否存在。随着数据量增大，最坏情况下，要遍历的 segment 会非常多，整个系统的查询效率显然是惨不忍睹的。
所以我们需要合并 segment，合并前老的 segment 长度都是一样的且有序的，在 SSTable 的主流实现里，我们会把不同的阶段被合并的 segment 放到不同的层中，并限制每一层数量，当某层 segment 超过一定数量，我们就会把它们删除，合并出一个更大的 segment 放入下一层（低层中的 segment 是更新的记录值，高层的则是更老的记录值）。同时也会对相同的key进行最新值的覆盖，以减少数据的冗余。
检索的时候，我们只需要按照“内存 -> SSTable 第一层->SSTable 第二层”这样的顺序，去遍历每层中不同段是否包含目标 key。每个段内都是有序存储的，所以整体读的时间复杂度也是可以接受的，确实可能会比 B+ 树的查询效率低一些，不过辅以布隆过滤器等手段，劣化也不会非常明显，在许多读写比不到 1:10 的场景下，顺序写带来的写性能提升是非常令人满意的。
总结自（极客时间-业务开发算法50讲-黄清昊）
