代表数据库：nessDB、leveldb、hbase等

核心思想的核心是放弃部分读取能力，以换取写入最大化能力。 LSM Tree，这个概念是结构化决策树的意思，其核心思路其实非常简单，假设内存足够大。 因此，每次更新数据时都必须将数据写入磁盘，可以将最新的数据保存在内存中，存储到最后，再使用合并排序方式合并内存中的数据并添加到磁盘组的末尾。 (因为所有要排序的树都是有序的，可以通过合并排序方式快速合并) )。

日志结构的合并树(LSM-tree )是基于硬盘的数据结构，与B-tree相比，可以大幅减少硬盘的磁盘臂开销，提供长时间的文件高速插入(删除)。 但是，在某些情况下，LSM-tree的性能较差，尤其是在查询需要快速响应时。 LSM-tree通常适用于索引插入频率比搜索频率高的APP应用程序系统。 Bigtable在提供Tablet服务时使用GFS来存储日志和SSTable。 GFS希望通过添加新数据来修改文件，而不是重写旧数据。 LSM-tree通过使用滚动合并和多页块来延迟和批量更新索引，从而充分利用内存来存储最近或经常使用的数据，从而降低搜索成本，并使用硬盘来存储不经常使用的数据

磁盘的技术特性3360要充分发挥磁盘的技术特性，可以一次读取或写入固定大小的块数据，最大限度地减少随机寻道操作的次数。

LSM和Btree差异就要在读性能和写性能进行舍和求。在牺牲的同事，寻找其他方案来弥补。

1、LSM具有批量特性，有记忆延迟。 在写入读取的比例大的情况下(写入比读取多)，LSM树的性能比b树好。 这是因为随着insert操作，为了保持b树结构，节点会分裂。 随机读写磁盘的概率会变高，性能会下降。 实现了多次随机写、多次随机写，复用了磁盘寻优时间，大大提高了效率。

2、b树的写入过程：向b树的写入过程主要分为两个部分，首先找到对应的块的位置，然后将新的数据写入刚才找到的数据块，接着将块的对应盘的物理地址写入当然，如果内存足够，b树的一部分将缓存在内存中，因此有一定的概率在内存中完成查找块的过程，但为了清楚起见，我们假设内存很小，只能存储b树的一个块大小的数据上面的模式需要两次随机寻道(一次寻道、一次原位写入)才能完成一次数据写入，可见成本很高。

3、LSM Tree放弃了磁盘的读取性能以换取写入的顺序性，认为读取是大多数系统最应该保证的特性，所以读写交换似乎不是一笔好买卖。

a、内存速度远远超过磁盘，为1000倍以上。 读取性能的提高主要取决于内存命中率，而不是磁盘读取次数

b、写入时不占用磁盘I/o，会增加读取时间，获得磁盘I/o使用权，也提高读取效率。 例如，LevelDb的SSTable虽然降低了读取性能，但是如果保证数据的读取命中率的话，由于通过读取能得到很多盘I/o的机会，所以读取性能几乎没有降低，反而会提高。 写入的性能大幅提高，基本上是5~10倍左右。

下面说说详细例子：

LSM Tree得到了很多小的秩序结构。 例如，每m个数据，在内存中排序一次，接下来的100个数据，再排序一次……这样按顺序做下去，我就得到N/m个有序的小有序结构。

在调查的过程中，因为不知道这个数据在哪里，所以从最新的小秩序结构开始进行二分搜索，如果找不到就返回，如果找不到就继续寻找下一个小秩序结构，直到找到为止。

这种模式容易看出读出时间的复杂度为(N/m ) *log2N。 读取效率会下降。

这是最本来意义上的LSM tree的想法。 那么性能还很慢，需要再做点什么来提高。 我该怎么办？

LSM Tree优化方式：

答： Bloom filter:是一个带概率的bitmap，可以快速告诉你是否有被指定为某个小秩序结构的数据。 所以，不要用两点找，只需简单的计算几次，就可以知道数据是否在某个小集合里。 虽然提高了效率，但是花费了空间的成本。

b、由于compact:小树结合：小树存在性能问题，有一个过程不断将小树结合到大树上，大部分旧数据检索也可以直接采用log2N方式找到，不需要进行(N/m ) log2N的检索

哈希存储引擎是哈希表持久性，支持添加、删除、修改和随机读取操作，但不支持顺序扫描。 对应的存储系统是密钥值存储系统。 在key-value的插入和查询中，哈希表的复杂度都明显快于o(1)，树的操作o ) n )，如果不需要规则遍历数据，哈希表为your Mr.Right

B树存储引擎是B树(对于B树的由来、数据结构和应用场景可以看到前面的博客)的持久化的实现，不仅进行单一记录的追加、删除、读取、变更操作，还进行依次扫描()

LSM树(日志结构合并树)。

存储引擎和B树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。
通过以上的分析，应该知道LSM树的由来了，LSM树的设计思想非常朴素：将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，不过读取的时候稍微麻烦，需要合并磁盘中历史数据和内存中最近修改操作，所以写入性能大大提升，读取时可能需要先看是否命中内存，否则需要访问较多的磁盘文件。极端的说，基于LSM树实现的HBase的写性能比MySQL高了一个数量级，读性能低了一个数量级。

LSM树原理把一棵大树拆分成N棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。

以上这些大概就是HBase存储的设计主要思想，这里分别对应说明下：

因为小树先写到内存中，为了防止内存数据丢失，写内存的同时需要暂时持久化到磁盘，对应了HBase的MemStore和HLog
MemStore上的树达到一定大小之后，需要flush到HRegion磁盘中（一般是Hadoop DataNode），这样MemStore就变成了DataNode上的磁盘文件StoreFile，定期HRegionServer对DataNode的数据做merge操作，彻底删除无效空间，多棵小树在这个时机合并成大树，来增强读性能。

关于LSM Tree，对于最简单的二层LSM Tree而言，内存中的数据和磁盘你中的数据merge操作，如下图

lsm tree，理论上，可以是内存中树的一部分和磁盘中第一层树做merge，对于磁盘中的树直接做update操作有可能会破坏物理block的连续性，但是实际应用中，一般lsm有多层，当磁盘中的小树合并成一个大树的时候，可以重新排好顺序，使得block连续，优化读性能。

hbase在实现中，是把整个内存在一定阈值后，flush到disk中，形成一个file，这个file的存储也就是一个小的B+树，因为hbase一般是部署在hdfs上，hdfs不支持对文件的update操作，所以hbase这么整体内存flush，而不是和磁盘中的小树merge update，这个设计也就能讲通了。内存flush到磁盘上的小树，定期也会合并成一个大树。整体上hbase就是用了lsm tree的思路。