存储树-LSM NoSQL算法图：原理、插入、连接、查找、删除树

LSM，即Log-Structured Merge-Tree。其实并不涉及具体的数据结构，而是涉及数据结构设计的思想。 NoSQL数据库的核心思想大多基于LSM，但具体实现方式有所不同。所以，这就是为什么我不打算把它包含在这个系列中，但是我的朋友多次给我发消息让我谈论LSM树，所以我会谈论LSM树。

LSM树诞生的背景

传统的关系数据库使用btree或者某种变体作为存储结构，可以高效地进行搜索。但它存储在磁盘上时也有一个明显的缺点，那就是逻辑上很近但物理上可能很远，这会导致很多随机的磁盘读写。随机读写比顺序读写慢。为了提高IO性能，我们需要一种可以将随机操作变成顺序操作的机制，所以就有了LSM树。 LSM树允许我们顺序写入磁盘，从而大大增加了写入操作，但牺牲了一些读取性能。

关于磁盘IO

磁盘读写包括查找磁盘上的数据。地址一般由柱面号、磁盘号和块号组成。即移动臂首先根据柱面号移动到指定的柱面，然后根据盘片号确定盘片上的磁道，最后根据块号移动到磁头下方的指定磁道段，然后读取就可以开始写作了。

所有进程主要使用三部分时间，搜索时间+延迟时间+传输时间。它们仅代表定位柱面的大量时间、磁头按块号移动磁道部分的大量时间以及将数据传输到存储器的大量时间。所有磁盘IO中最耗时的部分是寻道时间，因此减少寻道时间可以提高性能。

LSM树原理

LSM树由两个或多个存储结构组成。例如，在纸面上，使用两种最简单的存储结构来进行说明。存储结构驻留在内存中，称为C0树。可以是任何有利于查找键值的数据结构，比如红黑树、地图等，甚至可以是跳表。另一种存储结构位于硬盘上，称为C1树，具体结构与B树类似。所有C1节点都是100%满的，节点大小就是磁盘块大小。

插入步骤

大致思路是：插入新记录时，先将操作日志插入到日志文件中，以便以后恢复。日志以append的形式录入，这样速度很快；向C0插入一条新的记录索引，这是在内存中完成的，不参与磁盘IO操作；当C0的大小达到一定阈值或者每隔一段时间，C0中的记录就会滚动并合并到磁盘C1中；对于各种存储结构的情况，当C1变大时，它会与C2合并，然后，将Ck向上合并。

合并步骤

合并过程中使用两个块：空块和填充块。

1. 从C1中读取未合并的叶子节点，并将其放入内存中的空块中。
2. 从小到大查找C0中的节点，与空块合并排序，将合并结果存入填充块，删除C0对应的节点。
3. 连续执行步骤2，合并后的排序结果不断填充到填充块中。当它已满时，它会被添加到磁盘上的新位置。请注意，原始节点是被添加而不是被替换。在合并期间，如果已经使用了空的故宫块，则将从C1中读取未合并的叶子节点。
4. 将所有叶子节点C0和C1按照上面的方法加入后，加入完成。

关于优化措施

本文用图来说明LSM的基本原理，但实际项目中的优化策略有很多，LSM树优化的论文也很多。例如，使用布隆过滤器来快速判断是否存在某个键，并做一些额外的索引来帮助更快地查找记录等。

插入操作

将A E L R U插入LSM树。第一个将被插入到内存中的 C0 树中。这里使用AVL树，输入“A”，第一个磁盘日志文件添加记录。然后输入C0，

输入“E”，同样先添加一条日志然后写入内存，

继续输入“L”，旋转后如下，

输入“R”和“U”，旋转后的结果如下。

假设此时触发合并，由于C1还没有树，所以空块为空，立即从C0树中按顺序找到最小的节点。填充块长度为4，磁盘块大小假设为4。

开始寻找最小的节点并将其插入到填充块中，

继续寻找第二个节点，

依此类推，填充填充块，

开始写入磁盘，树C1，

继续插入B F N T。先单独写入日志，然后插入到内存中的C0树中。

如果此时合并，将最左边的叶子节点C1加载到空块中，

然后将树节点C0和空块合并排序。首先，“A”进入填充块，

，然后“B”，

合并顺序的最终结果是，

将填充块添加到磁盘新位置，删除原来的节点。 。

继续连接、分类和填充补充块。

将填充块添加到磁盘上的新位置。顶层的节点也应该位于一个写入大小的磁盘块（或几个磁盘块）上，并尽量避免随机写入。此外，由于合并过程可能会导致顶级节点的更新，因此它们可以暂时存储在内存中并在以后适当的时间写入。

搜索操作

搜索的总体思路是先搜索内存的C0树，如果找不到，则从磁盘中搜索C1树，然后是C2树，以此类推。

如果你想找到“B”，先找树C0，但是找不到。

然后找到树C1，从根节点开始，

找到“B”。

删除操作

为了进行快速删除操作，主要是通过标记来完成。内存中标记了要删除的记录，后面异步执行merge时就会删除对应的记录。

例如要删除“U”，假设标记#表示删除，则树C0中的节点“U”变为，

而如果记录不在树C0中，则节点“U”变为会在树C0中生成，并用#标记，查找时可以知道该记录已在内存中删除，而不必到磁盘上查找。例如，如果要删除“B”，则无需到磁盘上执行删除操作。可以直接在树C0中插入节点“B”，并用#标记。作者：超人王小健非商业转载请注明出处。