折腾redis的sorted set数据结构Skip List跳跃表

我旁边的同时一直在捣鼓redis的分页功能,详细的分析了list和sorted set的两个结构.   我自己也对sorted set的数据结构很是感兴趣…  我这边的有个微信抓取的任务就是用python rq做的,里面的选用的redis数据类型就是sorted set…   这里不是重点,有时间专门写一篇关于redis实现时序任务队列的方式。


xiaorui.cc

xiaorui.cc

xiaorui.cc

开始先是介绍skip list :


Skip List是一种随机化的数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)。基本上,跳跃列表是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。Skip List可以很好解决有序链表查找特定值的困难。

Skip List定义
一个skip list 跳表,应该具有以下特征:
  一个跳表应该有几个层(level)组成;
  跳表的第一层包含所有的元素;
  每一层都是一个有序的链表;
  如果元素x出现在第i层,则所有比i小的层都包含x;
  第i层的元素通过一个down指针指向下一层拥有相同值的元素;
  在每一层中,-1和1两个元素都出现(分别表示INT_MIN和INT_MAX);
  Top指针指向最高层的第一个元素。

大家看下面的图片,一共构造了三层,根据上面的一些个特性,估计你也能理解一二了。   举个例子,你如果想查找14,那么先从第三层开始搞起,因为是有序的,所以14可以确定是在第二层的7和21之间,然后呢,再到第三层就能找到了。 他的一些算法是含有一些随机性的。 


那么我们再来查找117和118 

例子:查找元素 117
(1) 比较 21, 比 21 大,往后面找
(2) 比较 37,   比 37大,比链表最大值小,从 37 的下面一层开始找
(3) 比较 71,  比 71 大,比链表最大值小,从 71 的下面一层开始找
(4) 比较 85, 比 85 大,从后面找
(5) 比较 117, 等于 117, 找到了节点。

下面是我在wiki找到的一个流程动画,方便大家理解

跳表的插入方式

有人也用python实现了skip list的功能,有兴趣的朋友可以看看。   代码还算干练,对于理解skip list 也是很有帮助的。 


对Golang感兴趣的朋友可以加群: 278517979 !!!
另外如果大家觉得文章对你有些作用! 如果想赏钱,可以用微信扫描下面的二维码, 感谢!
另外再次标注博客原地址  xiaorui.cc

2 Responses

  1. 王超 2015年4月28日 / 上午8:14

    这个不错!

  2. udc-7301970 2015年3月28日 / 上午7:40

    学习了

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">