详解数据库存储的数据结构LSM Tree
LSM-Tree全称是Log Structured Merge Tree，是一种分层，有序，面向磁盘的数据结构。
LSM Tree的定义
1.LSM树是一个横跨内存和磁盘的，包含多颗"子树"的一个森林。
2.LSM树分为Level 0，Level 1，Level 2 ... Level n 多颗子树，其中只有Level 0在内存中，其余Level 1-n在磁盘中。
3.内存中的Level 0子树一般采用排序树（红黑树/AVL树）、跳表或者TreeMap等这类有序的数据结构，方便后续顺序写磁盘。
4.磁盘中的Level 1-n子树，本质是数据排好序后顺序写到磁盘上的文件，只是叫做树而已。
5.每一层的子树都有一个阈值大小，达到阈值后会进行合并，合并结果写入下一层。
6.只有内存中数据允许原地更新，磁盘上数据的变更只允许追加写，不做原地更新。
图1中分成了左侧绿色的内存部分和右侧蓝色的磁盘部分（定义1）。
图1左侧绿色的内存部分只包含Level 0树，右侧蓝色的磁盘部分则包含Level 1-n等多棵"树"（定义2）
图1左侧绿色的内存部分中Level 0是一颗二叉排序树（定义3）。注意这里的有序性，该性质决定了LSM树优异的读写性能。
图1右侧蓝色的磁盘部分所包含的Level 1到Level n多颗树，虽然叫做“树”，但本质是按数据key排好序后，顺序写在磁盘上的一个个文件（定义4） ，注意这里再次出现了有序性。
内存中的Level 0树在达到阈值后，会在内存中遍历排好序的Level 0树并顺序写入磁盘的Level 1。同样的，在磁盘中的Level n（n>0）达到阈值时，则会将Level n层的多个文件进行归并，写入Level n+1层。（定义5）
除了内存中的Level 0层做原地更新外，对已写入磁盘上的数据，都采用Append形式的磁盘顺序写，即更新和删除操作并不去修改老数据，只是简单的追加新数据。图1中右侧蓝色的磁盘部分，Level 1和Level 2均包含key为2的数据，同时图1左侧绿色内存中的Level 0树也包含key为2的数据节点。（定义6）
LSM树结构如下图所示：
数据库在执行写操作时，先同时写memtable与预写日志WAL。memtable写满后会自动转换成不可变的（immutable）memtable，并flush到磁盘，形成L0级sstable文件。sstable即有序字符串表（sorted string table），其内部存储的数据是按key来排序的，后文将其简称为SST。
执行读操作时，会首先读取内存中的数据（根据局部性原理，刚写入的数据很有可能被马上读取），即active memtable→immutable memtable→block cache。如果内存无法命中，就会遍历L0层sstable来查找。如果仍未命中，就通过二分查找法在L1层及以上的sstable来定位对应的key。
随着sstable的不断写入，系统打开的文件就会越来越多，并且对于同一个key积累的数据改变（更新、删除）操作也就越多。由于sstable是不可变的，为了减少文件数并及时清理无效数据，就要进行compaction操作，将多个key区间有重合的sstable进行合并。
LSM树的插入较简单，数据无脑往内存中的Level 0排序树丢即可，并不关心该数据是否已经在内存或磁盘中存在。该操作复杂度为树高log(n)，n是Level 0树的数据量，可见代价很低，能实现极高的写吞吐量。
LSM树的删除操作并不是直接删除数据，而是通过一种叫“墓碑标记”的特殊数据来标识数据的删除。
删除操作分为：待删除数据在内存中、待删除数据在磁盘中和该数据根本不存在三种情况。
1、待删除数据在内存中
待删除数据在内存中的删除过程。我们不能简单地将Level 0树中的节点删除，而是应该采用墓碑标记将其覆盖。
2、待删除数据在磁盘中
待删除数据在磁盘上时的删除过程。我们并不去修改磁盘上的数据（理都不理它），而是直接向内存中的Level 0树中插入墓碑标记即可。
3、待删除数据根本不存在
这种情况等价于在内存的Level 0树中新增一条墓碑标记，场景转换为情况3.2的内存中插入墓碑标记操作。
不论数据有没有、在哪里，删除操作都是等价于向Level 0树中写入墓碑标记。该操作复杂度为树高log(n)，代价很低。
修改操作
修改操作都是对内存中Level 0进行覆盖/新增操作。该操作复杂度为树高log(n)，代价很低。
LSM树的增加、删除、修改（这三个都属于写操作）都是在内存执行，完全没涉及到磁盘操作，所以速度快，写吞吐量高。
LSM树将增、删、改这三种操作都转化为内存insert + 磁盘顺序写(当Level 0满的时候)，通过这种方式得到了无与伦比的写吞吐量。
LSM树的查询能力则相对被弱化，相比于B+树的最多3~4次磁盘IO，LSM树则要从Level 0一路查询Level n，极端情况下等于做了全表扫描。（即便做了稀疏索引，也是lg(N0)+lg(N1)+...+lg(Nn)的复杂度，大于B+树的lg(N0+N1+...+Nn)的时间复杂度）。
同时，LSM树只append追加不原地修改的特性引入了归并操作，归并操作涉及到大量的磁盘IO，比较消耗性能，需要合理设置触发该操作的参数。
综上我们可以给出LSM树的优缺点：
优：增、删、改操作飞快，写吞吐量极大。
缺：读操作性能相对被弱化；不擅长区间范围的读操作；归并操作较耗费资源。
LSM Tree的增、删、改、查四种基本操作的时间复杂度分析如下所示：
以上是对LSM树基本操作以及优缺点的分析，我们可以据此得出LSM树的设计原则：
先内存再磁盘
内存原地更新
磁盘追加更新
归并保留新值
如果说B/B+树的读写性能基本平衡的话，LSM树的设计原则通过舍弃部分读性能，换取了写性能。该数据结构适合用于写吞吐量远远大于读吞吐量的场景。
党的二十大报告指出，教育、科技、人才是全面建设社会主义现代化国家的基础性、战略性支撑。必须坚持科技是第一生产力、人才是第一资源、创新是第一动力。加快建设网络强国和数字中国。贵州易鲸捷信息技术有限公司连日来深入学习党的二十大精神，将其贯彻至具体生产工作中，凝心聚力攻克科技技术难关，为我党实现第二个百年奋斗目标奋勇前进。
END
▼
往期精彩回顾
▼
王燮元：基于易鲸捷分布式2.0数据库的银行核心交易系统落地实践
易鲸捷简介
易鲸捷公司成立于2015年，专注于新一代融合型分布式数据库核心技术研发。公司核心团队源自天腾公司，曾创造过NonStopSQL等全球领先的数据库产品，核心技术完全自主可控。经过多年技术沉淀，易鲸捷已形成自主可控、国产可信、安全高效的三条完整分布式数据库产品线：QianBase xTP/QianBase TP/QianBase MPP，可面向不同行业应用提供完整的一站式解决方案，在金融、运营商、智能制造、5G等重点行业获得广泛应用。
网址：www.esgyn.cn
贵州易鲸捷信息技术有限公司 地址：贵阳市高新区长岭南路160号高科1号C座24楼 | |
北京易鲸捷信息技术有限公司 地址：北京市朝阳区大屯街道北苑路万科时代中心奥林A座10层 | |
上海易鲸捷信息技术有限公司 地址：上海市浦东新区金科路2889弄1号长泰广场A座6层03单元 | |
北京：010-84983409 | 上海：021-50822117 |
邮箱：info@esgyn.cn | 网址：www.esgyn.cn |