B+树的数据都存储在叶子节点中，而叶子节点一般都存储在磁盘中。因此，每次插入的新数据都需要随机写入磁盘，而随机写入的性能非常慢。如果是一个日志系统，每秒钟要写入上千条甚至上万条数据，这样的磁盘操作代价会使得系统性能急剧下降，甚至无法使用。
针对这种频繁写入的场景，提出一种常见的设计思路和检索技术：LSM树。
LSM树是近年来许多火热的NoSQL数据库中使用的检索技术。
滚动归并:
- 第一步，以多页块为单位，将C1树的当前叶子节点从前往后读入内存。读入内存的多页块，叫做清空块，意思是处理完以后会被清空。
- 第二步，将C0树的叶子节点和清空块中的数据进行归并排序，把归并的结果写入内存的一个新块中，叫作填充块。
- 第三步，如果填充块写满了，我们就要将填充块作为新的叶节点顺序写入磁盘。这个时候，如果C0树的叶子节点和清空块都没有遍历完，我们就继续遍历归并，将数据写入新的填充块。如果清空块遍历完了，我们就去C1树中顺序读取新的多页块，加载到清空块中。
- 第四步，重复第三步，直到遍历完C0树和C1树的所有叶子节点=，并将所有的归并结果写入到磁盘。这个时候，我们可以同时删除C0树和C1树中被处理过的叶子节点。这样就完成了滚动归并的过程。
在C0树到C1树的滚动归并过程中，你会看到，几乎所有的读写操作都是以多页块为单位，将多个叶子节点进行顺序读写的。而且，因为磁盘的顺序读写性能和内存是一个数量级的，这使得LSM树的性能得到了大幅度的提升。
因为同时存在C0和C1树，所以要查询一个key时，我们会先到C0树中查询。如果查询到了则直接返回，不用再去查询C1树了。
而且C0树会存储最新的一批数据，所以C0树中的数据一定会比C1树中的新。因此如果一个系统的检索主要是针对近期数据的，那么大部分数据我们都能在内存中查到，检索效率会非常高。
那如果我们在C0树种没有查询到key呢？那这个时候系统就会去磁盘中的C1树查询，在C1树种查到了，我们能直接返回吗？如果没有特殊处理的话其实不能。
比如如果一个数据已经被写入系统，并且我们也把它写入C1树了。但是，在最新的操作中，这个数据被删除了，那我们自然不会在C0树中查询到这个数据。可是它依然存在于C1树中。这种情况下，我们在C1树中检索到的就是过期的数据。既然是过期的数据，那为了不影响检索结果，我们能否从C1树中将这个数据删除呢？删除的思路没有错，但是我们不希望对C1树进行随机访问，这时我们该怎么处理？
我们依然可以采取延迟写入和批量操作的思路。对于被删除的数据，我们会将这些数据的key插入到C0树中，并且存入删除标志。如果C0树中已经存有这些数据，我们就将C0树中这些数据对应的key都加上删除标志。这样一来，当我们在C0树中查询时，如果查到了一个带着删除标志的key就直接返回查询失败，我们也就不用去查询C1树了。在滚动归并的时候，我们会查看数据在C0树中是否带有删除标志。如果有，滚动归并时将它放弃。这样C1树就能批量完成数据删除操作。（标记删除的数据时在merge合并的时候被物理删除的）
在写大于读的应用场景下，尤其在日志系统和监控系统这类应用中，我们可以使用基于LSM树的NoSQL数据库，这是比B+树更适合的技术方案。
LSM树具有以下三个特定：
- 将索引分为内存和磁盘两个部分，并在内存达到阈值时启动树合并
- 用批量写入代替随机写入，并且用预写日志WAL技术保证内存数据在系统崩溃后可以被恢复
- 数据采用类似日志追加写的方式写入磁盘，以顺序写的方式提高写入效率
LSM树的这些特定，使得它相对于B+树，在写入性能上有大幅提升。所以，许多NoSQL系统都使用LSM树作为检索引擎，而且还对LSM树进行了优化以提升检索性能。
B+树是写入的时候就找好key的位置，读取的时候直接根据索引查找key的值
LSM是写入是可能一个key存在不同层的树上，读取的时候，需要合并key不同树上的值。
相当于B+树是写入时merge，LSM是读取时候merge
早期LSM树：
实质就是利用内存，延迟写入磁盘的时机。
C0-tree 由于常驻内存，检索起来不会产生 IO，所以理论上，我们可以使用各种可用于高效索引的数据结构来存储数据，比如红黑树、跳表等等。但是因为内存成本高昂，能存储的数据必然有限，更大量的数据仍然需要存储在磁盘里。而磁盘中的 C1-tree 一般被实现为特殊的 B+ 树。数据的存储也会分为两个阶段，我们会一直先在内存中存储元素，直到内存中的数据到达一个阈值，我们会开始和 C1-tree 中的节点进行合并和覆写，过程和多路归并有点相似。因为我们可以决定写入磁盘的时机，所以完全可以保证 B+ 树的所有节点是满的，也就避免了许多单次的随机写操作。
现代LSM树包含三个部分：memtable、immutable memtable、SSTable
前两个在内存中，最后一个在磁盘中。我们会先把临时地数据写在memtable中，然后在合适的时机刷入磁盘的SSTable中。（WAL机制保证数据安全）
- 内存上的部分，memtable、immutable memtable，比较简单，用通用的有序集合存储即可，跳表、红黑树都是非常不错的选择；
- 磁盘上的数据结构，SSTable，也不复杂，就是一段段连续按 key 有序存储的段，唯一需要做的就是后台启动一个程序不断地进行多路归并，得到分层的有序存储结构。
-LSM（Log-Structured Merge Tree）树是一种新型的索引结构，与传统的 B+ 树相比，具有以下优点：
- 高写入性能。LSM 树采用了日志结构存储方式，所有的写操作都追加到磁盘顺序写日志中，不需要进行随机写入操作，因此具有较高的写入性能。
- 空间利用率高。LSM 树使用了合并机制，将多个较小的数据文件合并成一个较大的文件，避免了 B+ 树中频繁分裂和合并导致的空间浪费问题。