数据结构篇：深度剖析LSM及与B+树优劣势分析

        本文旨在探讨LSM的特性及其在实际应用场景中的作用，同时对其与B+树进行比较，以帮助更好地理解和运用这两种数据结构。

什么是LSM（Log-structured Merge-tree）

        全称 Log-Structured Merge-Tree 日志结构合并树，但不是树，而是利用磁盘顺序读写能力，实现一个多层读写的存储结构，它是一种分层，有序，面向磁盘的数据结构，核心思想是利用了磁盘批量的顺序写要远比随机写性能高出很多，大大提升了数据的写入能力，但会牺牲部分读取性能为代价。

        其中HBase、LevelDB、ClickHouse这些NoSQL存储都是采用的类LSM树结构，该数据结构在 NoSQL 系统里非常常见，基本已经成为必选方案, 为了解决快速读写的问题去设计的充分利用了磁盘顺序写的特性，实现高吞吐写能力，数据写入后定期在后台Compaction在数据导入时全部是顺序append写，在后台合并时也是多个段merge sort后顺序写回磁盘。

深入理解

        首先，LSM是日志结构（Log-Structured）的，打印日志是一行行往下写，不需要更改，只需要在后边追加就好了。其次会进行合并树（Merge-tree），合并就是把多个合成一个，自上而下。基于以上特点，LSM-tree其实就是一个多层结构，像一个喷泉树一样，上小下大。

        专门为 key-value 存储系统设计的，最主要的就两个功能：1）写入put（k，v）； 2）查找 get（k）得到v；

        首先是内存的 C0 层，保存了所有最近写入的 （k，v），这个内存结构是有序的，且可以随时原地更新，同时支持随时查询。接下去的 C1 到 Ck 层都在磁盘上，每一层都是一个有序的存储结构。降低一点读性能，通过牺牲小部分读性能，换来高性能写。

写入流程

        put 操作，首先追加到写前日志（Write Ahead Log）并更新其结构，然后加到C0 层。当 C0 层的数据达到一定大小，就把 C0 层 和 C1 层合并，这个过程就是Compaction（合并），合并出来的新的C1 会顺序写磁盘，替换掉原来的C1。当 C1 层达到一定大小，会和下层继续合并，合并后删除旧的，留下新的。

查询流程

        最新的数据在 C0 层，最老的数据在 Cn 层。就算查询也是先查 C0 层，如果没有要查的数据，再查 C1，逐层查下去直到最后一层。

以读换写不是个好方案？

        LSM树充分利用了磁盘顺序写的特性，实现高吞吐写能力，数据写入后定期在后台合并（Compaction），在数据导入时全部是顺序append写，在后台合并时也是多个段merge sort后顺序写回磁盘。针对写快读慢特点，比较适合那些数据插入操作远多于数据更新/删除/读操作的场景。但是问题来了，读能力应该是大部分存储系统最应该保证的能力，所以用读换写似乎不是个好方案。

针对该问题，为了提高读取性能，LSM Tree采用了多种优化方案

1）Bloom filter

           是一种带随机概率的bitmap，可以快速的判断某一个小树里有没有指定的那个数据

   避免了更多的IO查找，只需经过几个哈希函数计算就能知道数据是否在某个小树里

   查询效率得到了提升，但需要付出额外的存储空间，和维护布隆过滤器。

    直通车：布隆过滤器原理介绍和典型应用案例-CSDN博客

2）compact

           查询的时候去读取多个小树会有性能问题，通过后台进程不断地将小树合并到大树上

   程序查询的时候就可以直接读取大树，从而提高读取性能。

写入流程

        核心关键在于先将数据的操作存到内存中，由log记录，同时触发相关的更新，例如布隆过滤器，方便后续查询。当内存的MemTable达到阈值时通过归并排序方式合并放到磁盘队尾，防止内存因断电等原因丢失数据，写入内存的数据同时会顺序在磁盘上预写日志（WAL)。

        然后就是正常的put 操作，先是追加到写前日志（Write Ahead Log）并更新其结构，然后加到C0 层。当 C0 层的数据达到一定大小，就把 C0 层 和 C1 层合并，这个过程就是Compaction（合并），合并出来的新的C1 会顺序写磁盘，替换掉原来的C1。当 C1 层达到一定大小，会和下层继续合并，合并后删除旧的，留下新的。（关键在于更新布隆过滤器）

查询流程

        核心关键在于LSM Tree提升读性能的优化策略主要是使用布隆过滤器、多路归并机制。进行查询时，先检查布隆过滤器，如果布隆过滤器报告数据不存在，则直接返回不存在。在查询时，先使用二分搜索检索对应的稀疏索引/平衡二叉树，找到数据所在的范围，再读取磁盘上该范围内的数据。

        最新的数据在 C0 层，最老的数据在 Cn 层，查询也是先查 C0 层，如果没有要查的数据，再查 C1，逐层查下去直到最后一层。（关键在于查询布隆过滤器）

与 B/B+ tree的对比

B-Tree/B+Tree 

        关系型数据库均以 B-Tree/B+Tree作为其构建索引的数据结构，大量数据下 B/B+ tree 提供了比较高的查询效率，但B-Tree/B+Tree 的相应缺点插入或删除一条数据时，均需要更新索引，需要一次随机磁盘 IO，所以B+tree 只适用于频繁读、较少写的场景，如果在多写少读的场景下，将造成大量的随机磁盘 IO，导致性能骤降。
LSM tree 

        充分利用了磁盘顺序写的特性，实现高吞吐写能力，数据写入后定期在后台Compaction，在数据导入时全部是顺序append写，在后台合并时也是多个段merge sort后顺序写回磁盘，避免了高并发写场景下的磁盘 IO 开销，查询效率无法达到O（logn），但依然非常快。

        本质上来说，LSM tree 牺牲了一部分查询性能，换取较高的写入性能, 在key-value 型或日志型数据库是非常重要的。

        其缺点在于读写都进行了放大，读取数据时实际读取的数据量大于真正的数据量，因为在LSM树中需要先在C0查看当前key是否存在，不存在继续从Cn层中寻找。写入数据时实际写入的数据量大于真正的数据量，在LSM树中写入时可能触发Compact操作，导致实际写入的数据量远大于该key的数据量。