江苏龙网

  1. 主页 > 生活百科 > >

Redis跳跃列表究竟怎么跳( 二 )

Redis

首先是查找对应元素是否存在，如果存在并且没有参数NX，就记录下这个元素当前的分数 。这里可以看出zset中的hash字典是用来根据元素获取分数的 。
接着判断是不是要执行increment命令，如果是的话，就用当前分数加上指定分数，得到新的分数newscore 。如果分数发生了变化，就调用zslUpdateScore函数，来更新skiplist中的节点，另外还要多一步操作来更新hash字典中的分数 。
如果要插入的元素不存在，那么就直接调用zslInsert函数 。
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) { zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x; unsigned int rank[ZSKIPLIST_MAXLEVEL]; int i, level; serverAssert(!isnan(score)); x = zsl->header; for (i = zsl->level-1; i >= 0; i--) { /* store rank that is crossed to reach the insert position */ rank[i] = i == (zsl->level-1) ? 0 : rank[i+1]; 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[i] += x->level[i].span; x = x->level[i].forward; } update[i] = x; } /* we assume the element is not already inside, since we allow duplicated * scores, reinserting the same element should never hAppen since the * caller of zslInsert() should test in the hash table if the element is * already inside or not. */ level = zslRandomLevel(); if (level > zsl->level) { for (i = zsl->level; i < level; i++) { rank[i] = 0; update[i] = zsl->header; update[i]->level[i].span = zsl->length; } zsl->level = level; } x = zslCreateNode(level,score,ele); for (i = 0; i < level; i++) { x->level[i].forward = update[i]->level[i].forward; update[i]->level[i].forward = x; /* update span covered by update[i] as x is inserted here */ x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]); update[i]->level[i].span = (rank[0] - rank[i]) + 1; } /* increment span for untouched levels */ for (i = level; i < zsl->level; i++) { update[i]->level[i].span++; } x->backward = (update[0] == zsl->header) ? NULL : update[0]; if (x->level[0].forward) x->level[0].forward->backward = x; else zsl->tail = x; zsl->length++; return x;}复制代码函数一开始定义了两个数组，update数组用来存储搜索路径，rank数组用来存储节点跨度 。
第一步操作是找出要插入节点的搜索路径，并且记录节点跨度数 。
接着开始插入，先随机一个层数 。如果随机出的层数大于当前的层数，就需要继续填充update和rank数组，并更新skiplist的最大层数 。
然后调用zslCreateNode函数创建新的节点 。
创建好节点后，就根据搜索路径数据提供的位置，从第一层开始，逐层插入节点（更新指针），并其他节点的span值 。
最后还要更新回溯节点，以及将skiplist的长度加一 。
这就是插入新元素的整个过程 。
更新过程
了解了插入过程以后我们再回过头来看更新过程
zskiplistNode *zslUpdateScore(zskiplist *zsl, double curscore, sds ele, double newscore) { zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x; int i; /* We need to seek to element to update to start: this is useful anyway, * we'll have to update or remove it. */ x = zsl->header; for (i = zsl->level-1; i >= 0; i--) { while (x->level[i].forward && (x->level[i].forward->score < curscore || (x->level[i].forward->score == curscore && sdscmp(x->level[i].forward->ele,ele) < 0))) { x = x->level[i].forward; } update[i] = x; } /* Jump to our element: note that this function assumes that the * element with the matching score exists. */ x = x->level[0].forward; serverAssert(x && curscore == x->score && sdscmp(x->ele,ele) == 0); /* If the node, after the score update, would be still exactly * at the same position, we can just update the score without * actually removing and re-inserting the element in the skiplist. */ if ((x->backward == NULL || x->backward->score < newscore) && (x->level[0].forward == NULL || x->level[0].forward->score > newscore)) { x->score = newscore; return x; } /* No way to reuse the old node: we need to remove and insert a new * one at a different place. */ zslDeleteNode(zsl, x, update); zskiplistNode *newnode = zslInsert(zsl,newscore,x->ele); /* We reused the old node x->ele SDS string, free the node now * since zslInsert created a new one. */ x->ele = NULL; zslFreeNode(x); return newnode;}复制代码和插入过程一样，先保存了搜索路径 。并且定位到要更新的节点，如果更新后节点位置不变，则直接返回 。否则，就要先调用zslDeleteNode函数删除该节点，再插入新的节点 。
删除过程
Redis中skiplist的更新过程还是比较容易理解的，就是先删除再插入，那么我们接下来就看看它是如何删除节点的 。


推荐阅读


上一篇：智能马桶盖 女性最好不要买 智能马桶盖能洗女人的前面吗

下一篇：洗洗衣机的过期了还能用么 没拆封的洗衣片过期了能用吗