LSM Tree
2021-12-02 19:17:37 11 举报AI智能生成
LSM tree 数据结构
作者其他创作
大纲/内容
https://zhuanlan.zhihu.com/p/415799237
定义：
LSM树是一个横跨内存和磁盘的，包含多颗"子树"的一个森林
LSM树分为Level 0，Level 1，Level 2 ... Level n 多颗子树，其中只有Level 0在内存中，其余Level 1-n在磁盘中
内存中的Level 0子树一般采用排序树（红黑树/AVL树）、跳表或者TreeMap等这类有序的数据结构，方便后续顺序写磁盘
采用排序树（红黑树/AVL树）
跳表
TreeMap
一颗二叉排序树
有序性
该性质决定了LSM树优异的读写性能。
磁盘中的Level 1-n子树，本质是数据排好序后 顺序写到 磁盘上的 文件，只是叫做树而已
是文件
排好序数据
按数据key排好序后
顺序写在磁盘上的一个个文件（
有序性。
每一层的子树都有一个阈值大小，达到阈值后会进行合并，合并结果写入下一层
变化--》层变化规则
本层数据 冲顶
阈值
合并 M （LSM 中M）
进入下一层
层 0（（n>0））===》 阈值
内存中遍历排好序的Level 0树
顺序写入磁盘的Level 1
层 N （（n>0））===》 阈值 ==》归并排序 ===》写入 层 N + 1
只有内存中数据允许原地更新，磁盘上数据的变更只允许追加写，不做原地更新
追加
写入
Level 0
原地更新
n > 0 写入磁盘上的数据
采用Append形式的磁盘顺序写，
更新和删除操作并不去修改老数据，只是简单的追加新数据
总结：
“磁盘顺序写”
“多个树(状数据结构)”
冷热（新老）数据分级”
定期归并
非原地更新
几种特性统一在一起的思想
增删改
增加
新数据直接插入Level 0树的过程
该操作复杂度为树高log(n)
n是Level 0树的数据量，
写入
WAL（Write Ahead Log）日志
（通常用于故障恢复）
删除操作
待删除数据在内存中
墓碑标记数据在 节点上
待删除数据在磁盘中
墓碑标记数据在 节点子树上
待删除数据根本不存在
墓碑标记数据在 节点子树上
综合看待上述三种情况
三种情况
转化
向Level 0树中写入墓碑标记。该操作复杂度为树高log(n)，代价很低
删除实质
“墓碑标记”的特殊数据
标记删除
并不是直接删除数据
修改操作
数据在内存中
直接内存覆盖
待修改数据在磁盘中
新的蓝色的节点7插入内存中的Level 0树中
待修改数据根本不存在
新的蓝色的节点7插入内存中的Level 0树中
复杂度为树高log(n)
都是在内存中倒腾
没涉及到磁盘操作
速度飞快，写吞吐量高的离谱
查询
顺序查找Level 0、Level 1、Level 2 ... Level n 每一颗树
一旦匹配便返回目标数据，不再继续查询
该策略保证了查到的一定是目标key最新版本的数据（有点MVCC的感觉）。
LSM树的查询操作相对来说代价比较高
优化
布隆过滤器 + 建立稀疏索引
知识点：
稠密索引和稀疏索引
https://cloud.tencent.com/developer/article/1711134
合并操作
内存数据写入磁盘的场景
归并写入磁盘Level 1树
L0 中序遍历 与 L1 文件中
此时L1 中 多了一个块 Block
磁盘中多个块的归并：
如果 Ln 中 块 ==》阈值
则
归并写入
下一层 Ln+1
归并的过程是保留较新的数据，于是我们看到结果中，key=5和7的数据都是红色的（来自于较新的Block2）
原始数据都是有序
复杂度为O(n)
组织文件
SSTable
总结：
先内存再磁盘
内存原地更新
磁盘追加更新
归并保留新值
B/B+树的读写性能基本平衡
LSM树的设计原则通过舍弃部分读性能，换取了无与伦比的写性能
写吞吐量远远大于读吞吐量的场景
得到了NoSQL届的喜爱和好评。
精髓：
相比于B/B+树或者倒排索引
LSMTree采用了“疯狂到不顾一切”的干啥都磁盘顺序写的方案，
赋予了它无与伦比的写吞吐量。
属于nosql
应用
RocksDB
LevelDB
HBase
Prometheus
0 条评论
下一页
