凌云的博客

行胜于言

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 值,目前为: c #define ZSKIPLIST_MAXLEVEL 64 /* Should be enough for 2^64 elements */ #define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4 */