LSM简介
Log Structured Merge Tree，下面简称 LSM。2006年，Google 发表了 BigTable 的论文。这篇论文提到 BigTable 单机上所使用的数据结构就是 LSM。目前，LSM 被很多存储产品作为存储结构，比如 Apache HBase, Apache Cassandra, MongoDB 的 Wired Tiger 存储引擎, LevelDB 存储引擎, RocksDB 存储引擎等。简单地说，LSM 的设计目标是提供比传统的 B+ 树更好的写性能。LSM 通过将磁盘的随机写转化为顺序写来提高写性能 ，而付出的代价就是牺牲部分读性能、写放大（B+树同样有写放大的问题）。LSM 相比 B+ 树能提高写性能的本质原因是：外存，其随机读写都要慢于顺序读写，无论磁盘还是 SSD。
三种基本的存储引擎
1、哈希存储引擎
是哈希表的持久化实现，支持增、删、改以及随机读取操作，但不支持顺序扫描，对应的存储系统为key-value存储系统。对于key-value的插入以及查询，哈希表的复杂度都是O(1)，明显比树的操作O(n)快，如果不需要有序的遍历数据，哈希表就是正确的选择。
2、B树存储引擎
是B树的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针），对应的存储系统就是关系数据库（Mysql等）。
3、LSM树存储引擎
和B树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能，并且不容易支持事务。
LSM树（Log Structured Merge Tree，结构化合并树）的思想非常朴素，就是将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘（由此提升了写性能），是一种基于硬盘的数据结构，与B-tree相比，能显著地减少硬盘磁盘臂的开销。读取时需要合并磁盘中的历史数据和内存中最近的修改操作，读取时可能需要先看是否命中内存，否则需要访问较多的磁盘文件（存储在磁盘中的是许多小批量数据，由此降低了部分读性能。但是磁盘中会定期做merge操作，合并成一棵大树，以优化读性能）。LSM树的优势在于有效地规避了磁盘随机写入问题，但读取时可能需要访问较多的磁盘文件。
LSM tree的核心特点：
- 将索引分为内存和磁盘两部分，并在内存达到阈值时启动树合并（Merge Trees）；
- 用批量写入代替随机写入，并且用预写日志 WAL 技术（Elasticsearch 中为 translog 事务日志）保证内存数据，在系统崩溃后可以被恢复；
-
数据采取类似日志追加写的方式写入（Log Structured）磁盘，以顺序写的方式提高写入效率。
LSM.png
