跳跃表的分析与实现

----《大规模分布式存储系统:原理解析与架构实战》读书笔记

在了解了

Bitcask存储模型后,又开始研究LSM树存储引擎。LSM在实现的过程中使用了一个很有意思的数据结构:跳跃表。之前在《算法导论公开课》中听过这一节。当时感觉这种结构和二叉树简直是殊途同归,但是一直没有亲自动手实现过。这次又遇到了,就来实现试试看。话说跳跃表和各种平衡树一样,都是用来加速查询的。要随手实现一个B树不容易,但是实现一个跳跃表就简单很多。

跳跃表的简单介绍

跳跃列表一个有序链表,按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的"快速跑道",查找一个元素时,可以先通过高层的“快车道”,在快车道上找不到时,从最接近目标元素的快车道逐步进入慢车道,直到最后找的目标元素。

分析的时候,常用的形状如下:

各层是完全分开的列表。但是在实际实现中,则使用的为如下结构:

这种方式将多条联表的值合并到一起,同时使用指针来构造高层"快车道"。这种方式管理起来简单,节省空间。

更详细的介绍,请看跳表SkipList

跳跃表的复杂度分析以及概率因子p

来看看跳跃表的复杂度分析:

  • 空间复杂度: O(n) (期望)
  • 跳跃表高度: O(logn) (期望)

相关操作的时间复杂度:

  • 查找: O(logn) (期望)
  • 插入: O(logn) (期望)
  • 删除: O(logn) (期望)

跳跃表的操作时间负责度是基于概率的,所有加上了期望。

在层 i 中的元素按某个固定的概率 p 出现在层 i+1 中。当p=1/2或者1/e的时候查找的性能最好。

更详细的对比,请看到这篇文章:跳跃表,当中对不同概率的P对查询性能的影响做了对比。

跳跃表的高度

实际使用时,如果高度太高,会造成空间浪费,我们要做一个空间和时间的平衡。那么跳跃表的高度多少最合适?

假设跳跃表中的元素个数为N,当跳跃表的高度为log(N)时,跳跃表进化为一个二叉树结构,其查询次数与二分查找法一致。这无疑最理想的结果。

如果有一亿条记录,高度log(N)约等于30。redis中,最大高度也就是32,最多可以存几亿条记录。通常,我们用不了这么多记录。所以高度可以降低一点。

跳跃表的实现

跳跃表在levledb和redis中均有实现。二者都是用C实现的。我这个实现是C++版本的

主要特点为:

  • 支持模板
  • 0.2版本增加了对迭代器和反向迭代器的支持
  • 可自定义高度,默认为8,0.2版本版本改为了16

    因为高度为8的话适合几百条的记录,这时候,选用跳跃表并没有太多优势,不如之间使用排序数组。将默认值改为16的话,可以方便几万条记录大小的地方使用。

  • 概率p:暂时使用p=1/2
  • 做过单元测试,放心使用啦

初始版本简单直接,支持的函数为insert,find,remove。不支持范围操作。0.2版本增了对了迭代器的支持。

另外,在实现的时候也遇到一些问题,要注意模板编程与平时编程有所不同,平时编程通常实现和定义分离,分别放在.cpp和.h中。但是模板编程编写的通常是没有具现的实现,为了方便,一般定义和实现都会放在.h文件中。

初始版本简单直接,支持的函数为insert,find,remove。不再介绍。下面是0.2版本实现的函数及其功能:

void insert(const_value_type &value)

在当前表中插入value值。值可以重复。

void remove(const_value_type &value)

删除第一个值为value的元素。重复值需要多次删除

void clear()

清空跳跃表

iterator find(const_value_type &value)

返回第一个值为value的元素的迭代器,否则返回end.

iterator begin(int level = 0)

返回指向当前表中第level层的第一个元素的迭代器。使用begin的时候,可以指定遍历不同的层,默认为最底层。这个实际上并不是标准的迭代器,为了实现分层遍历进行了特化。

iterator end() const

返回指向当前表中最后一个元素的迭代器。

iterator rbegin() const

返回指向当前表中最后一个元素的反向迭代器。

iterator rend() const

返回指向表中第一个元素的反向迭代器。

unsigned long size()

返回当前表中元素的数目

unsigned int level()

返回当前表的总层数

unsigned int maxlevel()

返回当前表的能使用的最大层数

bool empty()

判断表是否为空

代码地址见上面的链接。



欢迎光临我的网站----蝴蝶忽然的博客园----人既无名的专栏

如果阅读本文过程中有任何问题,请联系作者,转载请注明出处!

跳跃表的分析与实现,布布扣,bubuko.com

时间: 07-16

跳跃表的分析与实现的相关文章

redis源码分析4---结构体---跳跃表

redis源码分析4---结构体---跳跃表 跳跃表是一种有序的数据结构,他通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的: 跳跃表支持平均O(logN),最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点.性能上和平衡树媲美,因为事先简单,常用来代替平衡树. 在redis中,只在两个地方使用了跳跃表,一个是实现有序集合键,另一个是在集群节点中用作内部数据结构. 1 跳跃表节点 1.1 层 层的数量越多,访问其他节点的速度越快: 1.2 前进指针 遍历举例

