【数据结构】深入浅出LSM

前言

        在数据库或搜索引擎的存储过程中会很多数据结构,而NoSql数据库对LMS结构非常青睐，如RocksDB、LevelDB、HBase以及Prometheus等其底层的存储引擎都是基于LSM树。本文就来详细了解一下何为LMS，以及它的优缺点和使用范围。

简介

        LSM一般的名字叫 Log Structured-Merge Tree（日志结构合并树），来源于分布式数据库领域，也是BigTable 的论文中所使用的文件组织方式。它的特点在于写入的时候是append only的形式，就像名字所显示的那样，跟日志一样只在文件后面追加。LSM树并不像B+树、红黑树一样是一颗严格的树状数据结构，它其实是一种存储结构。LSM树的核心特点是利用顺序写来提高写性能，但因为分层(此处分层是指的分为内存和文件两部分)的设计会稍微降低读性能，但是通过牺牲小部分读性能换来高性能写，使得LSM树成为非常流行的存储结构。

LSM树的核心思想

如图所示,在 LSM 树中，MemTable、Immutable MemTable 和 SSTable（Sorted String Table）是三个重要的概念。

Memtable

        LSM树中的内存缓存，用于暂存新插入的键值对，以减少频繁写入磁盘的IO操作。MemTable通常采用哈希表或平衡树等数据结构实现，可以很快速地进行键值对的插入和查找。当MemTable达到容量限制后，其中的键值对将会被排序后写入Immutable MemTable或SSTable中。

Immutable MemTable

        一旦MemTable达到容量限制，它就会被“冻结”成为一个不可修改的immutable MemTable，同时系统会在后台创建一个新的空白的Mutable MemTable供后续写入使用。Immutable MemTable中的键值对是按照键升序排列的，这样可以方便地进行二分查找和归并操作。

SSTable

        LSM树中持久化存储的部分，包含一组已经排好序的键值对列表。由于SSTable中的键值对是有序的，因此可以采用较为高效的二分查找算法进行查询。另外，SSTable还支持key-range删除操作，即可以通过标记某个键值对被删除，在合并操作时统一进行处理。除此之外，SSTable还拥有其他高级特性，如布隆过滤器和索引块等。

总结

        MemTable、Immutable MemTable和SSTable都是LSM树中非常重要的概念。其中MemTable和Immutable MemTable用于加速新数据的写入操作，而SSTable则是LSM树中持久化存储部分的核心，通过SSTable中的键值对列表，支持高效的查询和删除操作。

LSM树的Compact策略

        在LSM树中，Compact是一种重要的策略，用于减少存储空间的浪费和提高查询性能。Compact操作主要通过合并多个SSTables以及删除已经过期或无效的数据来实现。

常见的Compact策略有以下几种：

