关于zrange时间复杂度的问题

[hongliuliao]

https://github.com/huangz1990/annotated_redis_source/blob/unstable/src/t_zset.c
上的注释说的是o(n),但是为啥官方文档上说是log(n)+m呢?

[huangz1990]

代码里注释的是最坏复杂度，当时因为时间比较紧张，就没有在代码里添加平均复杂度。

在 www.redisbook.com 里是有最坏复杂度和平均复杂度的，可以参考书本。

[hongliuliao]

为啥我觉得平均也应该是o(n)呢,如果是根据score来找的话,确实平均是log(n),但是range中是根据索引呀,那查找的时候应该和链表根据索引查找的复杂度是一样的吧??

[huangz1990]

查找索引的平均复杂度也是 log(N) 的，过程和查找元素类似，都是可以利用跳跃表性质的。

每个跳跃表节点都有一个 level 结构，这个结构里面都有一个 span 属性，这个属性记录了这个层跨越了多少节点，通过计算多个层跨越的节点数总和，程序就可以在平均 log(N) 的时间内找到起始索引所指示的位置。

具体细节请看源码，请特别关注那些和 span 属性有关的代码。

Redis 官网所说的 log(N) + M 是指：

1. 定位到开头索引的开头元素， log(N)
2. 取出从开头索引到结尾索引的所有元素， M

[hongliuliao]

嗯,我找到了,确实是log(n),代码如下:

zskiplistNode* zslGetElementByRank(zskiplist *zsl, unsigned long rank) {
zskiplistNode *x;
unsigned long traversed = 0;
int i;

x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
    while (x->level[i].forward && (traversed + x->level[i].span) <= rank)
    {
        traversed += x->level[i].span;
        x = x->level[i].forward;
    }
    if (traversed == rank) {
        return x;
    }
}
return NULL;

}
这个span是redis自己加的吧?标准的skiplist中也有这个属性?

[huangz1990]

是自己加的，我在书中也忘记说这个了，等下一版加上去才行。

谢谢你提醒我了。