传统关系型数据库大都使用B-Tree或其变体作为存储结构，能够进行高效查找。但保存在磁盘中时它也有一个明显的缺陷，那就是逻辑上相离很近但物理却可能相隔很远，这就可能造成大量的磁盘随机读写。因此对于关系型数据库来说随机读写比顺序读写慢很多，为了提升IO性能，我们需要一种能将随机操作变为顺序操作的机制，于是便有了本篇要讲的LSM树。LSM树能让我们进行顺序写磁盘，从而大幅提升写操作，作为代价的是牺牲了一些读性能。因此在大数据生态下，很多数据库引擎都是使用LSM树存储引擎。
数据结构（一）、二叉树（BT），二叉查找树（BST），平衡二叉树（AVL树）
数据结构（二）、红黑树（RBT）
数据结构（三）、B树，B+树，B*树
背景年，一篇名为TheLogStructuredMergeTree（LSM-tree）的论文创造性地提出了日志结构合并树（LogStructuredMergeTree）的概念，该方法既吸收了日志结构方法的优点，又通过将数据文件预排序克服了日志结构方法随机读性能较差的问题。尽管当时LSM-tree新颖且优势鲜明，但它真正声名鹊起却是在10年之后的年，那年谷歌的一篇使用了LSM-tree技术的论文Bigtable:ADistributedStorageSystemforStructuredData横空出世，在分布式数据处理领域掀起了一阵旋风，随后两个声名赫赫的大数据开源组件（年的HBase与年的Cassandra，目前两者同为Apache顶级项目）直接在其思想基础上破茧而出，彻底改变了大数据基础组件的格局，同时也极大地推广了LSM-tree技术。
LSM树相比B+树能提高写性能的本质原因是：无论是磁盘还是SSD，都有随机读写慢，顺序读写快的问题。
存储引擎目前常见的主要的三种存储引擎是：
哈希存储引擎：哈希表的持久化实现，支持增、删、改以及随机读取操作，但不支持顺序扫描，对应的存储系统为key-value存储系统。对于key-value的插入以及查询，哈希表的复杂度都是O(1)，明显比树的操作O(n)快,如果不需要有序的遍历数据，哈希表就是正确的选择。
B树存储引擎：B树的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针），对应的存储系统就是关系数据库（如：Mysql）。
LSM树存储引擎：和B+树存储引擎一样，支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利就有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。
原理LSM树真正发扬光大是从Google的BigTable论文起：
由图上可以看出，LSM树的读写原理分解下来就是下面几个步骤：
写请求操作：
先将数据写入log文件，当内存储中的memtable数据丢失时可以从log文件中恢复。log文件中的数据不会进行排序；
将数据写入内存储中的memtable，若命中数据则更新，否则插入新数据。memtable中的数据会按key值排序，通常使用AVL，红黑树的数据结构进行索引；
当memtable的大小达到一定规模时会将数据连同索引一起写入磁盘，即sstable文件；
memtable的数据持久化sstable中后，log文件中的内容被清空；
后台