Redis - 跳表

喜欢ヅ旅行 2021-08-31 05:03 318阅读 0赞

### 跳表 ###

*  0. 前言
 *  1. 结构源码
 *  2. 创建
 *  3. 插入
 *  4. 删除
 *  5. 获取

# 0. 前言 #

`Redis`的跳表在面试过程中，经常被问到，这里通过源码深入研究一个其实现原理。

# 1. 结构源码 #

// 跳表中的每一个节点的结构
    typedef struct zskiplistNode { 
        // 成员对象，sds 结构
        sds ele;
        // 分值
        double score;
        // 后退指针，指向当前节点的前一个指针
        struct zskiplistNode *backward;
        struct zskiplistLevel { 
        	// 前进指向
            struct zskiplistNode *forward;
            // 前进指针指向的节点和当前节点的距离
            unsigned long span;
        } level[];
    } zskiplistNode;
    
    // 跳表对象
    typedef struct zskiplist { 
    	// header 表头
    	// tail 表尾
        struct zskiplistNode *header, *tail;
        // 跳表长度（不包含表头节点）
        unsigned long length;
        // 非表头节点的最大层
        int level;
    } zskiplist;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70]

# 2. 创建 #

/* Create a skiplist node with the specified number of levels. * The SDS string 'ele' is referenced by the node after the call. */
    zskiplistNode *zslCreateNode(int level, double score, sds ele) { 
        zskiplistNode *zn =
            zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
        zn->score = score;
        zn->ele = ele;
        return zn;
    }
    
    /* Create a new skiplist. */
    zskiplist *zslCreate(void) { 
        int j;
        zskiplist *zsl;
    
        zsl = zmalloc(sizeof(*zsl));
        zsl->level = 1;
        zsl->length = 0;
        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;
    }

# 3. 插入 #

/* 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 用来记录需要进行更新的节点
        zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
        // rank 用来记录每层到新元素插入位置的距离
        unsigned int rank[ZSKIPLIST_MAXLEVEL];
        int i, level;
    
        serverAssert(!isnan(score));
        x = zsl->header;
        // 找到插入的位置
        // 从最高层向下寻找
        for (i = zsl->level-1; i >= 0; i--) { 
            
            // 最高层 rank 初始化为 0，下面的层初始化为上一层的结果
            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;
        }
        // 随机生成一个层数（1~32） 
        level = zslRandomLevel();
        if (level > zsl->level) { 
        	// 初始化空白 rank 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++) { 
        	// 新插入的元素一定是 update 的下一个节点
            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 */
            // 计算 span
            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 */
        // 未接触的节点的span 值也需要加一
        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;
    }

# 4. 删除 #

/* Internal function used by zslDelete, zslDeleteRangeByScore and * zslDeleteRangeByRank. */
    void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) { 
        int i;
        // 所有和被删除节点x有关的节点的指针，解除它们之间的关系
        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].span -= 1;
            }
        }
        // 更新被删除节点 x 的前进和后退指针
        if (x->level[0].forward) { 
            x->level[0].forward->backward = x->backward;
        } else { 
            zsl->tail = x->backward;
        }
        // 更新跳跃表最大层数（只有被删除节点是跳跃表最高的节点时才执行）
        while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
            zsl->level--;
        zsl->length--;
    }

# 5. 获取 #

/* Find the first node that is contained in the specified range. * Returns NULL when no element is contained in the range. */
    zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range) { 
        zskiplistNode *x;
        int i;
    
        /* If everything is out of range, return early. */
        if (!zslIsInRange(zsl,range)) return NULL;
    
        x = zsl->header;
        for (i = zsl->level-1; i >= 0; i--) { 
            /* Go forward while *OUT* of range. */
            // 检测节点是否小于range中的最小项，如果是，则继续向后找
            while (x->level[i].forward &&
                !zslValueGteMin(x->level[i].forward->score,range))
                    x = x->level[i].forward;
        }
    
        /* This is an inner range, so the next node cannot be NULL. */
        x = x->level[0].forward;
        serverAssert(x != NULL);
    
        /* Check if score <= max. */
        if (!zslValueLteMax(x->score,range)) return NULL;
        return x;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdfemhhb18_size_16_color_FFFFFF_t_70]: /images/20210813/03d19c816c744ccaac51481e8515e484.png