跳表是 有序集合的底层实现之一

定义

跳表节点 zskiplistNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct zskiplistNode {
    // 成员对象
    robj *obj;
    // 分值
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
} zskiplistNode;
  • robj：保存的对象
  • score：对象的分值
  • backward：指向前一个节点的指针
  • level：层。每次创建一个跳表节点时，程序会根据幂次定律（越大的数字出现的概率越小）随机生成一个介于1~32之间的值作为 level 数组的大小，这个大小就是层的高度
    • level.forward：前进指针，指向下一个同层的节点
    • level.span：跨度，当前节点和前进指针指向的节点的距离，主要用途是计算排位

跳表 zskiplist

1
2
3
4
5
6
7
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;
  • header、tail：分别指向头节点和尾节点
  • length：表中节点的数量
  • level：记录表中最高层的节点的层数，不算头节点

多个 zskiplistNode 组成一个跳表，而 zskiplist 结构则保存了跳表的关键信息，使程序可以更方便的操作跳表

zskiplist 的头节点指向一个高度为32的空节点，方便高层跳跃

zset

1
2
3
4
5
6
7
8
9
typedef struct zset {
    // 字典，键为成员，值为分值
    // 用于支持 O(1) 复杂度的按成员取分值操作
    dict *dict;
    // 跳跃表，按分值排序成员
    // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
    // 以及范围操作
    zskiplist *zsl;
} zset;

跳表是zset的底层实现之一。

尽管跳表可以快速的按照分值定位成员，但是这样的需求远远不够满足 zset 的定义。zset 是一个有序集合，不仅各个节点要按照 score 排序，还必须保证所有节点的成员对象 obj 唯一。因此 zset 以 dict 和 跳表两种数据结构配合使用，满足了有序集合这个定义，而且能以较低的时间复杂度实现增删改查等操作。

总结

  • 跳跃表是有序集合的底层实现之一
  • Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点
  • 每个跳跃表节点的层高都是1至32之间的随机数
  • 在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的
  • 跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序