Redis 5 数据结构（七）skiplist

分类：Redis| 发布时间：2019-05-11 00:48:00

概述

本文是 Redis 5 数据结构系列的第七篇，主要讲解 skiplist 的结构和实现细节。

本文不会讲解 skiplist 本身的定义和算法细节，如果没接触过 skiplist 的可以先看看 skiplist 原理与实现。

skiplist 的实现

skiplist 的源码在 src/server.h 和 src/t_zset.c。

Redis 的 skiplist 基本就是 William Pugh in 论文："Skip Lists: A Probabilistic Alternative to Balanced Trees" 里面描述的 skiplist 的 C 语言实现版本。 Redis 的 skiplist 在论文描述的实现的基本上做了如下改变：

原文的 skiplist 需要 scores（论文中的 key）是唯一的，在 Redis 的实现里 scores 去掉了这个限制，允许有重复的 scores
不仅比较 score 同时需要对数据进行比较
每个节点拥有一个指向 "level 1" 的回朔(back)指针（用于实现 ZREVRANGE 命令）
每个 forward 指针都关联一个 span 值，表示 forward 指针指向的节点和本节点的距离（forward 为 NULL 时 span 为 0）

skiplist 结构的定义如下：

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

和系列文章前几篇介绍的不同。 Redis 的 skiplist 总是和哈希表一起组合使用，用来表示 Redis 中的有序集合对象，因此 skiplist 的实现代码并没有使用单独和源文件，而是和有序集合相关代码一起放在了 src/t_zset.c 中。

下图给出了一个 Redis 实现的 skiplist 的示例：

skiplist API

zskiplist *zslCreate(void);

创建一个 skiplist

void zslFree(zskiplist *zsl);

释放一个 skiplist

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele);

插入一个 skiplist 节点。假设 skiplist 不存在此节点（由调用者保证）。 sds 的所有权转移到 skiplist 中。

返回插入的节点。

int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node);

删除 skiplist 中和传入的 score 与 element 匹配的节点。若 skiplist 中找到指定的节点则返回 1，否则返回 0。

如果 'node' 为 NULL 则会使用 zslFreeNode 删除节点，否则将节点赋值给 *node 指针（匹配的节点只会从 skiplist 中 unlink）。

typedef struct {
    double min, max;
    int minex, maxex; /* are min or max exclusive? */
} zrangespec;

zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range);
zskiplistNode *zslLastInRange(zskiplist *zsl, zrangespec *range);

zslFirstInRange 返回第一个在 range 中的节点，若不存在则返回 NULL。
zslLastInRange 返回最后一个在 range 中的节点，若不存在则返回 NULL。

unsigned long zslGetRank(zskiplist *zsl, double score, sds o);

返回指定节点的 rank 值，返回 0 表示未找到指定的节点。

注意： rank 表示的是 zsl->header 和指定节点的距离，因此所有有效的节点总是大于等于 1。

int zslValueGteMin(double value, zrangespec *spec) {
    return spec->minex ? (value > spec->min) : (value >= spec->min);
}

int zslValueLteMax(double value, zrangespec *spec) {
    return spec->maxex ? (value < spec->max) : (value <= spec->max);
}

这两个方法比较简单，直接把实现贴出来了

总结

Redis 的 skiplist 总是和哈希表一起使用，用于表示有序集合
Redis 为 skiplist 的每个 forward 指针添加了一个 span 成员，因此可以快速地返回指定 rank 的节点
skiplist 中的节点按照 score 从小到达排序
Redis 在 server.h 上定义了 skiplist 的 max level 和 p 值，目前为：

#define ZSKIPLIST_MAXLEVEL 64 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */

凌云的博客

行胜于言