背景本来是想写b树的，因为b树用于Mysql等关系数据库，所以大家都很熟悉。 LSM树之类的索引设计思路主要用于NoSql。 如果没有接触过NoSql数据库的朋友可能不太了解，我来介绍一下。 我参考了很多文章和资料。
LSM树是日志结构合并树的简称。 (其中的日志不一定指我们的程序日志，也指以时间为其中维度的大量树。 NoSQL数据库有广泛的APP应用，包括LevelDB和HBASE。 严格来说，这不是索引结构，而是索引设计的整体架构。 B树作为关系数据库中常用的索引存储结构，本身就很好。 支持范围查询、随机访问和添加删除调查。 但是，修改时，b树的集群索引数据存在叶节点，需要随机读写磁盘，随机写入的性能不充分。 磁盘的随机读写性能不好，顺序读写性能可以达到与存储器相同的水平，对其进行优化，容易考虑采用批量顺序写入来代替磁盘的随机写入。
LSM树适合的是写入量大、查询量比较少，而且查询查询最近的数据，旧数据一般查询较少的场景，LSM树适合。
二LSM树的关键思想Log Structured采用日志追加方式而不是随机写入，追加采用顺序写入，因此性能良好。 另一个重要思想是Merge Trees，写入数据时，先写入内存树。 既可以是红黑树，也可以是b树，有的采用了跳转表的存储器数据结构。 当内存中的树大小达到一定大小时，将内存中的树与磁盘中的树合并。 这就是合并树的来源。 开始将数据写入内存时，如果电源突然关闭或系统异常，可能会丢失数据。 为避免数据丢失，首先使用写预写日志技术(wal )将数据写入磁盘文件。 因为是顺序写入，所以不用担心性能上的问题。 如果发生异常，可以从WAL文件中恢复数据。
如上图所示，LSM树整体由内存部分的数据结构和磁盘上的两种文件组成。 内存中的数据结构由memtable和immutable Memtable两部分组成，首先是可写的，然后是只读的，两者具有相同的数据结构。 由于immutable Memtable是只读的，因此写入磁盘时无需锁定即可提高性能。 那么，如何读写数据呢？
写数据
请求到来后，写入WAL和内存的memtable。 memtable是红黑树和跳跃表等。
当memtable已满时，为新的申请内存构建新的memtable，将原始memtable转换为只读immutable memtable，并在适当的时间将其刷到磁盘上，作为SStable文件
刷新到磁盘后，可以截断WAL日志，以避免WAL日志无限扩大的问题。
immutable memtable保存在磁盘上。 直接与磁盘上的文件合并会增加磁盘的大小，因为内存中的数据较少，而且合并的数据较少，但会占用大量的IO磁盘。 这是绝对做不到的。 所以，像LevelDB一样，采用延迟合并方式，当每一层都已满时，滚动合并到下一层。
读数据
读取数据时，首先从存储器内的memtable读取。
否则，导入到immutable memtable中。
如果尚未查询数据，请将其读取到高速缓存中，包括数据高速缓存和索引高速缓存。
如果仍然找不到，请从0级开始查找。 0级SSTable未合并，因此数据重叠，需要查找每个SSTable。 0级的只有4MB (级别db )中，所以速度比较快。
如果为0级，则如果找不到数据，下沉到下一级1继续搜索。 级别1和更高级别的SSTABLE文件不重叠，因此您可以通过快速导航并搜索SSTABLE文件，在找到或找到所有级别后返回。
三SSTable SSTable即Sorted String Table听起来相当高，但实际上是已排序的键值和值对的集合，是存储在文件中的结构。 正在将散列表保存到磁盘文件中。 为了加快查询速度，还保存索引文件，保存key和offset的位置，用key快速检索offset，然后打开文件，直接放置在offset的位置。 但是散列表没有顺序，访问不同的key时需要随机的磁盘访问，而且散列表发生冲突时需要复杂的处理逻辑，不能支持范围查询。
简单来说，就是按key-value对的顺序按键排序。 这种格式称为排序字符串表或SSTable。
该结构将数据部分和索引部分分开，查询时不需要将整个SSTable文件读入内存。 如果先读取索引部分，布隆过滤可以快速确定是否存在要检查的key。 如果不存在，则不需要重读数据部分。
索引部分的索引块记录采用key:offset:size形式，key是各数据块的最小key，offset记录是数据块的开始位置，size是各数据块的符号每个数据块都采用顺序存储方式，可以方便地进行二分查找。
每次从四索引加速SSTable加载数据时都必须从磁盘读取
数据，性能比较差。所以LevelDB中设计了内存的缓存区。缓存区包括两个部分,一部分为最近使用的Index Block，另一个部分为Data Block，这样如果我们搜索的索引和数据都在内存中，就不用从磁盘中读取，提升了查询性能。 五 Level中SSTable合并首先为什么需要SSTable合并那，那是因为，随着数据的增大，写的SSTable文件越来越多，而且随着对key的更新和删除，这种需要删除的数据越来越多，为了减少文件数量和清理无效数据，就需要进行compact，即将多个SSTable文件合并成一个SSTable文件。
SSTable 按照分层滚动合并的方式，Level DB 的Level 0层最多只能保存4个SSTable,当Level 0层满了之后，我们就将它们进行多路归并，合并后的文件就是Level 1层的有序SSTable文件,
除Level 0 层，SSTable层的key的范围是不交叉的，这样查询的时候，就可以通过二分查找的方式进行快速查找了。Level 1 层的SSTable 就会从Level 1 层中轮询的方式选择一个SSTable去和Level 2 层在此SSTable 的key 范围内的SSTable进行文件合并，为了防止合并的占用的IO比较多，所以在生成SSTable的会判断此文件和下一层多少个SSTable有key的重合，如果超过10个就停止写入，生成新的SSTable 文件。这样每次合并SSTable文件消耗的IO也不至于太多。
合并的过程中，老的SSTable文件，是不能删除的，所以就会同时存在老的SSTable文件和新的SSTable文件，导致同一份数据因为被compaction，数据最多可能膨胀到原来的2倍。
不过数据会膨胀，由于在compaction过程中，有可能同一份数据不断随着compaction过程向更高层重复写入，有多少层有可能就写入多少次，IO几倍量的增加。
六 参考《核心索引20讲》 ssdxxm 《数据密集型应用系统设计》 Martin Leppmann
七 诗词欣赏 我宁愿瞄准星星，却击不中他们；也不愿没有目标；我宁愿去追逐目标，却得不到它，也不愿不曾追逐，我宁愿去尝试却失败，也不愿不曾尝试。我不想活着的每一天都在幻想如果我当初付出了更多努力现在会怎样？我会去放手追逐、无论刀山火海，我会去追逐我的命运！你不能朝着你的梦想漫步，你不能朝着梦想行走，你要向它狂奔！