redis zset源码
文章目录
1. 结构体定义
/* 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;2. debug日志
void print_zsl(zskiplist *zsl) {
struct zskiplistNode *x;
printf("print_zsl length:%lu level:%d\n", zsl->length, zsl->level);
printf("----[from header]---\n");
for (int i=zsl->level-1; i>=0; i--) {
x = zsl->header;
printf("level:%d [header] -> ", i);
for (;x->level[i].forward; x=x->level[i].forward) {
//printf("print_zsl level:%d, ele:%s, score:%lf, span:%lu\n",
// i, x->level[i].forward->ele, x->level[i].forward->score,
// x->level[i].span);
printf("[%s:%lf] -> ", x->level[i].forward->ele, x->level[i].forward->score);
}
printf("\n");
}
printf("-------\n");
x = zsl->tail;
printf("----[from tail]---\n");
for (;x;x=x->backward) {
printf("[%s:%lf] -> ", x->ele, x->score);
}
printf("\n-------\n");
}3. 跳表结构 核心代码
zskiplist *zslCreate(void);
void zslFree(zskiplist *zsl);
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele);
zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range);
zskiplistNode *zslLastInRange(zskiplist *zsl, zrangespec *range);4. 压缩链表转换为跳表
int zsetAdd(robj *zobj, double score, sds ele, int *flags, double *newscore)
zobj->ptr = zzlInsert(zobj->ptr,ele,score);
if (zzlLength(zobj->ptr) > server.zset_max_ziplist_entries)
zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);
if (sdslen(ele) > server.zset_max_ziplist_value)
zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);举例说明
修改配置文件,将zset压缩链表 最小val长度改为1,
这样member名称长度>1,zset将用跳表结构
zset-max-ziplist-value 1
假设zset key=z1, 有8个元素
score值分别是
1,2,3,4,5,6,7,8
其中
1在1层
2在2层
3在1层
4在3层
5在1层
6在2层
7在1层
8在4层
那么跳表结构如下
debug日志输出如下:
print_zsl length:8 level:4
----[from header]---
level:3 [header] -> [m8:8.000000] ->
level:2 [header] -> [m4:4.000000] -> [m8:8.000000] ->
level:1 [header] -> [m2:2.000000] -> [m4:4.000000] -> [m6:6.000000] -> [m8:8.000000] ->
level:0 [header] -> [m1:1.000000] -> [m2:2.000000] -> [m3:3.000000] -> [m4:4.000000] -> [m5:5.000000] -> [m6:6.000000] -> [m7:7.000000] -> [m8:8.000000] ->
-------
----[from tail]---
[m8:8.000000] -> [m7:7.000000] -> [m6:6.000000] -> [m5:5.000000] -> [m4:4.000000] -> [m3:3.000000] -> [m2:2.000000] -> [m1:1.000000] ->
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论