LSM树

阅读数:103 评论数:0

跳转到新版页面

分类

算法/数据结构

正文

Log Structured Merge Tree,简单地说,LSM的设计目标是提供比传统的B+树更好的写性能。LSM通过将磁盘的随机写转化为顺序写来提高写性能,而付出的代价就是牺牲部分读性能、写放大(B+树同样有写放大的问题,即实际写入的的物理数据量是比写入数据量多)。

LSM相比B+树能提高性能的本质原因是:外存的随机读写都要慢于顺序读写。

优化写性能

如果我们对写性能特别敏感,最好Append Only:所有写操作都是将数据添加到文件末尾。这样做的写性能是最好的,大约等于磁盘的理论速度,但是Append Only的方式带来的问题是:

(1)读操作不方便

(2)很难支持范围操作

(3)需要垃圾回收(合并过期数据)

优化读性能

一般我们有两种方式:

(1)有序存储,比如B+树,SkipList

(2)Hash存储,不支持范围操作

读写性能的权衡

以LevelDB为例:

写操作主要由两步组成:

(1)写日志并持久化(Append Only)

(2)Apply到内存中的memtable(SkipList)

memtable写“满”后,会转换为immutable memtable,然后被后台线程compaction成按key有序存储的sst文件(顺序写)。由于sst文件会有多个,所以LevelDB的读操作可能会有多次贷危机磁盘IO。

SkipList

一个有序的链表,我们选取它的一半的节点来建索引,这样如果插入一个节点,我们比较的次数就减少了一半。这种做法,虽然增加了50%的空间,但是性能提高了一倍。

既然,我们已提取了一层节点索引,那么,可以在第一层索引上再提取索引。

LSM树原理

LSM树由两个或以上的存储结构组成,比如在论文中为了方便说明使用了最简单的两个存储结构。一个存储结构常驻内存中,称为C0 tree,具体可以是任何方便键值查找的数据结构,比如红黑树、map之类,甚至可以是跳表。另外一个存储结构常驻在硬盘中,称为C1 tree,具体结构类似B树,C1所有节点都是100%满的,节点的大小为磁盘块大小。

1、插入步骤

大体思路:插入一条新的纪录时,首先在日志文件中插入操作日志,以便后面恢复使用,日志是以append形式插入,将新纪录的索引插入到C0中,这里在内存中完成,不涉及磁盘IO操作,当C0大小达到某一阈值时或者每隔一段时间,将C0中记录滚动合并到磁盘C1中,对于多个存储结构的情况,当C1体量越来越大就向C2合并,以此类推,一直往上合并Ck。

2、查找操作

先找内存的C0树,找不到则找磁盘的C1树,然后是C2树,以此类推。

3、删除操作

主要是通过标记来实现,在内存中将要删除的记录标记一下,后面民步执行合并时将相应记录删除。

 




相关推荐

Trie,又称单词查找树或键树,是一种树形结构,是一种哈希树

单模式VS多模式 (1)单模式 单模就是给你一个单词,然后给你一个字符串,问你这个单词是否在这个字符串中出现过(匹配) (2)多模式 给你

定义:设G=(V,E)的顶点集为V={v1,v2,...}用a(i,j)表示G中顶点vi到vj的边数。称矩阵A(G)=(aij)为G的邻接矩阵。 (1)是一个对称矩阵 <p

1、已知前序、中序求后序 (1)确定根(前序中第一个结点为根),确定左子树,确定右子树(在中序中,找到前序所示根,其左为左子树,其右为右子树) (2)在左子树中递

1、B树 B 树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。与红黑树很相似,但在降低磁盘I/0操作方面要更好一些。 B树与红黑树最大的不同在于,B树的结点可以有许多子女

一、二叉树 Binary Search Tree 1、二叉树性质 (1)若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值。 (2)若它的右子树不空,则右子树上的所有结点的值均大于它的根结点