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