`
susiya
  • 浏览: 90812 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

skiplist跳跃表原理

 
阅读更多

转载请注明:http://blog.csdn.net/ict2014/article/details/17394259

SkipList在leveldb以及lucence中都广为使用,是比较高效的数据结构。由于它的代码以及原理实现的简单性,更为人们所接受。我们首先看看SkipList的定义,为什么叫跳跃表?

“ Skip lists  are data structures  that use probabilistic  balancing rather  than  strictly  enforced balancing. As a result, the algorithms  for insertion  and deletion in skip lists  are much simpler and significantly  faster  than  equivalent  algorithms  for balanced trees. ”

译文:跳跃表使用概率均衡技术而不是使用强制性均衡,因此,对于插入和删除结点比传统上的平衡树算法更为简洁高效。 

我们看一个图就能明白,什么是跳跃表,如图1所示:


                                                                 图1:跳跃表简单示例

如上图所示,是一个即为简单的跳跃表。传统意义的单链表是一个线性结构,向有序的链表中插入一个节点需要O(n)的时间,查找操作需要O(n)的时间。如果我们使用图1所示的跳跃表,就可以减少查找所需时间为O(n/2),因为我们可以先通过每个节点的最上面的指针先进行查找,这样子就能跳过一半的节点。比如我们想查找19,首先和6比较,大于6之后,在和9进行比较,然后在和12进行比较......最后比较到21的时候,发现21大于19,说明查找的点在17和21之间,从这个过程中,我们可以看出,查找的时候跳过了3、7、12等点,因此查找的复杂度为O(n/2)。查找的过程如下图2:


                                                                  图2:跳跃表查找操作简单示例

其实,上面基本上就是跳跃表的思想,每一个结点不单单只包含指向下一个结点的指针,可能包含很多个指向后续结点的指针,这样就可以跳过一些不必要的结点,从而加快查找、删除等操作。对于一个链表内每一个结点包含多少个指向后续元素的指针,这个过程是通过一个随机函数生成器得到,这样子就构成了一个跳跃表。这就是为什么论文“Skip Lists : A Probabilistic Alternative to Balanced Trees ”中有“概率”的原因了,就是通过随机生成一个结点中指向后续结点的指针数目。随机生成的跳跃表可能如下图3所示:


                                                                 图3:随机生成的跳跃表

 

分享到:
评论

相关推荐

    跳跃表skiplist参考文档

    跳跃表(Skiplist)是一种在Redis中广泛使用的数据结构,它作为一种概率性的平衡树替代方案,通过概率性平衡而非严格平衡,实现了更简单、更快的插入和删除算法。本篇将深入探讨跳跃表的基本概念、工作原理以及其在...

    SkipList.pptx

    跳跃表(Skiplist)技术分享 跳跃表(Skiplist)是一种高效的数据结构,能够快速查询一个有序连续元素的数据链表。它的平均查找和插入时间复杂度都是 O(log n) ,优于普通队列的 O(n) 。下面是跳跃表的详细知识点:...

    C# 简单的跳跃表实现

    下面将详细介绍跳跃表的工作原理以及如何在C#中实现它。 跳跃表的核心思想是通过随机概率增加节点的层级,使得查找效率近似于对数时间复杂度。每层节点都包含一部分下层节点,这样在查找时,可以跳过部分节点,从而...

    skipList.rar

    本压缩包"skipList.rar"包含了一个用C++实现的跳跃表,该实现参考了Redis中的zskiplist。下面将详细介绍跳跃表的概念、工作原理以及C++实现的关键点。 跳跃表是一种随机化的数据结构,由多个层(level)组成,每层...

    Java实现跳跃表(skiplist)的简单实例

    "Java实现跳跃表(skiplist)的简单实例" 跳跃表(Skiplist)是一种随机化数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间),并且对并发算法友好。跳跃表的结构是:假如...

    SkipList_Java.rar_SkipList in Java_skiplist_skiplist java

    1. SkipList.html: 这可能是一个关于跳表的HTML文档,用于解释跳表的原理、操作和Java实现的细节。它可能会包含示例代码、伪代码或者交互式的可视化工具,帮助理解跳表的工作方式。 2. SkipList.java: 这是跳表的...

    chapter_10_映射、哈希表和跳跃表.zip

    最后,跳跃表(Skip List)是一种概率型数据结构,它通过构建多层索引来加速查找过程。每个元素在跳跃表中有多个节点,每个节点包含一个值和多个指向相邻节点的指针。较上层的节点跳过的步数更多,这样就可以快速从...

    跳跃表 C++实现

    本篇将详细介绍C++实现跳跃表的原理、步骤以及如何与红黑树进行对比测试。 跳跃表(Skip List)的基本思想是通过在原有有序链表上增加多级索引,使得查找过程可以跳跃性地前进,从而减少查找次数。每条数据记录都有...

    C# 实现 01背包问题,跳跃表方案

    2. 定义跳跃表类(SkipList),包含头部节点,插入和查找方法。插入方法会根据概率决定节点的层级,查找方法则通过逐层遍历找到目标物品。 3. 在01背包问题的解决过程中,可能会用到跳跃表的查找方法来快速找到当前...

    spiklist跳跃表

    **跳跃表(Skip List)详解** 跳跃表是一种高效的数据结构,用于快速查找序列中的元素,其设计灵感来源于随机化算法。在计算机科学中,跳跃表常被用来实现有序集合或映射,它允许我们以近似对数的时间复杂度进行...

    Redis内部数据结构详解(6)——skiplist1

    skiplist不是传统意义上的平衡树或哈希表,而是基于链表的结构,通过多级跳转实现快速访问。 1. 跳跃列表基础概念: 跳跃列表由一系列节点组成,每个节点包含一个值和多个向前的指针。这些指针按层次排列,底层的...

    Go-skiplist-Skiplist在Go中的实现

    Skiplist的核心思想是分层跳跃。它由多个层级组成,每一层都是一个有序的链表。底层(最下面一层)包含所有元素,而上层则包含部分元素,使得在上层可以直接跳过一些元素,达到快速定位的目的。这种设计使得查找时...

    skipList.zip

    综上所述,"skipList.zip"项目提供了一个跳表的C++实现,通过对跳表的原理、数据结构、查找算法、插入和删除操作的理解,开发者可以学习到如何在实际编程中应用这一高效的数据结构。同时,通过对源代码的分析,还...

    skiplist 跳表C++实现

    跳表(Skip List)是一种高效的查找数据结构,它利用了概率算法来提高查询效率,通常用于数据库和搜索引擎中。在C++中实现跳表,我们可以利用STL中的容器和算法库来简化工作,同时理解其背后的原理至关重要。 跳表...

    Skiplist-CPP-master.zip

    在这个名为"Skiplist-CPP-master"的项目中,开发者使用C++语言实现了一个基于跳表的轻量级键值存储系统。下面我们将深入探讨跳表的基本原理、C++实现的关键点以及在键值存储中的应用。 1. 跳表基本原理: - 跳表是...

    cpp-ASkipListImplementedByTemplate一个支持模板的跳表

    在"SkipList-master"这个压缩包中,可能包含了跳表实现的源代码文件,如头文件skip_list.h和实现文件skip_list.cpp。开发者可以通过阅读这些文件,理解跳表的内部实现细节,并根据需要对其进行修改和扩展。 总结来...

    Lucene 3.0 原理

    6. **搜索优化**:Lucene 3.0 在搜索性能上做了很多优化,如位图过滤(BitSet)用于快速排除不相关的文档,跳跃表(Skip List)加速跳过低得分文档,以及缓存机制来提高后续查询的速度。 7. **多线程支持**:为了...

    202302256428.rar

    跳跃链表,也称为Skip List,是一种概率型数据结构,它的核心思想是通过分层结构来加速查找过程。与传统的链表相比,跳跃链表中的元素不仅按照顺序连接,还通过多级指针形成了多条“跳跃路径”,使得在平均情况下...

    redis设计与实现原理及运作机制

    ##### 1.4 跳跃表 (Skip List) **跳跃表的实现** 跳跃表是一种随机化的数据结构,它可以用于实现有序集合。Redis中的跳跃表每个节点都包含一个或多个级别的指针,这些指针指向集合中更大的元素。通过这种方式,...

    Redis设计与实现笔记1

    4. **跳跃表 (Skip List)** 跳跃表是一种高效的近似有序数据结构,其查询性能接近于平衡树,但实现更简单。Redis 使用跳跃表来实现有序集合和部分主键空间的范围查询。跳跃表由多个层级的链表组成,每层链表上的...

Global site tag (gtag.js) - Google Analytics