跳跃表,字典树(单词查找树,Trie树),后缀树,KMP算法,AC 自动机相关算法原理详细汇总

第一部分:跳跃表 本文将总结一种数据结构:跳跃表.前半部分跳跃表性质和操作的介绍直接摘自<让算法的效率跳起来--浅谈"跳跃表"的相关操作及其应用>上海市华东师范大学第二附属中学 魏冉.之后将附上跳跃表的源代码,以及本人对其的了解.难免有错误之处,希望指正,共同进步.谢谢. 跳跃表(Skip List)是1987年才诞生的一种崭新的数据结构,它在进行查找.插入.删除等操作时的期望时间复杂度均为O(logn),有着近乎替代平衡树的本领.而且最重要的一点,就是它的编程复杂度较同类

浅析SkipList跳跃表原理及代码实现

本文将总结一种数据结构:跳跃表.前半部分跳跃表性质和操作的介绍直接摘自<让算法的效率跳起来--浅谈“跳跃表”的相关操作及其应用>上海市华东师范大学第二附属中学 魏冉.之后将附上跳跃表的源代码,以及本人对其的了解.难免有错误之处,希望指正,共同进步.谢谢. 跳跃表(Skip List)是1987年才诞生的一种崭新的数据结构,它在进行查找.插入.删除等操作时的期望时间复杂度均为O(logn),有着近乎替代平衡树的本领.而且最重要的一点,就是它的编程复杂度较同类的AVL树,红黑树等要低得多,这使得其

跳跃表SkipList

SkipList在各种开源引擎中用处普遍,例如redis的sortedset容器.luence里面的索引字典等均用到了skiplist. 1.SkipList     在数据结构里面,我们知道有两种基本数据存储结构:数组和链表.它们均有其各自的特点,数组(特别是有序数组),可以进行快速查询,但不便于删除操作;链表,可以进行快速的增删操作,但是又不便于查询.那有没可能存在一种数据结构,结合两者各自的优点呢?     基于这样的思路,William Pugh这位马里兰大学的计算机教授,于1989年提

查找——图文翔解SkipList(跳跃表)

跳跃表 跳跃列表(也称跳表)是一种随机化数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(logn)平均时间). 基本上,跳跃列表是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表元素,因此得名.所有操作都以对数随机化的时间进行. 如下图所示,是一个即为简单的跳跃表.传统意义的单链表是一个线性结构,向有序的链表中插入一个节点需要O(n)的时间,查找操作需要O(n)的时间.如果我们使用图中所示的跳跃表,就可以大大减少减少

“跳跃表”简析

复杂度 空间复杂度: O(n) (期望) 跳跃表高度: O(logn)(期望) 查找:O(logn)(期望) 插入: O(logn)(期望) 删除:O(logn)(期望) 之所以在每一项后面都加一个“期望”,是因为跳跃表的复杂度分析是基于概率论的.有可能会产生最坏情况,不过这种概率极其微小. 顶层链表元素的确定方式 底层链表就是最初的链表,包含所有元素. we just like every node to be accessed sort of as quickly as possible,

第一部分 数据结构与对象 跳跃表

下面是跳跃表的基本原理,REDIS的实现大致相同 跳跃表的一个特点是,插入NODE是通过随机的方式来决定level的,比较奇特 下面是skipList的一个介绍,转载来的,源地址:http://kenby.iteye.com/blog/1187303,为防止源地址丢失,故拷贝一份放在这里,望作者原谅. ---------------转载开始----------------- 为什么选择跳表 目前经常使用的平衡数据结构有:B树,红黑树,AVL树,Splay Tree, Treep等. 想象一下,给

skip list跳跃表实现

跳表(skip List)是一种随机化的数据结构,基于并联的链表,实现简单,插入.删除.查找的复杂度均为O(logN).跳表的具体定义,跳表是由William Pugh发明的,这位确实是个大牛,搞出一些很不错的东西.简单说来跳表也是 链表的一种,只不过它在链表的基础上增加了跳跃功能,正是这个跳跃的功能,使得在查找元素时,跳表能够提供O(log n)的时间复杂 度.红黑树等这样的平衡数据结构查找的时间复杂度也是O(log n),并且相对于红黑树这样的平衡二叉树skiplist的优点是更好的支持并

skip跳跃表的实现

skiplist介绍跳表(skip List)是一种随机化的数据结构,基于并联的链表,实现简单,插入.删除.查找的复杂度均为O(logN).跳表的具体定义, 跳表是由William Pugh发明的,这位确实是个大牛,搞出一些很不错的东西.简单说来跳表也是 链表的一种,只不过它在链表的基础上增加了跳跃功能,正是这个跳跃的功能,使得在查找元素时,跳表能够提供O(log n)的时间复杂 度.红黑树等这样的平衡数据结构查找的时间复杂度也是O(log n),并且相对于红黑树这样的平衡二叉树skiplist