Redis数据结构：跳表

2015-02-05 20:25 Redis redis , 跳跃表 , 数据结构

Redis数据结构：跳表

引言

Redis的有序集合有两种实现方式：

基于压缩列表(ziplist)实现（当数据量较少时，采用此种方式）
基于跳跃表(skiplist)和字典实现

所以，跳表是Redis中实现有序结合采用数据结构之一。关于跳跃表这种数据结构更详细的介绍，可以关注本博客的另一篇文章数据结构之跳跃表。本文重点讲解跳跃表在Redis上的具体实现。

在此之前，我们要知道的Redis有序集合的一些特性：

每个元素包含两个部分，成员对象和分值。集合按分值大小有序排列。
分值允许重复，但成员对象是唯一的。

实现

跳跃表节点结构定义


xxxxxxxxxx
typedef struct zskiplistNode {
    // member 对象
    robj *obj;
    // 分值
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 这个层跨越的节点数量；用来计算成员在整个链表的排位(rank)
        unsigned int span;
    } level[];
} zskiplistNode;

从代码我们可以看出，Redis采用的是双端链表，既有前进指针，也有后退指针。要注意的是，后退指针只有一个，所以从后往前遍历，不能”跳”着走，只能老老实实一步一步脚印。前进指针则相反。

obj：表示成员对象；实际上是个字符串对象，保存着一个SDS值。
score：分值，double类型的浮点数

跳跃表结构定义


xxxxxxxxxx
typedef struct zskiplist {
    // 头节点，尾节点
    struct zskiplistNode *header, *tail;
    // 节点数量
    unsigned long length;
    // 目前表内节点的最大层数
    int level;
} zskiplist;

结构总览图

跳跃表API

函数	作用	复杂度
`zslCreateNode`	创建并返回一个新的跳跃表节点	最坏 O(1)O(1)
`zslFreeNode`	释放给定的跳跃表节点	最坏 O(1)O(1)
`zslCreate`	创建并初始化一个新的跳跃表	最坏 O(1)O(1)
`zslFree`	释放给定的跳跃表	最坏 O(N)O(N)
`zslInsert`	将一个包含给定 `score` 和 `member` 的新节点添加到跳跃表中	最坏 O(N)O(N) 平均 O(logN)O(log⁡N)
`zslDeleteNode`	删除给定的跳跃表节点	最坏 O(N)O(N)
`zslDelete`	删除匹配给定 `member` 和 `score` 的元素	最坏 O(N)O(N) 平均 O(logN)O(log⁡N)
`zslFirstInRange`	找到跳跃表中第一个符合给定范围的元素	最坏 O(N)O(N) 平均 O(logN)O(log⁡N)
`zslLastInRange`	找到跳跃表中最后一个符合给定范围的元素	最坏 O(N)O(N) 平均 O(logN)O(log⁡N)
`zslDeleteRangeByScore`	删除 `score` 值在给定范围内的所有节点	最坏 O(N2)O(N2)
`zslDeleteRangeByRank`	删除给定排序范围内的所有节点	最坏 O(N2)O(N2)
`zslGetRank`	返回目标元素在有序集中的排位	最坏 O(N)O(N) 平均 O(logN)O(log⁡N)
`zslGetElementByRank`	根据给定排位，返回该排位上的元素节点	最坏 O(N)O(N) 平均 O(logN)

参考

书籍《Redis设计与实现》