转http://bofang.iteye.com/blog/1676698
论文 The Log-Structure Merge-Tree(LSM-tree)(http://www.google.com.my/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&cad=rja&ved=0CDoQFjAD&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.44.2782%26rep%3Drep1%26type%3Dpdf&ei=6OlPUJuZFsaYiAfIkIHIDg&usg=AFQjCNGGoN9IFTLShcv2HbL0RVQdElfxow&sig2=8wysS63qlqRvWf5m3lk7bg) 描述了这种数据结构的目标和算法细节。
LSM-tree主要目标是快速地建立索引。B-tree是建立索引的通用技术,但是,在大并发插入数据的情况下,B-tree需要大量的磁盘随机 IO,很显然,大量的磁盘随机IO会严重影响索引建立的速度。特别地,对于那些索引数据大的情况(例如,两个列的联合索引),插入速度是对性能影响的重要 指标,而读取相对来说就比较少。LSM-tree通过磁盘的顺序写,来达到最优的写性能,因为这会大大降低磁盘的寻道次数,一次磁盘IO可以写入多个索引 块。
LSM-tree的主要思想是划分不同等级的树。以两级树为例,可以想象一份索引数据由两个树组成,一棵树存在于内存,一棵树存在于磁盘。内存中的 树可以不一定是B-树,可以是其他的树,例如AVL树。因为数据大小是不同的,没必要牺牲CPU来达到最小的树高度。而存在于磁盘的树是一棵B-树。
数据首先会插入到内存中的树。当内存中的树中的数据超过一定阈值时,会进行合并操作。合并操作会从左至右遍历内存中的树的叶子节点与磁盘中的树的叶 子节点进行合并,当被合并的数据量达到磁盘的存储页的大小时,会将合并后的数据持久化到磁盘,同时更新父亲节点对叶子节点的指针。
之前存在于磁盘的叶子节点被合并后,旧的数据并不会被删除,这些数据会拷贝一份和内存中的数据一起顺序写到磁盘。这会操作一些空间的浪费,但是,LSM-tree提供了一些机制来回收这些空间。
磁盘中的树的非叶子节点数据也被缓存在内存中。
数据查找会首先查找内存中树,如果没有查到结果,会转而查找磁盘中的树。
有一个很显然的问题是,如果数据量过于庞大,磁盘中的树相应地也会很大,导致的后果是合并的速度会变慢。一个解决方法是建立各个层次的树,低层次的 树都比上一层次的树数据集大。假设内存中的树为c0, 磁盘中的树按照层次一次为c1, c2, c3, ... ck-1, ck。合并的顺序是(c0, c1), (c1, c2)...(ck-1, ck)。
为什么LSM-tree的插入很快
1. 首先,插入操作首先会作用于内存,并且,内存中的树不会很大,这会很快。
2. 合并操作会顺序写入一个或多个磁盘页,这比随机写快得多。
相关推荐
airmate艾美特马桶消毒器 LSM01-01, LSM01-02 – 20200323 说明书.pdf
JLink-LSm1-Update-1.07-120816-1.zip v8 好用
LSM-trie: An LSM-tree-based Ultra-Large Key-Value Store for Small DataXingbo Wu1, Yuehai Xu1, Zili Shao2, and Song Jiang11 Wayne State University, {wuxb,yhxu,sjiang}@wayne.edu 2 The Hong Kong ...
C&D西恩迪 LSM2-T/6-D12-C 模块电源说明书pdf,C&D西恩迪 LSM2-T/6-D12-C 模块电源说明书
驱动LSM6DS3TR-C实现高效运动检测与数据采集(5)----上报匿名上位机实现可视化 CSDN文字教程:https://blog.csdn.net/qq_24312945/article/details/131250387 B站教学视频:...
驱动LSM6DS3TR-C实现高效运动检测与数据采集(4)----上报匿名上位机实现可视化 CSDN文字教程:https://blog.csdn.net/qq_24312945/article/details/131082161 B站教学视频:...
使用说明 LD-K-.AK./LSH(LSM)-...-.S[手册]pdf,
重力加速度传感器lsm303的驱动源代码
LSM-trie: An LSM-tree-based Ultra-LargeKey-Value Store for Small DataXingbo WuYuehai XuSong JiangZili ShaoThe Hong KongPolytechnic UniversityThe Challenge on Today’s Key-Value Store• Trends on ...
LSM-Tree关键技术[收集].pdf
python库。 资源全名:lsm-0.2.1-cp37-cp37m-macosx_10_14_x86_64.whl
python库,解压后可用。 资源全名:lsm-0.1.4-cp36-cp36m-win_amd64.whl
LSM使用了一个算法来延迟批处理索引变更,然后类似归并排序的方式串联起一个基于内存的组件和若干基于磁盘的组件上面的所有变更信息。该算法相比于传统的B树访问方式大大减少磁盘臂的移动开销。
资源来自pypi官网。 资源全名:lsm-0.1.1-cp37-cp37m-win_amd64.whl
资源来自pypi官网。 资源全名:lsm-0.1.4-cp36-cp36m-win_amd64.whl
资源来自pypi官网。 资源全名:lsm-db-0.6.1.tar.gz
摘要:伴随着数据量的大规模爆发和云计算的快速发展,早期由于缺乏标准化和其他问题而发展缓慢的键值存储(keyvaluestorage,KVStorage)进入了飞
资源分类:Python库 所属语言:Python 资源全名:lsm-0.3.8-cp37-cp37m-win_amd64.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059