Redis数据结构之跳跃表-蒲公英云

Redis数据结构之跳跃表

在Redis5大数据结构中，跳跃表（skiplist）是比较难理解的，同时却也是使用比较少的数据结构，只在实现有序集合zset和集群节点内部槽位和键的对饮关系数据结构中用到了。

数据结构代码

typedef struct zskiplist{
    struct zskiplistNode *header, *tail;//指定头节点和尾节点
    unsigned long length;//集合长度
    int level；//跳跃表最大深度，即以节点中层数最多的那个为准，头节点不包括在内
}zskiplist；

跳跃表单节点数据结构

typedef struct zskiplistNode{
    struct zskiplistNode *backward；//后退指针
    double score；//分值
    robj *obj；//成员对象
    struct zskiplistLevel{
   //层对象
        struct zskiplistNode *forward;//前进指针
        unsigned int span;//两个节点之间的距离跨度，主要用于获取当前节点排位
    }level[];
}zskiplistNode;

头节点的后退指针和成员对象、分值都不会被使用到。尾节点的前进指针都为null。
跳跃表每创建一个节点的时候，都会根据幂次定律随机生成一个介于1～32的数值作为该节点的层数，即zskiplistLevel数组的长度。也就是说跳跃表的最大深度为32。一般来说，层数越多，则从该节点访问其他节点的速度会越快。

当跳跃表用于表示集群中槽位和键的关系的时候，score为槽位号(score可重复，节点按键排序)，成员是数据库键。通过遍历跳跃表可以很轻易的统计某个槽位中所有键及其个数。