`
nil-zhang
  • 浏览: 51617 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Redis skip list结构分析

阅读更多

如何实现一个海量用户的实时排名系统?或许可以用mysql搞一个纠结的方案;但要是选择了redis,那绝对是既简单又优雅。Redis的zset本身就是一种支持排序的集合,而zset的实现,则使用了skip list数据结构。Skip list是一种多层次的有序链表,通过随机地选择层数来实现插入、查找和删除都是O(logn)的时间复杂度(和平衡树同样的效率,但实现比平衡树简单很多)。关于skip list的具体介绍可以参见William Pugh的论文:Skip Lists: A Probabilistic Alternative to Balanced Trees 。下面我们来分析一下redis中skip list的实现。
Redis中skip list主要有zskiplist和zskiplistNode两个数据结构:

typedef struct zskiplistNode {

    robj *obj;

    double score;

    struct zskiplistNode *backward;

    struct zskiplistLevel {

        struct zskiplistNode *forward;

        unsigned int span;

    } level[];

} zskiplistNode;

 

typedef struct zskiplist {

    struct zskiplistNode *header, *tail;

    unsigned long length;

    int level;

} zskiplist;

其中zskiplistNode中包含一个zskiplistLevel数组,数组的大小根据节点所在的层数(level)决定。backward指针是为了方便向后遍历而对skip list做的改进。

主要的API有:

zslCreate            创建一个zskiplist,并添加一个具有最高层数ZSKIPLIST_MAXLEVEL(代码中定义为32)的节点来管理分层的链表。

zslInsert              插入一个节点到zskiplist,并调整每一个层级的链表都是有序的。

zslDelete            从zskiplist删除一个节点,并调整剩余节点在每个层级都是有序的。

zslRandomLevel 为新加入的节点随机产生一个不超过ZSKIPLIST_MAXLEVEL的层数。

zslInsert和zslDelete函数都需要首先查找到合适的位置或节点,查找的代码很简单,直接包含在了这两个函数内:

x = zsl->header;

for (i = zsl->level-1; i >= 0; i--) {

/* store rank that is crossed to reach the insert position */

    rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];

    while (x->level[i].forward &&

          (x->level[i].forward->score < score ||

             (x->level[i].forward->score == score &&

          compareStringObjects(x->level[i].forward->obj,obj) < 0))) {

       rank[i] += x->level[i].span;

       x = x->level[i].forward;

   }

   update[i] = x;

}

查找是从zskiplist现有的最高层开始向前,并在查找的过程中根据规则转向低层的链表继续,一直到skip list的最低层为止。同时看到redis的实现中允许相同的score存在(这时按对象的字符串进行比较),但不允许具有相同值的对象并存(集合的特性)。

下面通过一个例子来说明skip list的建立过程。

按顺序执行下列语句:

zslInsert(zsl, 5, obj1);              //level=1;

zslInsert(zsl, 3, obj2);              //level=2;

zslInsert(zsl, 4, obj3);              //level=1;

zslInsert(zsl, 1, obj4);              //level=3;

zslInsert(zsl, 2, obj5);              //level=1;

现在的zsl结构如下图所示,其中level array的数组下标是为了图例更直观,实际不占存储空间。为了保证图例的简洁,backward的指针没有画出,对应level 0红色指针相反方向的指针。

祝大家玩儿的开心!(学霸哥^_^)。

分享到:
评论

相关推荐

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

    Redis中的跳跃列表(skiplist)是一种高效的数据结构,用于实现有序集合(sorted set)。它是一种概率性数据结构,通过随机概率控制层数,从而在平均情况下提供接近于对数时间复杂度的查找、插入和删除操作。skiplist...

    为啥 redis 使用跳表(skiplist)而不是使用 red-black?1

    在Redis中,跳表(Skip List)被用于实现有序集合(ZSET,Sorted Set),而不是使用红黑树。以下是对这一决策背后原因的详细分析: 1. **内存效率**: - 跳表在内存占用方面相对较低,可以通过调整节点层级的概率...

    Redis ziplist内部结构分析

    Redis中的ziplist是一种使用连续...需要注意的是,随着数据量的增加,ziplist的性能可能会下降,因为频繁地修改会导致内存重分配操作,对于大量数据的存储,Redis提供了更高效的跳表(skiplist)和哈希表等数据结构。

    Redis学习笔记

    "深入redis学习(九)--redis skiplist.doc"讲解了跳跃表,这是Redis实现有序集合排序的底层数据结构,提供O(log N)的查找、插入和删除效率,比红黑树更节省内存。 "深入redis学习(十)--redis object management....

    redis源码日志

    - **第9章:redis数据结构skiplist** - **概述**: 跳表的基本概念。 - **实现**: 描述跳表的插入、删除等操作细节。 - **场景**: Redis中跳表的应用实例。 - **第10章:redis数据结构intset** - **结构**: int...

    Redis实践与总结

    - **Skiplist**:对于更大规模的数据,Redis采用Skiplist(跳跃表)进行编码,这是一种随机化数据结构,通过在每个节点中维护多个指向其他节点的指针,达到快速访问节点的目的。跳跃表的平均时间复杂度为O(log N),...

    redis-4.0.14源码压缩包

    - **有序集合(Sorted Sets)**:结合集合和排序功能,使用ziplist或skiplist实现。 2. **命令处理**: Redis通过命令处理器接收客户端发送的命令,解析并执行。每个命令都有一个对应的处理函数,如`lpush`、`get...

    Redis面试常考知识点

    **Redis**(Remote Dictionary Server)是一种开源的、基于内存的、支持多种数据结构的键值(Key-Value)存储系统。由于它主要依赖内存进行数据存储,因此读写速度极快,能够达到微秒级别的响应时间,远超传统的关系...

    Algorithm-skiplist.zip

    在压缩包`skiplist-master`中,可能包含了实现跳表算法的源代码。通过对源代码的分析和学习,我们可以更深入地理解跳表的内部机制,包括节点的创建、连接、查找、插入和删除等操作。这有助于我们更好地运用跳表解决...

    week2_3_朱道冰_cpp_SkipLIst1

    class SkipList { private: Comparator const compare_; std::unique_ptr&lt;Node&gt; head_; Random rnd_; std::map, int&gt; heights; public: // 构造函数和析构函数 SkipList(); ~SkipList(); // 插入元素 ...

    redis3.0源码有注解

    例如,`dict`数据结构用于实现哈希表,`quicklist`优化了列表的性能,而`skiplist`则用于实现有序集合的快速查找。 2. 网络I/O:Redis使用事件驱动的网络库`ae`处理客户端连接和数据传输。`ae`通过非阻塞I/O和多路...

    Redis_Source_code:Redis源码分析-redis source code

    -有序集合:元素有序且不重复,使用跳跃表(Skip List)实现,支持范围查询。 2. Redis的核心组件: - Redis服务器:处理客户端连接,解析命令,执行操作并返回结果。 - RDB持久化:定期将内存中的数据快照到...

    一文带你搞定Redis.docx

    3. **高效的数据结构**:Redis 内部使用优化的数据结构,如跳跃表(Skip List)和简单动态字符串(SDS),以提高查询效率。 4. **丰富的数据类型**:Redis 提供了String、Hash、Set、List、Sorted Set等多种数据类型...

    Redis中文手册

    - **SKIPLIST编码的有序集**:对于较大的有序集或分数范围较广的情况,Redis会选择SKIPLIST编码,以提供更快的查找速度。 #### 四、功能实现详析 ##### 4.1 事务 - **事务**:Redis支持简单的事务机制,允许多个...

    Redis源码程序

    1. 数据结构实现:Redis的核心在于其高效的数据结构,如SDS(Simple Dynamic String)用于实现字符串,ZipList用于紧凑存储列表和哈希表,SkipList用于有序集合的排序等。通过源码,我们可以看到这些数据结构如何...

    【Redis】——常用五大数据类型之Zset,算法数据结构

    在内部,有序集合Zset由两个主要的数据结构支撑:哈希(Hash)和跳跃表(Skip List)。哈希用于存储元素(value)和它们对应的分数(score),确保元素的唯一性,并能快速通过元素找到其分数。跳跃表则用于对元素...

    Redis面试题,来自工作笔记

    - **内部结构**: 使用跳跃表 (skip list) 来保证O(logN)的复杂度。 - **应用场景**: - 排行榜应用,如游戏的玩家等级排名。 - 时间线排序,如微博、推特等社交网络的时间线展示。 #### 6. Bitmaps 位图 - **定义*...

    redis-1.0:redis 1.0源码学习使用

    这些数据类型的实现基于高效的数据结构,例如 SDS(Simple Dynamic String)用于字符串,ZipList 用于小对象的哈希表和列表,以及 SkipList 用于有序集合。 2. **命令处理**: Redis 的命令处理模块负责解析客户端...

Global site tag (gtag.js) - Google Analytics