我旁边的同时一直在捣鼓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 也是很有帮助的。 



对Python及运维开发感兴趣的朋友可以加QQ群 : 478476595 !!!
{ 2000人qq大群内有各厂大牛,常组织线上分享及沙龙,对高性能及分布式场景感兴趣同学欢迎加入该QQ群 }

另外如果大家觉得文章对你有些作用!   帮忙点击广告. 一来能刺激我写博客的欲望,二来好维护云主机的费用.
如果想赏钱,可以用微信扫描下面的二维码. 另外再次标注博客原地址  xiaorui.cc  ……   感谢!

redis多线程服务端设计的一些思考

    最近有看redis server的源码,想实现一个多线程的版本。在大多数场景下单个redis实例是满足需求的,但如果ops的量级过十几万,连接数超过几k...

阅读全文

redis modules扩展模块的开发使用

上下文:       Redis 4.0 的RC终于出来了, 看了redis官方及antirez的博客都有提到4.0的各种新功能,对我来说是相当有吸引力的 。&n...

阅读全文

技术分享 《大话redis设计实现》

        这次又给朋友公司 (Naver) 做了一次技术分享,主题是《大话redis设计实现》 ,  里面的内容来自 学习《redis设计与实现》...

阅读全文

2则回应给“折腾redis的sorted set数据结构Skip List跳跃表”

  1. 王超说道:

    这个不错!

  2. udc-7301970说道:

    学习了

发表评论