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

雨点打透心脏的1/2处 2024-04-25 20:22 4阅读 0赞

![9f406d62247d47f4ab5448b99ae90928.png][]

**目录**

1.什么是LSM树？

2.LSM树的落地实现

--------------------

## 1.什么是LSM树？ ##

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

**LSM为什么会出现：**

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

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

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

![img][]

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

**原因如下：**

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

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

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

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

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

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

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

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

![1dc06eaccf3347038f46a79b38120319.png][]

## 2.LSM树的落地实现 ##

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

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

![b9665ae3dca24cf0b50466ca09db343c.png][]

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

![4e89c68d0e0d4b5f9b39f5c0d286251c.png][]

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

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

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

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

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

[9f406d62247d47f4ab5448b99ae90928.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/4dfbd88b43a04b2282507e5de2996397.png
[8_B_B_b_-CSDN]: https://blog.csdn.net/Joker_ZJN/article/details/128153273?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522171392695716800227474264%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=171392695716800227474264&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-1-128153273-null-null.nonecase&utm_term=B%2B&spm=1018.2226.3001.4450
[img]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/45c9645b8d2a47c9998d358a143cb7e0.png
[1dc06eaccf3347038f46a79b38120319.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/348d897d3a894eee82b6669ca79a76da.png
[b9665ae3dca24cf0b50466ca09db343c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/f54a0910f8a34b868c5a303874674237.png
[4e89c68d0e0d4b5f9b39f5c0d286251c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/49170e35d1544695a46a295d5574c9a5.png