> 文档中心 > Redis数据结构(四)跳跃表—skiplist

Redis数据结构(四)跳跃表—skiplist

  我们知道,跳跃表是一种有序的数据结构,查询平均复杂度为O(logN),最坏O(N)。其效率可以和平衡树相媲美,而且其实现更为简单.
  Redis只在两个地方用到了跳跃表,一个是实现有序集合键,另一个是在集群节点中用作内部数据结构,除此之外,跳跃表在Redis里面没有其他用途。所以我们可以看到关于skiplist的定义都是在server.h(3.0及之前在redis)中,其他的数据结构基本上都有自己单独的定义文件。

我们先来看看跳跃表节点结构的定义如下:

typedef struct zskiplistNode {// 节点value,4.0之前为robj *obj;    sds ele;     // 节点分数    double score;     // 后退指针,可以反向查找    struct zskiplistNode *backward;     struct zskiplistLevel {    // 前进指针 struct zskiplistNode *forward;  // 到下一节点的距离 unsigned long span;     } level[]; // 柔性数组,定义了层级指针和距离下一个节点的距离} zskiplistNode;

我们分别来看看其每个属性:

  • ele
    我们可以看出,跳跃表的节点值保存的是SDS类型的值,也就是我们前面将到的简单动态字符串。
  • score
    这个属性是用于整个跳跃表进行排序的值,当score相同时再使用ele进行排序
  • backward
    后退指针,通过backward我们就可以直接实现逆序的输出,比如使用zrevange命令的时候就可以直接按照backward逆序遍历,而不需要进行逆序翻转。
  • level[i].forward
    前进指针,也就是该层级指向下一个层级节点的指针。用于从表头向表尾方向访问节点。
  • level[i].span
    该变量的意义是该层级到下一个节点的距离。其实这个变量的真正意义是算出该节点的排名,比如rank命令只需要累加变量路径上所有节点的span值就可以了。之所以不直接使用rank来记录绝对排名,是由于如果采用绝对排名,那么在插入和删除的时候该节点后面的所有节点rank值都需要修改,严重影响效率。而使用span则在插入和删除节点的时候只需要修改前后两个节点的span就可以了
    我们可以看一下rank命令的实现就可以看出
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {    zskiplistNode *x;    unsigned long rank = 0;    int i;    x = zsl->header;    // 向下走    for (i = zsl->level-1; i >= 0; i--) {    // 该层节点不为空,且score都小于查找score,或者是在score相同的情况下ele小于查找的ele while (x->level[i].forward &&     (x->level[i].forward->score < score ||  (x->level[i].forward->score == score &&  sdscmp(x->level[i].forward->ele,ele) <= 0))) {     rank += x->level[i].span; // 排名就是所有跳过的span总和     x = x->level[i].forward; } /* x might be equal to zsl->header, so test if obj is non-NULL */ if (x->ele && sdscmp(x->ele,ele) == 0) {     return rank; }    }    return 0;}

我们再来看看对于跳跃表的定义:

typedef struct zskiplist {// 头节点及尾指针    struct zskiplistNode *header, *tail;    // 节点数    unsigned long length;    // 最大层级    int level;} zskiplist;

我们可以看出skiplist的定义很简单,只存储了头节点以及尾指针、节点数和最大层级。之所以是头节点和尾指针,那是因为,头节点并非是真正意义上的有效节点,并没有存储实际的数据,而是初始化了一个空的,层级数默认为最大(32)的节点。我们可以从源码中看出端倪:

/* Create a new skiplist. */zskiplist *zslCreate(void) {    int j;    zskiplist *zsl;    zsl = zmalloc(sizeof(*zsl));    // 初始层级值为1    zsl->level = 1;     // 长度为0,没有有效节点    zsl->length = 0;     // 创建header节点,实际并不是有效节点,层级数为32    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);     for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) { zsl->header->level[j].forward = NULL; zsl->header->level[j].span = 0;    }    zsl->header->backward = NULL;    zsl->tail = NULL;    return zsl;}

Redis数据结构(四)跳跃表—skiplist
我们可以从图来具体看实际查询的过程:例如我们要查询10这个值

  • 首先我们通过head指针从HEAD节点可以获取到第一个节点信息,我们查看第一个层级的forward指针的最高层级就能知道下一个层级节点对应的值为20>16
  • 我们再次向下查询一个层级对应的节点,为16>10,仍然比查询值大
  • 我们再向下查一个层级,为16=16,这样,我们就查询到了节点值。
  • 如果到了最后一个层级仍然没有查询到,那么就说明数据不存在

红酒品牌排行榜