早期LSM树

为什么需要LSM树

B+树的数据都存储在叶子节点中，而叶子节点一般都存储在磁盘中。因此，每次插入的新数据都需要随机写入磁盘，而随机写入的性能非常慢。如果是一个日志系统，每秒钟要写入上千条甚至上万条数据，这样的磁盘操作代价会使得系统性能急剧下降，甚至无法使用。
针对这种频繁写入的场景，提出一种常见的设计思路和检索技术：LSM树。
LSM树是近年来许多火热的NoSQL数据库中使用的检索技术。

如何使用批量写入代替多次随机写入

操作系统对磁盘的读写是以块为单位的，我们也可以以块为单位写入，而不是每次插入一个数据都要随机写入磁盘。
LSM树根据上面这个思路设计这样一个机制：
当数据写入时，延迟写磁盘，将数据先存放在内存中的树里，进行常规的存储和查询。当内存中的树持续变大达到阈值时，再批量地以块为单位写入磁盘的树中。因此LSM树至少需要由两棵树组成，一棵是存储在内存中较小的C0树，另一课时存储在磁盘中较大的C1树。

C1存储在磁盘，因此我们可以直接使用B+树来生成。那对于全部存储在内存中的C0树，该如何生存？在数据都能加载在内存中的时候，B+树并不是最合适的选择，它的效率并不会更高。因此，C0树我们可以选择其他的数据结构来实现，比如平衡二叉树甚至跳表。我们先假设C0树也是一棵B+树。相比于普通的B+树，C0,C1树有一个特点就是所有叶子节点都是满的，因为C1树不需要支持随机写入了，我们完全可以等内存中的数据写满一个叶子节点之后，再批量写入磁盘，因此每个叶子节点都是满的，不需要预留空位来支持新数据的随机写入。

如何将内存数据与磁盘数据合并

解决了内存中数据备份的问题，我们就可以接着写入数据了。内存中C0树的大小是有上限的，当C0树被写满之后，怎么把它转化到磁盘的C1树上呢？这就涉及滚动合并的过程了。我们可以参考两个有序链表归并排序的过程，将C0树和C1树的所有叶子节点中存储的数据看作是两个有序链表，那滚动合并问题就变成了我们熟悉的两个有序链表的归并问题。

由于磁盘具有顺序读写效率高的特性，因此，为了提高C1树中节点的读写性能，除了根节点以外的节点都要尽可能地存放到连续的块中，让它们能作为一个整体单位来读写，这种包含多个节点的块就叫作多页块。

滚动归并:

• 第一步，以多页块为单位，将C1树的当前叶子节点从前往后读入内存。读入内存的多页块，叫做清空块，意思是处理完以后会被清空。
• 第二步，将C0树的叶子节点和清空块中的数据进行归并排序，把归并的结果写入内存的一个新块中，叫作填充块。
• 第三步，如果填充块写满了，我们就要将填充块作为新的叶节点顺序写入磁盘。这个时候，如果C0树的叶子节点和清空块都没有遍历完，我们就继续遍历归并，将数据写入新的填充块。如果清空块遍历完了，我们就去C1树中顺序读取新的多页块，加载到清空块中。
• 第四步，重复第三步，直到遍历完C0树和C1树的所有叶子节点=，并将所有的归并结果写入到磁盘。这个时候，我们可以同时删除C0树和C1树中被处理过的叶子节点。这样就完成了滚动归并的过程。
  在C0树到C1树的滚动归并过程中，你会看到，几乎所有的读写操作都是以多页块为单位，将多个叶子节点进行顺序读写的。而且，因为磁盘的顺序读写性能和内存是一个数量级的，这使得LSM树的性能得到了大幅度的提升。

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树的使用场景

在写大于读的应用场景下，尤其在日志系统和监控系统这类应用中，我们可以使用基于LSM树的NoSQL数据库，这是比B+树更适合的技术方案。

LSM树具有以下三个特定：

