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;}
我们可以从图来具体看实际查询的过程:例如我们要查询10这个值
- 首先我们通过head指针从HEAD节点可以获取到第一个节点信息,我们查看第一个层级的forward指针的最高层级就能知道下一个层级节点对应的值为20>16
- 我们再次向下查询一个层级对应的节点,为16>10,仍然比查询值大
- 我们再向下查一个层级,为16=16,这样,我们就查询到了节点值。
- 如果到了最后一个层级仍然没有查询到,那么就说明数据不存在