面向自由编程

redis系列：跳跃表

Posted on Edited on In
Symbols count in article: 1.1k Reading time ≈ 1 mins.

基本结构

数据结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct zskiplistNode {
    //成员对象
    robj *obj;
    //分值
    double score;
    //后退指针
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        //前进指针
        struct zskiplistNode *forward;
        //跨度
        unsigned int span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

  • score是一个double类型树，跳表中所有节点按照分值排序
  • obj（5.0版本为ele）:存储一个sds类型对象

内部实现

  1. 节点层高
1
2
3
4
5
6
7
8
#define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4 */

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
    level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

level的初始值为1，通过while循环，每次生成一个随机值，取这个值的低16位作为x，当x小于0.25倍的0xFFFF时，level的值加1；否则退出while循环。最终返回level和ZSKIPLIST_MAXLEVEL两者中的最小值。
1）节点层高为1的概率为(1-p)。
2）节点层高为2的概率为p(1-p)。
3）节点层高为3的概率为p2 (1-p)。
4）……
5）节点层高为n的概率为pn-1 (1-p)。
节点期望层高为 E = 1 / (1 - p) .

  1. 创建跳跃表

1）创建跳跃表结构体对象zsl。
2）将zsl的头节点指针指向新创建的头节点。
3）跳跃表层高初始化为1，长度初始化为0，尾节点指向NULL。

  1. 插入节点
  • 查找要插入的位置
  • 调整跳跃表高度
  • 插入节点
  • 调整backward

源代码中的大概思路就是通过for循环来对每个高度进行遍历，找到前驱和后继节点，通过rank和update两个数组记录，最后调整指针。

  1. 删除节点
  • 查找需要更新的节点
  • 设置span和forward

跳跃表应用

跳跃表主要应用于有序集合的底层实现（有序集合的另一种实现方式为压缩列表）。