• 将索引分为内存和磁盘两个部分，并在内存达到阈值时启动树合并
• 用批量写入代替随机写入，并且用预写日志WAL技术保证内存数据在系统崩溃后可以被恢复
• 数据采用类似日志追加写的方式写入磁盘，以顺序写的方式提高写入效率

LSM树的这些特定，使得它相对于B+树，在写入性能上有大幅提升。所以，许多NoSQL系统都使用LSM树作为检索引擎，而且还对LSM树进行了优化以提升检索性能。

小总结

B+树是写入的时候就找好key的位置，读取的时候直接根据索引查找key的值
LSM是写入是可能一个key存在不同层的树上，读取的时候，需要合并key不同树上的值。
相当于B+树是写入时merge，LSM是读取时候merge

现代LSM树

早期LSM树：
实质就是利用内存，延迟写入磁盘的时机。
C0-tree 由于常驻内存，检索起来不会产生 IO，所以理论上，我们可以使用各种可用于高效索引的数据结构来存储数据，比如红黑树、跳表等等。但是因为内存成本高昂，能存储的数据必然有限，更大量的数据仍然需要存储在磁盘里。而磁盘中的 C1-tree 一般被实现为特殊的 B+ 树。数据的存储也会分为两个阶段，我们会一直先在内存中存储元素，直到内存中的数据到达一个阈值，我们会开始和 C1-tree 中的节点进行合并和覆写，过程和多路归并有点相似。因为我们可以决定写入磁盘的时机，所以完全可以保证 B+ 树的所有节点是满的，也就避免了许多单次的随机写操作。
现代LSM树包含三个部分：memtable、immutable memtable、SSTable
前两个在内存中，最后一个在磁盘中。我们会先把临时地数据写在memtable中，然后在合适的时机刷入磁盘的SSTable中。（WAL机制保证数据安全）

Memtable

内存中的数据结构，存储的是近期更新的记录值，类似原始LSM树，可用各种高效的数据结构实现，比如跳跃表，红黑树。

Immutable Table

在 Memtable 存储的元素到达一个数量级之后，我们就会把它固化成 immutable table，从字面上理解，就是不可变表。
memtable 的拷贝操作，拷贝过程需要时间，但同时我们的系统很可能在对外工作，所以创建副本可以很好的帮助我们避免读写冲突竞争，从而避免阻塞，提高性能。
顺序写入磁盘，SSTable不再发生变化

SSTable

SSTable不可变，因此对现有对象Key的更新不会覆盖现有的SSTable
当下我们有了内存中的有序结构，存储了近期的记录变更，如何把数据落盘，既要有磁盘顺序读写的优势，也能保证所写的格式便于改动也便于查询。
它是整个 LSM Tree 的核心，毕竟我们的大部分数据都是存储在磁盘上的，SSTable 就是在磁盘上做持久化的部分。本质其实很简单，就是一段段按照 key 有序排列的键值对。

SSTable 一般也会带上一个索引文件，值存储的是 key 所对应的 offset，加载到内存后，我们利用二分搜索可以很快查找出要访问的 key 的值。
最简单的持久化方式就是我们在磁盘上把内存中有序的键值对直接 dump 成一个个段，也就是 segment。后面存储的段和前面存储的段，key 可能是重复的，因为后面的段新一些，所以在有重复的时候，最靠后的段中的记录值，就是某个 key 最新的状态。
我们把内存中有序的数据结构比如红黑树中的记录，dump 到一段磁盘上的空间，然后按 segment 一段一段往后叠加

那在这样的存储下，检索数据的时候需要怎么做呢？很简单，就是从后面的段开始，往前遍历，看看是否有查找到目标 key，有的话就返回。由于从后往前遍历，我们第一次查询到 key 的时候，一定就是这个 key 对应的最新状态。

但是这样存储会有很多问题：

