【大数据】LSM树，专为海量数据读写而生的数据结构

1.什么是LSM树？

LSM树（Log-Structured Merge Tree）是一种专门针对大量写操作做了优化的数据存储结构，尤其适用于现代大规模数据处理系统，如NoSQL数据库（如Cassandra、HBase、RocksDB等）和键值存储。尽管其名称中包含“树”，但它并不直接对应于传统的树状数据结构，而是指一种数据管理策略或体系架构。

LSM为什么会出现：

当数据量大了之后，读操作采用顺序遍历来进行查找肯能是不行的，性能太低了。所以需要维护一种数据结构用来帮助提升读的效率，在关系型数据库中用B+树（索引）来维护数据的关系，便于查找。

B树和B+树详细内容可移步作者的另一篇文章，作者有个数据结构专栏，专门讲解了所有常用数据结构：

数据结构（8）树形结构——B树、B+树（含完整建树过程）_排序好的数怎么画b+树-CSDN博客

关系型数据库中对B+树的使用在读的时候性能不错，但是在写的时候存在明显的性能问题。不是说B+树这种数据结构在写的时候存在性能问题，而是关系型数据库中是将树结构存在磁盘上的，并且树的节点在磁盘上的存储是分散的，数据的存储也是分散的，这种落地方式在面对写操作的时候会有性能瓶颈。

原因如下：

首先是写操作。写操作是容易引起B+树的结构的调整的，要调整树的结构当然要去读写树的节点，树的整个结构都存在磁盘上的，所以要走磁盘IO，调整树当然就要去对磁盘上存的树的节点进行读写，B+树在磁盘中的存储是分散的，所以这里的IO是随机IO。写数据的时候，数据也不是顺序存放的，也是分散存放的，也会是随机IO。

其次是读操作，即使B+树尽力优化了树的层高，减少了磁盘IO次数，但是毕竟树的节点和数据不是顺序写入进行存储的，所以在访问的时候还是会进行随机IO，在关系型数据库的场景下倒是没什么问题，在大数据场景下要读的数据量是海量的，海量数据都是进行随机IO的读，性能上来说也是不佳的。

所以在海量数据的写入的时候B+树不是一个优质的选择。对着大数据场景的出现，LSM树出现，用于专门应对海量数据的写入。

总结一下B+树面对海量数据无力是因为：

• 树存在磁盘上，读写都是磁盘IO
• 树是分散存放的，读写都是随机IO
• 数据是分散存放的，读写都是随机IO

LSM树其实就是一套打法，核心目的就是为了规避上面的问题。

LSM树会将树结构放在内存中，从而规避磁盘IO，当然内存是有限的，到了一定条件后会将当前内存中这个版本的树存到磁盘中，存磁盘的时候开辟一块连续空间，将树的节点连续存储在一起，然后刷新内存再重新开始存新进来的内容。读的时候就会先去读内存，内存中没有再去读磁盘。由于磁盘中树的节点是连续写在一起的，会减少随机IO。

当在落磁盘的时候，磁盘上如果有历史版本的话，会和最新的历史版本进行合并。也就是说越新的历史版本，树越”茂盛“：

2.LSM树的落地实现

LSM树的落地实现通常包含内存中的MemTable（内存表）和磁盘上的SSTable（Sorted String Table，有序字符串表）两部分。

数据首先写入内存中的MemTable，数据在memtable中就会被组织成平衡二叉树：

当MemTable达到一定大小时，会被转换为不可变的SSTable并刷写到磁盘，写入磁盘的时候会开辟一段连续的存储空间，将树的内容连续存储在一起：

除了上面的内容外，还有一个核心内容——Compaction，合并。

由于肯定会落多次磁盘，生成多个版本的sstable，会浪费磁盘空间，所以还会存在合并操作，将多棵小树合成一棵大树。合并的时机一般有两个：

一个时机是在落磁盘生成新的sstable的时候会和之前最新的历史版本对应的sstable进行一次合并，两棵小树合并出一棵大树来。另一个时机是磁盘的存储达到一定阈值之后多个历史版本的sstable会进行合并合并出一棵大树来。

还有最后一个问题就是如何删除LSM树中的元素？

在memtable中删除了，但是sstable中还有，直接删除是没有用的，下次合并的时候还是会把已经删除的元素合并进来。所以LSM的做法是给要删除的元素打上一个墓碑标记，墓碑标记用来标记数据被删除了，下次合并的时候就能通过墓碑标记来判断哪些元素不用合并进来。