文档章节

Redis Skip List(跳跃表)

casoc
 casoc
发布于 2017/08/18 15:48
字数 528
阅读 108
收藏 0

跳跃表

跳跃表(Skip List)是一种用于有序元素序列快速搜索的数据结构。它的效率和红黑树以及AVL(自平衡二叉查找树)相近,但是实现起来更加容易(相对于复杂的自平衡算法)。

 

大概结构如下:

在最原始的已排序的链表基础上通过添加多个层级,理想情况下每个层级节点数是上一个层级1/2,查找时通过最上层开始,利用需要查找的值与当前层级值对比缩小范围并通过下一层进一步缩小范围,最终找到查询值的方式(类似于二分查找方式)。

 

Redis的跳跃表

Redis使用跳跃表作为有序集合的底层实现之一,如果一个有序集合包含的元素比较多或者集合中的元素时比较长的字符串时,Redis会使用跳跃表作为有序集合键的底层实现。

Redis跳跃表大致结构如下:

分为zskiplistNode和zskiplist两个结构,代码如下:

redis.h/zskiplistNode:

typedef struct zskiplistNode {

  // 成员对象
  robj *obj;

  // 分值
  double score;

  // 后退指针
  struct zskiplistNode *backward;

  // 层
  struct zskiplistLevel {

    // 前进指针
    struct zskiplistNode *forward;

    // 跨度
    unsigned int span;

  } level[];

} zskiplistNode;

level数组包含了当前元素在不用层高的下一个元素指针和跨度,Redis中程序会根据幂次定律(power law, 越大的数出现的概率越小)随机生成一个介于1~32之间的值作为level数组的大小,这个大小就是层的“高度”。

span表示跨度,由于底层的链表是有序的,所以从头部到当前节点跨度之和也就是元素的排位。用于Redis有序集合的ZRANK命令获取元素排行。

backward回退指针用于逆序遍历链表,对应Redis有序集合的ZREVRANGE命令。

 

redis.h/zskiplist:

typedef struct zskiplist {

  // 表头节点和表尾节点
  struct zskiplistNode *header, *tail;

  // 表中节点的数量
  unsigned long length;

  // 表中层数最大的节点的层数
  int level;

} zskiplist;

 

© 著作权归作者所有

上一篇: Redis 整数集合
下一篇: Redis 字典
casoc
粉丝 48
博文 85
码字总数 60735
作品 0
成都
程序员
私信 提问
【Redis源码剖析】 - Redis数据类型之有序集合zset

原创作品,转载请标明:http://blog.csdn.net/Xiejingfa/article/details/51231967 Redis源码剖析系列文章汇总:传送门 这周事情比较多,原本计划每周写两篇文章的任务看来是完不成了。今天为...

xiejingfa
2016/04/24
0
0
Redis 内存存储结构分析

1 Redis 内存存储结构 本文是基于 Redis-v2.2.4 版本进行分析. 1.1 Redis 内存存储总体结构 Redis 是支持多key-value数据库(表)的,并用 RedisDb 来表示一个key-value数据库(表). redisServe...

红薯
2011/07/08
1K
1
SkipList的那点事儿

Skip List的工作原理 Skip List(跳跃表)是一种支持快速查找的数据结构,插入、查找和删除操作都仅仅只需要对数级别的时间复杂度,它的效率甚至可以与红黑树等二叉平衡树相提并论,而且实现...

SylvanasSun
2017/12/31
0
0
Redis不同数据类型的的数据结构实现

原文:Redis不同数据类型的的数据结构实现 我们知道Redis支持五种数据类型, 分别是字符串、哈希表(map)、列表(list)、集合(set)和有序集合,和Java的集合框架类似,不同数据类型的数据...

杰克.陈
2017/12/19
0
0
游戏排行榜算法设计实现比较

  以前在音乐做过一些实时投票,积分排名;单曲、专辑等排行榜;游戏中也有类似的战斗力排行;SNS的游戏又有好友排行等,对于此类的排行算法在此做个总结。   需求背景:   查看前top...

shezjl
2015/10/04
680
1

没有更多内容

加载失败,请刷新页面

加载更多

java通过ServerSocket与Socket实现通信

首先说一下ServerSocket与Socket. 1.ServerSocket ServerSocket是用来监听客户端Socket连接的类,如果没有连接会一直处于等待状态. ServetSocket有三个构造方法: (1) ServerSocket(int port);...

Blueeeeeee
今天
6
0
用 Sphinx 搭建博客时,如何自定义插件?

之前有不少同学看过我的个人博客(http://python-online.cn),也根据我写的教程完成了自己个人站点的搭建。 点此:使用 Python 30分钟 教你快速搭建一个博客 为防有的同学不清楚 Sphinx ,这...

王炳明
昨天
5
0
黑客之道-40本书籍助你快速入门黑客技术免费下载

场景 黑客是一个中文词语,皆源自英文hacker,随着灰鸽子的出现,灰鸽子成为了很多假借黑客名义控制他人电脑的黑客技术,于是出现了“骇客”与"黑客"分家。2012年电影频道节目中心出品的电影...

badaoliumang
昨天
15
0
很遗憾,没有一篇文章能讲清楚线程的生命周期!

(手机横屏看源码更方便) 注:java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期,但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

彤哥读源码
昨天
15
0
jquery--DOM操作基础

本文转载于:专业的前端网站➭jquery--DOM操作基础 元素的访问 元素属性操作 获取:attr(name);$("#my").attr("src"); 设置:attr(name,value);$("#myImg").attr("src","images/1.jpg"); ......

前端老手
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部