漯河住房和城乡建设局网站,php做的汽车销售网站,什么网站做h5好,万网网站备案多久LSM是一种基于日志追加写的数据结构#xff0c;非常适合为具有高写入数据提供索引访问
LSM基于以下前提
内存读写速度远高于磁盘#xff0c;但内存有限磁盘顺序读写速度远高于随机读写
结构
WAL
WAL(write-ahead log)是用于在系统错误时提供持久化#xff0c;在写入数据…LSM是一种基于日志追加写的数据结构非常适合为具有高写入数据提供索引访问
LSM基于以下前提
内存读写速度远高于磁盘但内存有限磁盘顺序读写速度远高于随机读写
结构
WAL
WAL(write-ahead log)是用于在系统错误时提供持久化在写入数据的时候会首先写入到WAL文件中
Memtable
LSM中在内存中的数据结构称之为memtable通常是红黑树结构。
SSTable
SSTable(sorted strings table)是在磁盘中有序字符串表。 过程
LSM是多层结构在内存中的是C0层保存了最近写入的数据。当C0层达到阈值后将合并C1层形成新的C1层如此循环往复下去
查询
查询是从C0查起逐层查
逐层查太慢了
可以采用稀疏索引来优化。 二分查找找到key的offset根据offset找到相应的value
此外还可以运用bloom filter过滤掉一定不在的key
写入
收到写请求会将该数据记录在WAL(write ahead log预写log)中用于故障恢复接着将该数据写入内存的memtable为维持有序性可以在内存中采用红黑树或者跳表当内存memtable超过一定阈值就会合并到SSTable 删除
每次删除时仅仅只是标记删除了实际删除过程由后台进程compaction负责。
compaction会持续合并新旧segment ref
https://en.wikipedia.org/wiki/Log-structured_merge-treehttps://medium.com/swlh/log-structured-merge-trees-9c8e2bea89e8https://www.cnblogs.com/zxporz/p/16021373.htmlhttps://yetanotherdevblog.com/lsm/
