Redis数据结构之跳跃表

客官°小女子只卖身不卖艺 2022-11-06 09:54 130阅读 0赞

# 一：Redis数据结构之跳跃表 #

跳跃表是一个有序的数据结构，它可以通过跳跃表节点维持的多个指向其他节点的指针，从而达到快速访问的目的，是一种可以作为代替平衡树的数据结构。而且跳跃表的实现相对更简单一点。

Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合的元素数量比较多，又或者有序集合的成员是比较长的字符串时，则Redis就会用跳跃表。（说白了就是为了提高查找效率）

# 二：跳跃表的实现 #

redis跳跃表由跳跃表和跳跃表节点构成。

*  跳跃表节点由server.h/zskiplistNode结构构成：

/* ZSETs use a specialized version of Skiplists */
    typedef struct zskiplistNode {
        //成员对象
        sds ele;
        //分值
        double score;
        //后退指针
        struct zskiplistNode *backward;
        //层 （都是1到32之间的随机数）
        struct zskiplistLevel {
            //前进指针
            struct zskiplistNode *forward;
            //跨度
            unsigned long span;
        } level[];
    } zskiplistNode;

*  跳跃表由server.h/zskiplist结构构成：

typedef struct zskiplist {
        //指向跳跃表的表头节点和表尾节点
        struct zskiplistNode *header, *tail;
        //记录跳跃表中跳跃节点数量（表头节点不计入其中）
        unsigned long length;
        //记录跳跃表中跳跃节点最大层树
        int level;
    } zskiplist;

跳跃表如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70][]

最左边是一个zskiplist，其他都是zskiplistNode，表头的跳跃表节点和其他的节点是一样的，也有分值、后退指针和对象成员，对象成员则保存一个SDS值。

存入跳跃表中的对象成员必须是唯一的，但是分值可以相同，如果分值相同的情况下，则会根据成员对象在字典的大小进行排序，成员对象小的会排在前面（靠近表头的方向），成员对象大的会派在后面（靠近表尾的方向）。

如存在三个对象o1,o2,o3，这三个对象的分值是一样的，但保存对象o1的节点排在对象o2和o3之前，保存对象o2排在o3之前，那么o1，o2，o3在跳跃表的排序如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1][]

跳跃表可以o(1)复杂度内获取跳跃表的表头节点和表尾节点，获取跳跃表的层高最大那个节点的层数量，跳跃表节点的数量（去掉表头节点）

# 三：跳跃表API #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 2][]

zslCreate函数如下：

/* 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;
    }

zslFreeNode函数如下：

/* Free the specified skiplist node. The referenced SDS string representation
     * of the element is freed too, unless node->ele is set to NULL before calling
     * this function. */
    void zslFreeNode(zskiplistNode *node) {
        sdsfree(node->ele);
        zfree(node);
    }
    
    /* Free an sds string. No operation is performed if 's' is NULL. */
    void sdsfree(sds s) {
        if (s == NULL) return;
        s_free((char*)s-sdsHdrSize(s[-1]));
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70]: /images/20221023/f03f4062a9aa4a2392fcd81a82c9b523.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1]: /images/20221023/34ca66e271584b8e82e153bbedec3edf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 2]: /images/20221023/5152766714c34781a855f581c38fa650.png