• 数据冗余很大，随着时间的推移，磁盘上会有大量重复的键。
• 其次我们需要遍历每个有序的 segment，查看数据是否存在。随着数据量增大，最坏情况下，要遍历的 segment 会非常多，整个系统的查询效率显然是惨不忍睹的。
  总之就是读的速度慢过头了。
  压缩数据：
  前提：每个 segment 都是有序的，那我们显然可以比较高效地对多段数据进行合并操作，就是“多路归并”的思路，一般，多路归并的程序我们会在后台不断运行，我们会不断地把多个老的 segment 合并成一个更长的、同样有序的 segment。
  在 SSTable 的主流实现里，我们会把不同的阶段被合并的 segment 放到不同的层中，并限制每一层数量，当某层 segment 超过一定数量，我们就会把它们删除，合并出一个更大的 segment 放入下一层。
  低层中的 segment 显然是更新的记录值，更高层的则是更老的记录值。
  
  在图的例子中可以看出来，我们合并 segment1、2、3 之后，在得到的 segment4 里，dog 的记录就只剩更新的 segment2 中的记录 84 了。这样我们的整个存储空间就不会无尽地膨胀，最高的一层，最多也就是占用历史以来所有出现过的 key 和对应的记录值这样数量级的空间，而存储这些是数据库本应做到的。

更新和删除数据：

将数据标记成一种特殊的状态。这种通过标记而不是真实移除数据的方法，在业务开发中其实也很常见，有时候我们称为 soft delete。在有些 ORM 库中会直接通过 deleteAt 字段，标记删除时间，来表示这个数据被删除了，想恢复这个数据的时候也很简单，直接将 deleteAt 置空即可。
在 LSM tree 中也是一样，我们把这个特殊的状态称为== tombstone，墓碑==，看图就非常清楚了。

查询的时候，如果我们先查到了 tombstone，就可以认为数据已经不复存在了。
更新数据的时候也是，把原来key的数据标记为墓碑，如下图

小总结

• 内存上的部分，memtable、immutable memtable，比较简单，用通用的有序集合存储即可，跳表、红黑树都是非常不错的选择；
• 磁盘上的数据结构，SSTable，也不复杂，就是一段段连续按 key 有序存储的段，唯一需要做的就是后台启动一个程序不断地进行多路归并，得到分层的有序存储结构。

每向下一级数据就会指数级增加

• LSM树再内存中缓冲写入数据
• 当缓冲区填满时，我们将其排序并作为不可变的SSTable刷新到磁盘
• 随着更多缓冲区被刷新到磁盘，SSTable的数量也会增加
• 会给读取带来问题，因此每次读取都必须搜索这些SSTable以执行查找。为了限制每次读取必须搜索的SSTable的数量，LSM树合并SSTable并在后台压缩它们。
  

优化查找

查找key，会在每个级别SSTable上执行搜索，排序数据搜索快，但遍历所有磁盘SSTable会消耗大量I/O。
许多系统在内存中保留一个汇总表，其中包含每个level的每个磁盘块的最小key和最大key范围，允许系统跳过对那些key不在范围内的磁盘块的搜索。
另一个可能代价高昂的问题就是查找不存在的key，那就得扫描所有level中符合条件的磁盘块，因此大多数系统在每一层level都有一个布隆过滤器来防止这周情况。

chatgpt给的总结

-LSM（Log-Structured Merge Tree）树是一种新型的索引结构，与传统的 B+ 树相比，具有以下优点：

1. 高写入性能。LSM 树采用了日志结构存储方式，所有的写操作都追加到磁盘顺序写日志中，不需要进行随机写入操作，因此具有较高的写入性能。
2. 空间利用率高。LSM 树使用了合并机制，将多个较小的数据文件合并成一个较大的文件，避免了 B+ 树中频繁分裂和合并导致的空间浪费问题。

​ 但是，LSM 树也存在一些缺点：

1. 查询性能较差。由于 LSM 树中的数据需要通过多层文件进行合并才能达到可用状态，因此查询操作的性能相对较低。
2. 不支持范围查询。由于 LSM 树中的数据文件是按照时间顺序排列的，因此不支持范围查询。
3. 内存占用较高。由于 LSM 树需要维护多个数据文件，因此需要占用较多的内存空间。