Log structured merge tree
LSM Tree是一种基于排序和合并的数据存储方式，与一般数据存储引擎需要反复修改硬盘上的数据不同，LSM Tree的数据一旦写到磁盘上就不会再更改了。并且由于LSM Tree的数据都是连续写入到磁盘上的，因为磁盘的连续写入效率高于随机写入，所以LSMTree的数据写入速度往往高于BTree的数据写入速度；不过由于LSMTree的数据在查询时需要涉及到多个磁盘文件以及数据的合并操作，所以LSMTree的数据查询速度一般都会低于BTree的数据查询速度。
LSM Tree的核心原理分为以下几块
- 数据在内存中有序的保存，此时存储数据的部分叫做内存表（memtable）
- 内存中的数据达到一定条件之后会被写入到磁盘上的SSTable（Sorted String Table）中，这里的写入是连续写入
- 数据在SSTable中是有序的，所以可以给SSTable建立一个索引以提高数据查询速度
- 磁盘上SSTable达到了一定的条件之后会触发归并操作，即把多个较小的SSTable归并为一个大的SSTable
- 使用transaction log来避免内存中的数据丢失问题
memtable
因为数据需要有序的写入到SSTable中，所以在内存中我们就对数据进行有序的保存。内存中保存有序数据可选择的数据结构比较多，例如链表、红黑树等等，我们在这里选择使用SkipList。SkipList的复杂度和红黑树一样，但是实现起来更加简单。我们使用SkipList作为memtable，对于memtabl我们只需要使用其写入和查询方法即可。
SSTable
当内存中的memtable达到了一定的条件，例如占用的内存空间或者数据的条数达到了指定的要求之后，我们就会对memtabl中的数据进行序列化并把其有序的保存到SSTable中。因为这里的写入是连续批量写入，所以写入速度很快，一个SSTable一般对应着一个数据文件。
给SSTable建立索引
因为SSTable中的数据是有序的，所以我们在硬盘上创建数据文件的同时，也可以创建一个针对该数据文件的索引文件来提高数据查询时的效率。我们在索引文件中可以保存数据与该数据在数据文件中偏移的映射关系，并且由于数据文件中数据的存储是有序的，所以我们可以每隔n个数据创建一个索引，这样在索引文件中我们就得到了一个稀疏的数据文件中的数据位置信息。在查询数据时我们先到索引文件中查找指定的数据在数据文件中的偏移信息，由于数据是有序的所以我们通过索引能够把目标数据确定在数据文件中的某一个范围之内（或者在数据文件中不存在），这样就可以避免扫描整个数据文件，大大的提高了数据的查询速度。
SSTable的数据归并操作
由于硬盘上的数据文件一旦创建就不可以再更改，所以一段时间之后就有可能产生大量的数据文件，数据文件过多会影响查询速度，所以我们把一些数据文件合并为一个大的数据文件。与memtable写到硬盘中一样，数据合并也需要一定的触发条件，例如当文件数量达到了一定阈值我们就触发一次合并。
数据合并其实就是一个归并操作，我们从多个文件中取出每个文件中的当前最小值，然后对这些值进行比较，把比较得到的最小值写入到新的数据文件中，然后刚刚写入新数据文件的值所对应的旧数据文件再次取出一个最小值，之后进行下一轮的比较和写入，直到所有的源数据文件的数据都已经被处理完毕。当比较遇到同样的值的时候我们就会比较这些值的写入时间戳，时间戳较新的值被写入新的数据文件，时间戳较老的值被丢弃。在查询数据时当遇到同样的值的时候也一样需要比较数据的写入时间戳，查询结果使用时间戳最新的值。
在新的数据文件被成功的创建之后，删除所有老的被用于归并的数据文件。
translog
我们知道当我们写入数据时是写在memtable中的，当memtable达到一定的条件之后我们才会把其数据写到磁盘上的SSTable中。假如在写入到SSTable之前进程挂掉了，那么此时memtable中的数据就会丢失，解决办法是使用transaction log，translog的工作方式就是在数据写到memtable中的同时在磁盘上追加一条日志信息，这些日志信息是连续写入所以写入效率并不低。一旦进程飞掉memtable数据丢失，此时我们就可以从磁盘上的translog中恢复这部分数据。
当memtable中的数据被成功的写入到了SSTable之后，translog上面对应的日志信息就可以删除掉了。