Redis数据结构：跳跃表

1. 跳跃表是有序集合（zset）的底层实现之一；

2. 由zskiplist和zskiplistNode组成；

3. 每个跳跃表节点的层数都是1-32之间的随机数（每创建一个节点的时候，程序会随机生成一个数[1-32]作为level数组的大小）；

4. 同一个跳跃表中，多个节点可以包含相同的分值，但节点的成员对象是唯一的；

5. 按分值排序，若分值相同就按成员对象大小排序。

zskiplist数据结构

typedef struct zskiplist {

    //头节点和尾节点

    struct zskiplistNode *header, *tail;

    //节点数量

    unsigned long length;

    //表中节点最大层数

    int level;

} zskiplist;

zskiplistNode 数据结构

typedef struct zskiplistNode {

    //层

    struct zskiplistLevel {

        //前进指针

        struct zskiplistNode *forward;

        //跨度

        unsigned int span;

    } level [];

    //后退指针

    struct zskiplistNode *backward;

    //分值

    double score;

    //成员对象

    robj *obj;

} zskiplistNode;

1. 前进指针（leve[i].forward）用于表头向表尾方向访问节点。

2. 跨度（level[i].span）记录两个节点之间的关系。

3. 后退指针（backward）用于表尾向表头方向访问节点，每次只能后退一个节点。

4. 分值（score），表中的节点按分值大小排序。

5. 成员对象（obj）是一个指针，指向一个SDS对象。

巴特西

Redis数据结构：跳跃表

最新文章

热门文章