1. 1. 1. Level 0 Compaction：Level 0 Compaction是指将相邻的Immutable MemTable和SSTable进行归并操作。这种方式能够在磁盘上创建更大的文件块，从而提高查询性能，但可能会导致数据重复和存储空间的浪费。

      2. Level N Compaction：Level N Compaction是指将位于同一层级（Level）的多个SSTable进行归并操作。这种方式能够在不同的层级之间移动数据，从而进一步减少冗余数据和存储空间的浪费，同时也能够降低查询延迟。

      3. Size-Tiered Compaction：Size-Tiered Compaction是一种基于SSTable大小的Compaction策略，即按照SSTable大小分成不同的层级进行归并。这种策略可以有效地减少存储空间的浪费，但可能会导致数据读取性能下降。

      4. Time-Based Compaction：Time-Based Compaction是一种基于时间戳和数据过期时间的Compaction策略，即将已经过期或无效的数据从SSTable中删除。这种策略可以有效地减少不必要的磁盘I/O和存储空间使用，同时也能够确保数据的正确性和一致性。

         
         

        综上所述，LSM树的Compact策略可以根据具体应用场景和需求选择不同的方式进行优化。同时，在实际应用中，还需要考虑到吞吐量、查询延迟、存储空间等多个因素来选择最合适的Compact策略。

 Immutable MemTable","vertex":"1"},"J8FW3ixg":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"656","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"J8FW3ixg","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"JVfDYOhD":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"695","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"JVfDYOhD","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"K8sXvLQW":{"-0-mxGeometry":{"-0-mxPoint":{"as":"offset","x":"12"},"as":"geometry","relative":"1","x":"-0.2","y":"8"},"connectable":"0","id":"K8sXvLQW","parent":"e5m4ovba","style":"edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];","value":"full","vertex":"1"},"KgmDTNLk":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"800","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"KgmDTNLk","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"L7wnDVq3":{"-0-mxGeometry":{"as":"geometry","height":"50","width":"185","x":"312.5","y":"120"},"diagramCategory":"general","diagramName":"text","id":"L7wnDVq3","parent":"Pect1uf9","style":"text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;","value":"Memory（内存）","vertex":"1"},"LHXE1mhw":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"800","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"LHXE1mhw","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"MQPnf5y5":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"761","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"MQPnf5y5","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"MgK8Cvdh":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"826","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"MgK8Cvdh","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"O1lYllFT":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"117","x":"630","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"O1lYllFT","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;","value":"","vertex":"1"},"OMpCtE3t":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"643","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"OMpCtE3t","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"ONFVf0mt":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"643","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"ONFVf0mt","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"OQvuPBTX":{"-0-mxGeometry":{"as":"geometry","relative":"1"},"edge":"1","id":"OQvuPBTX","parent":"Pect1uf9","source":"iXKXZi1R","style":"edgeStyle=orthogonalEdgeStyle;rounded=0;orthogonalLoop=1;jettySize=auto;html=1;exitX=0.5;exitY=1;exitDx=0;exitDy=0;","target":"iXKXZi1R"},"P0F0T5OX":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"945","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"P0F0T5OX","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"Pect1uf9":{"id":"Pect1uf9","parent":"Xfazc13W"},"PwkmoKfk":{"-0-mxGeometry":{"-0-mxPoint":{"as":"targetPoint","x":"230","y":"430"},"as":"geometry","relative":"1"},"edge":"1","id":"PwkmoKfk","parent":"Pect1uf9","source":"ZuarnUSf","style":"edgeStyle=orthogonalEdgeStyle;curved=1;orthogonalLoop=1;jettySize=auto;html=1;entryX=0;entryY=0.5;entryDx=0;entryDy=0;","target":"GF2B9Rh4","value":""},"QNCh50pP":{"-0-mxGeometry":{"-0-mxPoint":{"as":"targetPoint","x":"230","y":"240"},"as":"geometry","relative":"1"},"edge":"1","id":"QNCh50pP","parent":"Pect1uf9","source":"F5z9GePl","style":"edgeStyle=orthogonalEdgeStyle;curved=1;orthogonalLoop=1;jettySize=auto;html=1;","target":"xWaQTopQ","value":""},"QW0GZfYt":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"839","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"QW0GZfYt","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"RjZ0cfXI":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"669","y":"300"},"diagramCategory":"general","diagramName":"Rectangle","id":"RjZ0cfXI","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"RvY59spi":{"-0-mxGeometry":{"-0-mxPoint":{"as":"sourcePoint","x":"560","y":"310"},"-1-mxPoint":{"as":"targetPoint","x":"530","y":"300"},"as":"geometry","height":"50","relative":"1","width":"50"},"diagramCategory":"general","diagramName":"straight","edge":"1","id":"RvY59spi","parent":"Pect1uf9","source":"hLHDkT3C","style":"endArrow=none;html=1;exitX=1.006;exitY=0.307;exitDx=0;exitDy=0;exitPerimeter=0;entryX=0;entryY=0.307;entryDx=0;entryDy=0;entryPerimeter=0;","target":"hLHDkT3C","value":""},"S3JVeyfK":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"643","y":"300"},"diagramCategory":"general","diagramName":"Rectangle","id":"S3JVeyfK","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"S7yVTdKA":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"669","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"S7yVTdKA","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"TzBl5Fkr":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"695","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"TzBl5Fkr","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"X5F6Ggu9":{"-0-mxGeometry":{"as":"geometry","height":"30","width":"125","x":"643","y":"260"},"diagramCategory":"general","diagramName":"text","id":"X5F6Ggu9","parent":"Pect1uf9","style":"text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;","value":"SSTable(Sorted String Table)","vertex":"1"},"XfVZIw0G":{"-0-mxGeometry":{"as":"geometry","height":"460","width":"280","x":"250","y":"110"},"diagramCategory":"general","diagramName":"Rectangle","id":"XfVZIw0G","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#FFCCCC;","value":"","vertex":"1"},"Xfazc13W":{"id":"Xfazc13W"},"Xll5cLm4":{"-0-mxGeometry":{"as":"geometry","height":"50","width":"185","x":"740","y":"120"},"diagramCategory":"general","diagramName":"text","id":"Xll5cLm4","parent":"Pect1uf9","style":"text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;","value":"Disk（磁盘）","vertex":"1"},"Xt2HNi6L":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"708","y":"300"},"diagramCategory":"general","diagramName":"Rectangle","id":"Xt2HNi6L","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"ZSVchtDT":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"669","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"ZSVchtDT","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"ZVTJU4Ju":{"-0-mxGeometry":{"-0-mxPoint":{"as":"offset"},"as":"geometry","relative":"1","x":"0.2391","y":"-12"},"connectable":"0","id":"ZVTJU4Ju","parent":"E6XCgje0","style":"edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];","value":"flash","vertex":"1"},"ZgrdusNh":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"958","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"ZgrdusNh","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"ZuarnUSf":{"-0-mxGeometry":{"as":"geometry","height":"80","width":"120","x":"30","y":"390"},"diagramCategory":"general","diagramName":"oval","id":"ZuarnUSf","parent":"Pect1uf9","style":"ellipse;whiteSpace=wrap;html=1;fillColor=#FFCCFF;","value":"read","vertex":"1"},"b1NtkJEO":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"656","y":"300"},"diagramCategory":"general","diagramName":"Rectangle","id":"b1NtkJEO","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"cbVCYMy5":{"-0-mxGeometry":{"as":"geometry","height":"20","width":"40","x":"717","y":"510"},"diagramCategory":"general","diagramName":"text","id":"cbVCYMy5","parent":"Pect1uf9","style":"text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;","value":"L1","vertex":"1"},"cqTOeDif":{"-0-mxGeometry":{"-0-mxPoint":{"as":"targetPoint","x":"90","y":"310"},"as":"geometry","relative":"1"},"edge":"1","id":"cqTOeDif","parent":"Pect1uf9","source":"ZuarnUSf","style":"edgeStyle=orthogonalEdgeStyle;curved=1;orthogonalLoop=1;jettySize=auto;html=1;entryX=0;entryY=0.5;entryDx=0;entryDy=0;","target":"xWaQTopQ","value":""},"d85j3v9e":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"682","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"d85j3v9e","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"dWqZNSJs":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"893","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"dWqZNSJs","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"djk22V9P":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"826","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"djk22V9P","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"e5m4ovba":{"-0-mxGeometry":{"-0-mxPoint":{"as":"sourcePoint","x":"320","y":"330"},"-1-mxPoint":{"as":"targetPoint","x":"370","y":"280"},"as":"geometry","height":"50","relative":"1","width":"50"},"diagramCategory":"general","diagramName":"arrow","edge":"1","id":"e5m4ovba","parent":"Pect1uf9","source":"xWaQTopQ","style":"shape=flexArrow;endArrow=classic;html=1;entryX=0.5;entryY=0;entryDx=0;entryDy=0;","target":"GF2B9Rh4","value":""},"fIKshuy3":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"708","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"fIKshuy3","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"feCcgpcE":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"787","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"feCcgpcE","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"h5HW04jB":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"88","x":"686","y":"180"},"diagramCategory":"Flowchart","diagramName":"Multi-Document","id":"h5HW04jB","parent":"Pect1uf9","style":"shape=mxgraph.flowchart.multi-document;whiteSpace=wrap;html=1;fillColor=#ffffff;strokeColor=#000000;strokeWidth=2","value":"WAL","vertex":"1"},"hLHDkT3C":{"-0-mxGeometry":{"as":"geometry","height":"460","width":"460","x":"602.5","y":"110"},"diagramCategory":"general","diagramName":"Rectangle","id":"hLHDkT3C","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFFF;","value":"","vertex":"1"},"iCIizIcM":{"-0-mxGeometry":{"-0-mxPoint":{"as":"targetPoint","x":"90","y":"550"},"as":"geometry","relative":"1"},"edge":"1","id":"iCIizIcM","parent":"Pect1uf9","source":"ZuarnUSf","style":"edgeStyle=orthogonalEdgeStyle;curved=1;orthogonalLoop=1;jettySize=auto;html=1;","target":"z1yTddZZ","value":""},"iKJnRWIw":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"88","x":"910","y":"180"},"diagramCategory":"Flowchart","diagramName":"Multi-Document","id":"iKJnRWIw","parent":"Pect1uf9","style":"shape=mxgraph.flowchart.multi-document;whiteSpace=wrap;html=1;fillColor=#ffffff;strokeColor=#000000;strokeWidth=2","value":"WAL","vertex":"1"},"iXKXZi1R":{"-0-mxGeometry":{"as":"geometry","height":"20","width":"40","x":"950","y":"330"},"diagramCategory":"general","diagramName":"text","id":"iXKXZi1R","parent":"Pect1uf9","style":"text;html=1;strokeColor=none;fillColor=none;align=center;verticalAlign=middle;whiteSpace=wrap;rounded=0;","value":"

