美文网首页
redis 跳表(6)

redis 跳表(6)

作者: lmem | 来源:发表于2017-05-27 21:59 被阅读96次

    跳表(skiplist)是一个特俗的链表,相比一般的链表,有更高的查找效率,其效率可比拟于二叉查找树
    总结跳表的性质:
    1.由很多层结构组成
    2.每一层都是一个有序的链表
    3.最底层(Level 1) 的链表包含所有元素
    4.如果一个元素出现在 Level i 的链表中,则它在 Level i 之下的链表也都会出现。
    5.每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。

    // 跳表节点结构体
    /* ZSETs use a specialized version of Skiplists */
    typedef struct zskiplistNode {
        // 节点数据
        robj *obj;
        // 分数,游戏分数?按游戏分数排序
        double score;
        // 后驱指针
        struct zskiplistNode *backward;
        // 前驱指针数组TODO
        struct zskiplistLevel {
            struct zskiplistNode *forward;
            // 调到下一个数据项需要走多少步,这在计算rank 的非常有帮助
            unsigned int span;
        } level[];
    } zskiplistNode;
    
    typedef struct zskiplist {
        // 跳表头尾指针
        struct zskiplistNode *header, *tail;
        // 跳表的长度
        unsigned long length;
        // 跳表的高度
        int level;
    } zskiplist;
    

    ** 1.查找过程 **

    Paste_Image.png

    2.跳表的插入
    跳表算法描述如下:找出每一层新插入数据位置的前驱并保存,在 Redis 中跳表插入是根据 score/member 的大小(看不懂可以参看 redis ZADD 命令)来决定插入的位置;将新数据插入到指定位置,并调整指针,在 redis 中还会调整 span。

    Paste_Image.png
    zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {
            // update 是插入节点所在位置的前一个节点。我们在学习链表插入的时候,需要找到插入
            // 位置的前一个节点。因为在跳表中一个节点是有多个前驱指针的,所以这里需要保存的
            // 是多个节点,而不是一个节点
        zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
        unsigned int rank[ZSKIPLIST_MAXLEVEL];
        int i, level;
        redisAssert(!isnan(score));
        x = zsl->header;
        // 遍历skiplist 中所有的层,找到数据将要插入的位置,并保存在update 中
        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 &&
                compareStringObjects(x->level[i].forward->obj,obj) < 0))) {
                rank[i] += x->level[i].span;
                x = x->level[i].forward;
            }
            // update[i] 记录了新数据项的前驱
            update[i] = x;
        }
        // random 一个level,是随机的
        /* we assume the key is not already inside, since we allow duplicated
        * scores, and the re-insertion of score and redis object should never
        * happen since the caller of zslInsert() should test in the hash table
        * if the element is already inside or not. */
        level = zslRandomLevel();
        // random level 比原有的zsl->level 大,需要增加skiplist 的level
        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,obj);
        for (i = 0; i < level; i++) {
            // 新节点项插到update[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;
        }
        // 更高的level 尚未调整span
        /* 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;
        // 调整skiplist 的长度
            zsl->length++;
        return x;
    }
    

    3. 跳表的删除
    跳表的删除算和插入算法步骤类似:找出每一层需删除数据的前驱并保存;接着调整指针,在 Redis 中还会调整 span

    Paste_Image.png
    // x 是需要删除的节点
    // update 是每一个层x 的前驱数组
    /* Internal function used by zslDelete, zslDeleteByScore and zslDeleteByRank */
    void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
        int i;
        // 调整span 和forward 指针
        for (i = 0; i < zsl->level; i++) {
        if (update[i]->level[i].forward == x) {
            update[i]->level[i].span += x->level[i].span - 1;
            update[i]->level[i].forward = x->level[i].forward;
        } else {
        // update[i]->level[i].forward == NULL,只调整span
            update[i]->level[i].span -= 1;
            }
        }
        // 调整后驱指针
        if (x->level[0].forward) {
            x->level[0].forward->backward = x->backward;
        } else {
            zsl->tail = x->backward;
        }
        // 删除某一个节点后,层数level 可能降低,调整level
        while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
            zsl->level--;
        // 调整跳表的长度
            zsl->length--;
    }
    

    Redis 中的跳表
    Redis 中结合跳表(skiplist)和哈希表(dict)形成一个新的数据结构 zset。添加 dict 是为了快速定位跳表中是否存在某个 member!

    typedef struct zset {
    dict *dict;
    zskiplist *zsl;
    } zset;
    
    

    相关文章

      网友评论

          本文标题:redis 跳表(6)

          本文链接:https://www.haomeiwen.com/subject/pyzqfxtx.html