redis skip list 结构解析

本文主要是介绍redis skip list 结构解析，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

先从基本的，去除掉span以后的开始 

// zset的数据结构定义
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        // 表示到下一个节点之间跨越了多少个节点。
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

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

// 去除span后的zslInsert的插入逻辑
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    //注意，这个是所有的level
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    int i, level;
 
	//每层结点找到插入位置前一结点
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        // 针对某个level来说，forward若小于当前score，则继续往前走，由于通过forward去找，最后找到的是它的不小于它的前一个节点，放置在update中，算法链表可以考虑使用类似的方法
        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)))
        {
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    

	//随机插入结点的层级
    level = zslRandomLevel();
	//将新层级header补充到update[]，update[i]保存了i层级插入位置前一结点
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            update[i] = zsl->header;
        }
        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;
    }
 
	//第一层是双向链表
    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;
}
 
————————————————
版权声明：本文为CSDN博主「_Lance」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_19648191/article/details/85381769

带入span的 插入分析

// span的含义
/* Insert a new node in the skiplist. Assumes the element does not already
 * exist (up to the caller to enforce that). The skiplist takes ownership
 * of the passed SDS string 'ele'. */
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    // update[i]保存了i层级插入位置前一结点
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    // 每一层的排序，从1开始
    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 
        // span的话其实就是跨度，这一层中距离下一个节点有多少跨度，先取到上一层的rank值。
//如果为初始值，那么设置rank为0，rank用来计算span的值*/
        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，rank实际上是前置的span（即到下一个节点的跨度）的和，
//最后得到的是到前置节点为止的总跨度（因为foward节点小于它的时候，才去加上当前节点的span，
//即若forward小于它，就去计算到forward节点的span），只是按照level的循环计算到当前level
//的x的，新插入的节点一定在x后面了。
            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  rank[0]实际上是
//最下面一层的值，也就是最下面的rank，i层其实是i层前置节点的数值*/
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        // +1 是说插入了一个节点，导致前置节点+1
        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;
}

插入后

# 插入前
header(7)                                                        tail
header                          9(3)                      15     tail
header        1                 9(3)                      15     tail
header        1     3           9(3)                      15     tail
header        1     3     7     9(1)     10(2)            15     tail
header        1     3     7     9(1)     10(1)     14     15     tail
 
# 插入时
header(7)                                                        tail
header                          9(3)                      15     tail
header        1                 9(3)                      15     tail
header        1     3           9(2)                      15     tail
header        1     3     7     9(1)     10(1)            15     tail
header        1     3     7     9(1)     10(1)     14     15     tail
 
# 插入时
header(7)                                                             tail
header                          9(3)                           15     tail
header        1                 9(3)                           15     tail
header        1     3           9(2)             13(2)         15     tail
header        1     3     7     9(1)     10(1)   13(2)         15     tail
header        1     3     7     9(1)     10(1)   13(1)  14     15     tail
 
# 插入后
header(8)                                                             tail
header                          9(4)                           15     tail
header        1                 9(4)                           15     tail
header        1     3           9(2)             13(2)         15     tail
header        1     3     7     9(1)     10(1)   13(2)         15     tail
header        1     3     7     9(1)     10(1)   13(1)  14     15     tail
看
————————————————
版权声明：本文为CSDN博主「_Lance」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_19648191/article/details/85381769

这篇关于redis skip list 结构解析的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！