Abel'Blog

我干了什么?究竟拿了时间换了什么?

0%

Redis-sortedset-学习

发表于 更新于 分类于 ，

简介

记录一下Redis跳表相关的知识。官方是说的sorted set。我这里阅读的是redis-7.0.2版本的源码。非常浅显从函数开始阅读里面的逻辑。为了加快自己的理解，参考了cnblog的一篇分析文档。

skiplist

函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
zskiplist *zslCreate(void);
void zslFree(zskiplist *zsl);
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele);
unsigned char *zzlInsert(unsigned char *zl, sds ele, double score);
int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node);
zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range);
zskiplistNode *zslLastInRange(zskiplist *zsl, zrangespec *range);
double zzlGetScore(unsigned char *sptr);
void zzlNext(unsigned char *zl, unsigned char **eptr, unsigned char **sptr);
void zzlPrev(unsigned char *zl, unsigned char **eptr, unsigned char **sptr);
unsigned char *zzlFirstInRange(unsigned char *zl, zrangespec *range);
unsigned char *zzlLastInRange(unsigned char *zl, zrangespec *range);
unsigned long zsetLength(const robj *zobj);
void zsetConvert(robj *zobj, int encoding);
void zsetConvertToListpackIfNeeded(robj *zobj, size_t maxelelen, size_t totelelen);
int zsetScore(robj *zobj, sds member, double *score);
unsigned long zslGetRank(zskiplist *zsl, double score, sds o);
int zsetAdd(robj *zobj, double score, sds ele, int in_flags, int *out_flags, double *newscore);
long zsetRank(robj *zobj, sds ele, int reverse);
int zsetDel(robj *zobj, sds ele);
robj *zsetDup(robj *o);
void genericZpopCommand(client *c, robj **keyv, int keyc, int where, int emitkey, long count, int use_nested_array, int reply_nil_when_empty, int *deleted);
sds lpGetObject(unsigned char *sptr);
int zslValueGteMin(double value, zrangespec *spec);
int zslValueLteMax(double value, zrangespec *spec);
void zslFreeLexRange(zlexrangespec *spec);
int zslParseLexRange(robj *min, robj *max, zlexrangespec *spec);
unsigned char *zzlFirstInLexRange(unsigned char *zl, zlexrangespec *range);
unsigned char *zzlLastInLexRange(unsigned char *zl, zlexrangespec *range);
zskiplistNode *zslFirstInLexRange(zskiplist *zsl, zlexrangespec *range);
zskiplistNode *zslLastInLexRange(zskiplist *zsl, zlexrangespec *range);
int zzlLexValueGteMin(unsigned char *p, zlexrangespec *spec);
int zzlLexValueLteMax(unsigned char *p, zlexrangespec *spec);
int zslLexValueGteMin(sds value, zlexrangespec *spec);
int zslLexValueLteMax(sds value, zlexrangespec *spec);

插入元素

入口参数

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

参数表：

zsl: zskiplist 跳表数据结构

zskiplist-datastructure

score: double 权重；

sds: 插入的对照值；

读取跳表的头节点，去读取这个头节点的跳表的高度。从高往低扫描：

redis-zkiplist-work

每个跳表中的节点层高都是[0,32)的随机数，每个同层高的链表都会连接起来。

在查询的时候，将会记录自己的

数据结构

zskiplist-datastructure

源码目录：src/server.h 1242 lines。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
typedef char *sds;

struct dict {
    dictType *type;

    dictEntry **ht_table[2];
    unsigned long ht_used[2];

    long rehashidx; /* rehashing not in progress if rehashidx == -1 */

    /* Keep small vars at end for optimal (minimal) struct padding */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
    signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) */
};

// 跳表的子节点

/* ZSETs use a specialized version of Skiplists */
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;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

总结

对比红黑树

红黑树的顺序遍历其实还是走的一次中序遍历，而对于跳表来说，定位到了node，就能直接开启遍历这件事。中序遍历肯定没有链表的遍历来的高效。

跳表里面是使用的单向链表加上索引方式来实现。

通过32级的索引来实现。

引用