Compacttion

","vertex":"1"},"iymhHcBA":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"813","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"iymhHcBA","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"kexlG0dj":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"708","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"kexlG0dj","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"knulpQ0s":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"117","x":"630","y":"300"},"diagramCategory":"general","diagramName":"Rectangle","id":"knulpQ0s","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;","value":"","vertex":"1"},"lSp84QBb":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"761","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"lSp84QBb","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"n6DQLOMF":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"630","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"n6DQLOMF","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"nvisUk5W":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"774","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"nvisUk5W","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"opPVFQV5":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"117","x":"761","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"opPVFQV5","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;","value":"","vertex":"1"},"rJxOHCJY":{"-0-mxGeometry":{"as":"geometry","height":"120","width":"120","x":"906","y":"280"},"diagramCategory":"BPMN general","diagramName":"LoopMarker","id":"rJxOHCJY","parent":"Pect1uf9","style":"shape=mxgraph.bpmn.loop;html=1;outlineConnect=0;fillColor=#CCFFCC;perimeterSpacing=500;strokeWidth=1;","value":"","vertex":"1"},"rlMMKrfY":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"117","x":"761","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"rlMMKrfY","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;","value":"","vertex":"1"},"tQjbJVPS":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"682","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"tQjbJVPS","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"u674ONpY":{"-0-mxGeometry":{"-0-mxPoint":{"as":"offset"},"as":"geometry","relative":"1","x":"0.2912","y":"-11"},"connectable":"0","id":"u674ONpY","parent":"E6XCgje0","style":"edgeLabel;html=1;align=center;verticalAlign=middle;resizable=0;points=[];","value":"","vertex":"1"},"vYHaxAHY":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"117","x":"893","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"vYHaxAHY","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;","value":"","vertex":"1"},"vYhmaqlq":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"839","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"vYhmaqlq","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"w1aUI3q3":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"932","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"w1aUI3q3","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"wzdb3Zcu":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"774","y":"390"},"diagramCategory":"general","diagramName":"Rectangle","id":"wzdb3Zcu","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"xWaQTopQ":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"170","x":"305","y":"200"},"diagramCategory":"general","diagramName":"RoundedRectangle","id":"xWaQTopQ","parent":"Pect1uf9","style":"rounded=1;whiteSpace=wrap;html=1;","value":"Active MemTable","vertex":"1"},"xrDvOwDw":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"13","x":"919","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"xrDvOwDw","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;fillColor=#CCFFCC;","value":"","vertex":"1"},"z1yTddZZ":{"-0-mxGeometry":{"as":"geometry","height":"80","width":"120","x":"330","y":"450"},"diagramCategory":"general","diagramName":"Cube","id":"z1yTddZZ","parent":"Pect1uf9","style":"shape=cube;whiteSpace=wrap;html=1;boundedLbl=1;backgroundOutline=1;darkOpacity=0.05;darkOpacity2=0.1;size=10;","value":"Block cache","vertex":"1"},"z5NfmNS4":{"-0-mxGeometry":{"as":"geometry","height":"60","width":"117","x":"630","y":"490"},"diagramCategory":"general","diagramName":"Rectangle","id":"z5NfmNS4","parent":"Pect1uf9","style":"rounded=0;whiteSpace=wrap;html=1;","value":"","vertex":"1"}}},"diagramType":"flowchart"}}},"LK8kda4I0oiSu6xm4gBcilhvnDc":{"id":"LK8kda4I0oiSu6xm4gBcilhvnDc","snapshot":{"type":"text","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+29"},"text":{"0":"如图所示,在 LSM 树中，MemTable、Immutable MemTable 和 SSTable（Sorted String Table）是三个重要的概念。"}}},"align":"","folded":false,"text_indent":1}},"WMYkdSEMyogosmxAZJtca3FCn3b":{"id":"WMYkdSEMyogosmxAZJtca3FCn3b","snapshot":{"type":"heading3","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+8"},"text":{"0":"Memtable"}}},"align":"","folded":false}},"ZqsSdQeK0oqqeExEd8HcBoDAnCc":{"id":"ZqsSdQeK0oqqeExEd8HcBoDAnCc","snapshot":{"type":"text","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+3y"},"text":{"0":"LSM树中的内存缓存，用于暂存新插入的键值对，以减少频繁写入磁盘的IO操作。MemTable通常采用哈希表或平衡树等数据结构实现，可以很快速地进行键值对的插入和查找。当MemTable达到容量限制后，其中的键值对将会被排序后写入Immutable MemTable或SSTable中。"}}},"align":"","folded":false,"text_indent":1}},"KmgadKECEo8SUqxUrhEcpfX3nyb":{"id":"KmgadKECEo8SUqxUrhEcpfX3nyb","snapshot":{"type":"heading3","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+i"},"text":{"0":"Immutable MemTable"}}},"align":"","folded":false}},"EOcwdi6gYosgqixIBoKck7yknOb":{"id":"EOcwdi6gYosgqixIBoKck7yknOb","snapshot":{"type":"text","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":2,"numToAttrib":{"0":["author","6976464396953960476"],"1":["textHighlightBackground","rgba(183,237,177,0.8)"]}},"initialAttributedTexts":{"attribs":{"0":"*0+3d*0*1+4*0+6*0*1+e*0+1"},"text":{"0":"一旦MemTable达到容量限制，它就会被“冻结”成为一个不可修改的immutable MemTable，同时系统会在后台创建一个新的空白的Mutable MemTable供后续写入使用。Immutable MemTable中的键值对是按照键升序排列的，这样可以方便地进行二分查找和归并操作。"}}},"align":"","folded":false,"text_indent":1}},"BEQWdOEswo8OMixYhTdceiBOnIf":{"id":"BEQWdOEswo8OMixYhTdceiBOnIf","snapshot":{"type":"heading3","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+7"},"text":{"0":"SSTable"}}},"align":"","folded":false}},"NGocdKesKoguOGx0kIbc7u9QnZb":{"id":"NGocdKesKoguOGx0kIbc7u9QnZb","snapshot":{"type":"text","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+4h"},"text":{"0":"LSM树中持久化存储的部分，包含一组已经排好序的键值对列表。由于SSTable中的键值对是有序的，因此可以采用较为高效的二分查找算法进行查询。另外，SSTable还支持key-range删除操作，即可以通过标记某个键值对被删除，在合并操作时统一进行处理。除此之外，SSTable还拥有其他高级特性，如布隆过滤器和索引块等。"}}},"align":"","folded":false,"text_indent":1}},"VG2md006CoYSoKxGEfJcJ6i0n1d":{"id":"VG2md006CoYSoKxGEfJcJ6i0n1d","snapshot":{"type":"heading3","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+2"},"text":{"0":"总结"}}},"align":"","folded":false}},"N08Wdm4w8oSmwWxi2zDcOszInSe":{"id":"N08Wdm4w8oSmwWxi2zDcOszInSe","snapshot":{"type":"text","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+44"},"text":{"0":"MemTable、Immutable MemTable和SSTable都是LSM树中非常重要的概念。其中MemTable和Immutable MemTable用于加速新数据的写入操作，而SSTable则是LSM树中持久化存储部分的核心，通过SSTable中的键值对列表，支持高效的查询和删除操作。"}}},"align":"","folded":false,"text_indent":1}},"OcAWd0YusoG46exMVKvcDs7tnph":{"id":"OcAWd0YusoG46exMVKvcDs7tnph","snapshot":{"type":"heading2","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+e"},"text":{"0":"LSM树的Compact策略"}}},"align":"","folded":false}},"A204dcKIUoG2iSxGKOUczyLBnQc":{"id":"A204dcKIUoG2iSxGKOUczyLBnQc","snapshot":{"type":"text","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":2,"numToAttrib":{"0":["author","6976464396953960476"],"1":["textHighlightBackground","rgba(183,237,177,0.8)"]}},"initialAttributedTexts":{"attribs":{"0":"*0+n*0*1+i*0+18"},"text":{"0":"在LSM树中，Compact是一种重要的策略，用于减少存储空间的浪费和提高查询性能。Compact操作主要通过合并多个SSTables以及删除已经过期或无效的数据来实现。"}}},"align":"","folded":false,"text_indent":1}},"KI2QdWwuWoGE0SxiGQOcwcWTnFh":{"id":"KI2QdWwuWoGE0SxiGQOcwcWTnFh","snapshot":{"type":"text","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+i"},"text":{"0":"常见的Compact策略有以下几种："}}},"align":"","folded":false}},"S0SqdgYSeoQa6kxG4Aqchxmtnad":{"id":"S0SqdgYSeoQa6kxG4Aqchxmtnad","snapshot":{"type":"ordered","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+3f"},"text":{"0":"Level 0 Compaction：Level 0 Compaction是指将相邻的Immutable MemTable和SSTable进行归并操作。这种方式能够在磁盘上创建更大的文件块，从而提高查询性能，但可能会导致数据重复和存储空间的浪费。"}}},"align":"","folded":false,"seq":"1"}},"PEC0damgco6m8ix2z0YcMwcunzJ":{"id":"PEC0damgco6m8ix2z0YcMwcunzJ","snapshot":{"type":"ordered","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+3d"},"text":{"0":"Level N Compaction：Level N Compaction是指将位于同一层级（Level）的多个SSTable进行归并操作。这种方式能够在不同的层级之间移动数据，从而进一步减少冗余数据和存储空间的浪费，同时也能够降低查询延迟。"}}},"align":"","folded":false,"seq":"auto"}},"LA6qd8SYio2I0QxCIvtcMAMznLc":{"id":"LA6qd8SYio2I0QxCIvtcMAMznLc","snapshot":{"type":"ordered","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+3n"},"text":{"0":"Size-Tiered Compaction：Size-Tiered Compaction是一种基于SSTable大小的Compaction策略，即按照SSTable大小分成不同的层级进行归并。这种策略可以有效地减少存储空间的浪费，但可能会导致数据读取性能下降。"}}},"align":"","folded":false,"seq":"auto"}},"T2iydKICuoGicaxKYsvcWRSLnjd":{"id":"T2iydKICuoGicaxKYsvcWRSLnjd","snapshot":{"type":"ordered","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+3y"},"text":{"0":"Time-Based Compaction：Time-Based Compaction是一种基于时间戳和数据过期时间的Compaction策略，即将已经过期或无效的数据从SSTable中删除。这种策略可以有效地减少不必要的磁盘I/O和存储空间使用，同时也能够确保数据的正确性和一致性。"}}},"align":"","folded":false,"seq":"auto"}},"E2EYdK804ocequx2rhRcFU0AnZc":{"id":"E2EYdK804ocequx2rhRcFU0AnZc","snapshot":{"type":"text","parent_id":"BjPHdX0VmoeVlnxIG4cckihSn9x","comments":[],"locked":false,"hidden":false,"author":"6976464396953960476","children":[],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+2n"},"text":{"0":"综上所述，LSM树的Compact策略可以根据具体应用场景和需求选择不同的方式进行优化。同时，在实际应用中，还需要考虑到吞吐量、查询延迟、存储空间等多个因素来选择最合适的Compact策略。"}}},"align":"","folded":false}},"BjPHdX0VmoeVlnxIG4cckihSn9x":{"id":"BjPHdX0VmoeVlnxIG4cckihSn9x","snapshot":{"type":"page","parent_id":"","comments":null,"locked":false,"hidden":false,"author":"6976464396953960476","children":["KWCkdCwsQoiyUmxGInBcVzz2n9d","O6ikdGCMcoOeqSxM93ocuAyenIc","H8AodEQwqouS2YxqE5ecyjZ5nKc","FOoId6QaWoooMSxGm4ycdsR2nxc","FK68dOC22oe2ocxe2gGcFAdqnSc","HYUqdeksuocakMx0YmGcXFdAnge","LK8kda4I0oiSu6xm4gBcilhvnDc","WMYkdSEMyogosmxAZJtca3FCn3b","ZqsSdQeK0oqqeExEd8HcBoDAnCc","KmgadKECEo8SUqxUrhEcpfX3nyb","EOcwdi6gYosgqixIBoKck7yknOb","BEQWdOEswo8OMixYhTdceiBOnIf","NGocdKesKoguOGx0kIbc7u9QnZb","VG2md006CoYSoKxGEfJcJ6i0n1d","N08Wdm4w8oSmwWxi2zDcOszInSe","OcAWd0YusoG46exMVKvcDs7tnph","A204dcKIUoG2iSxGKOUczyLBnQc","KI2QdWwuWoGE0SxiGQOcwcWTnFh","S0SqdgYSeoQa6kxG4Aqchxmtnad","PEC0damgco6m8ix2z0YcMwcunzJ","LA6qd8SYio2I0QxCIvtcMAMznLc","T2iydKICuoGicaxKYsvcWRSLnjd","E2EYdK804ocequx2rhRcFU0AnZc"],"text":{"apool":{"nextNum":1,"numToAttrib":{"0":["author","6976464396953960476"]}},"initialAttributedTexts":{"attribs":{"0":"*0+d"},"text":{"0":"【数据结构】深入浅出LSM"}}},"align":""}}},"payloadMap":{"O6ikdGCMcoOeqSxM93ocuAyenIc":{"level":1},"FOoId6QaWoooMSxGm4ycdsR2nxc":{"level":1},"LK8kda4I0oiSu6xm4gBcilhvnDc":{"level":1},"ZqsSdQeK0oqqeExEd8HcBoDAnCc":{"level":1},"EOcwdi6gYosgqixIBoKck7yknOb":{"level":1},"NGocdKesKoguOGx0kIbc7u9QnZb":{"level":1},"N08Wdm4w8oSmwWxi2zDcOszInSe":{"level":1},"A204dcKIUoG2iSxGKOUczyLBnQc":{"level":1},"KI2QdWwuWoGE0SxiGQOcwcWTnFh":{"level":1},"E2EYdK804ocequx2rhRcFU0AnZc":{"level":1}},"extra":{"mention_page_title":{},"external_mention_url":{}},"isKeepQuoteContainer":false,"selection":[{"id":2,"type":"block","recordId":"KWCkdCwsQoiyUmxGInBcVzz2n9d"},{"id":3,"type":"block","recordId":"O6ikdGCMcoOeqSxM93ocuAyenIc"},{"id":4,"type":"block","recordId":"H8AodEQwqouS2YxqE5ecyjZ5nKc"},{"id":5,"type":"block","recordId":"FOoId6QaWoooMSxGm4ycdsR2nxc"},{"id":6,"type":"block","recordId":"FK68dOC22oe2ocxe2gGcFAdqnSc"},{"id":7,"type":"block","recordId":"HYUqdeksuocakMx0YmGcXFdAnge"},{"id":8,"type":"block","recordId":"LK8kda4I0oiSu6xm4gBcilhvnDc"},{"id":9,"type":"block","recordId":"WMYkdSEMyogosmxAZJtca3FCn3b"},{"id":10,"type":"block","recordId":"ZqsSdQeK0oqqeExEd8HcBoDAnCc"},{"id":11,"type":"block","recordId":"KmgadKECEo8SUqxUrhEcpfX3nyb"},{"id":12,"type":"block","recordId":"EOcwdi6gYosgqixIBoKck7yknOb"},{"id":13,"type":"block","recordId":"BEQWdOEswo8OMixYhTdceiBOnIf"},{"id":14,"type":"block","recordId":"NGocdKesKoguOGx0kIbc7u9QnZb"},{"id":15,"type":"block","recordId":"VG2md006CoYSoKxGEfJcJ6i0n1d"},{"id":16,"type":"block","recordId":"N08Wdm4w8oSmwWxi2zDcOszInSe"},{"id":17,"type":"block","recordId":"OcAWd0YusoG46exMVKvcDs7tnph"},{"id":18,"type":"block","recordId":"A204dcKIUoG2iSxGKOUczyLBnQc"},{"id":19,"type":"block","recordId":"KI2QdWwuWoGE0SxiGQOcwcWTnFh"},{"id":20,"type":"block","recordId":"S0SqdgYSeoQa6kxG4Aqchxmtnad"},{"id":21,"type":"block","recordId":"PEC0damgco6m8ix2z0YcMwcunzJ"},{"id":22,"type":"block","recordId":"LA6qd8SYio2I0QxCIvtcMAMznLc"},{"id":23,"type":"block","recordId":"T2iydKICuoGicaxKYsvcWRSLnjd"},{"id":24,"type":"block","recordId":"E2EYdK804ocequx2rhRcFU0AnZc"}],"pasteFlag":"3f0a3fda-9072-410d-b906-8ae8315ea909"}" data-lark-record-format="docx/record" class="lark-record-clipboard">