一.什么是LSM树?
LSM全称为"Log-Structured Merged-Tree"．后来被Google发表的BigTable论文发扬广大．LSM相对于B+树而言，LSM树在损失部分读性能的前提下尽可能的提高写性能，将随机写转换为顺序写.
LSM树主要应用于写多读少的情况．
二.LSM树的基本思想
LSM树将所有的数据的插入，删除，修改等操作保存在内存之中，当操作达到一定的阀值，批量的写入磁盘之中．而在写入磁盘的时候，达到一定的阀值会进行合并，对于磁盘文件不进行修改.
三.LSM树如何组织起来?
LSM树的结构是横跨内存和磁盘的，其中包含了memtable,sstable,log,bloom_fifter组件，下述将会讨论这些组件应该如何实现?
在内存中如何存储?
-
首先介绍一下
memtable这一组件，它是在内存中的数据结构，用来保存最近的一些更新操作．当写数据到memtable中，必须先写入磁盘中的Log(这里我们可以采用写穿的方式,例如O_SYNC或者fsync直接去磁盘进行交互),防止数据因为掉电而丢失. -
memtable一般是需要有序的，这样在落入磁盘的时候是可以加快读取速率的，我们可以通过跳表或者搜索树等数据结构来组织数据保持有序性，当memtable达到一定量的时候，转化为unmemtable，同时我们创建新的memtable来处理内存的写入. -
unmemtable在内存中是不可修改的数据结构,它将memtable转换为sstable 的一种中间状态.为了在转存过程中不阻塞写操作，写操作可以由新的memtable进行处理,而转换过的unmemtable逐步的写入
索引如何建立?
- 首先我们开始想到的是在内存中建立索引，但是很明显这种办法是行不通的．想要内存中建立索引，就必须保证索引可以在内存中存入，并且在更新的时候，需要大量的
随机访问磁盘I/O - 我们可以采用磁盘索引的方式，如果数据文件本身就是有序存放的，我们可以不用给每一个key 建立索引．我们可以将key 划分若干个block,只需要建立
block的索引和block中的部分key的索引. - 我们可以通过
布隆过滤器加快查找键在块的位置，之后在block中进行搜索即可.
在LSM树，我们可以把按序组织的数据文件称为sstable,只保存block中的部分键的索引.
假设你正在内存中寻找键 handiwork ， 但是你不知道段文件中该关键字的确切偏移量。然而， 你知道 handbag 和 handsome 的偏移， 而且由于排序特性， 你知道 handiwork必须出现在这两者之间。 这意味着您可以跳到 handbag 的偏移位置并从那里扫描， 直到您找到 handiwork （ 或没找到， 如果该文件中没有该键） 。
我们可以针对整个文件或者块进行相应的压缩，减少磁盘的利用率．
日志应该如何组织?
- LSM树中的
log的中的数据一般为乱序，它是为了保证断电的时候的数据恢复 - 将对于键的操作写入log之中，若部分键落在磁盘之后，可以在
日志中清除相应的数据，防止日志过度膨胀,
布隆过滤器的作用?
- 首先我们可以思考一个问题，如何快速的判断一个key是不是存在某个集合?可能大部分同学都会回答
HashMap吧，的确,HashMap是一个好的方案，它可以通过O(1)的时间复杂度返回结果，效率相当不错．但是如果数据量相当庞大的情况下? - 因为负载因子的存在，这时候的HashMap的空间是不能被用满的，也就是说内存的占用是十分庞大的．
- 我们可以利用布隆过滤器来达到这一需求，布隆过滤器实际上是一个位数组或者可以称之为位变量，布隆过滤器通过对键的hash得到相应的值，将那个值所对应的位置置为１．
- 我们通过判断位置是不是为１，来确定这个key是不是在这个集合之中.
四.LSM树的增删改查
写入操作
- 写操作首先需要将数据写入Log 中，防止数据丢失，然后数据被写入到内存的memtable 中的，这样一次写操作已经完成了，只需要１次磁盘IO,再加上１次内存操作. 相比较B+树的多次磁盘随机IO,大大提高了效率.
删除操作
- 当有删除操作的时候，并不需要B+树一样，在磁盘中找到相应的数据后再删除，只需要在memtable中插入一条数据当作标志．当读操作读取之后，会知道这个key已经被删除了．在日志合并的过程中，内存中被删除的数据会在磁盘中删除.
更新操作
- 操作memtable,写入一个标志，随后真正的更新操作会被延迟在合并一并完成．
查询操作
- 查询操作就比较慢了，LSM树主要是通过牺牲读性能而提高写性能，需要从内存表，磁盘中读取．
- 我们可以通过二分法+布隆过滤器提高速率．
合并操作
- 合并内存中的数据到磁盘中
- 将内存数据合并到磁盘中会产生大量小的集合，并且更新和删除操作会产生大量的冗余数据，通过合并可以介绍之前的冗余数据．
目前比较广泛的两种策略, size_tiered策略和leveled策略
size_tiered策略
当某个规模的集合达到一定的数量，合并为一个大的集合，缺点会变得很耗时.
leveled策略
分层进行合并，在本层选出一个文件和下一层合并或者直接提升，不会重复，更新的时候发现数据冲突，直接丢弃掉．