跳跃表的底层实现

跳跃表的底层是由 C 语言实现的，它的实现源码如下：

typedef struct zskiplistNode {
   
	// 成员对象
    robj *obj;
    double score; // 分值
    struct zskiplistNode *backward; // 回退指针
    //层
    struct zskiplistLevel {
   
    	// 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
} zskiplistNode;

• obj：用于存储字符串类型的数据；
• score：用于存储排序的分值；
• backward：后退指针，只能指向当前节点最底层的前一个节点，头节点和第一个节点 backward 指向 NULL，从后向前遍历跳跃表时使用；
• level：柔性数组。每个节点的数组长度不一样，在生成跳跃表节点时，随机生成一个 1-64 的值，值越大出现的概率越低。level 数组的每项包含以下两个元素：
  • forward：指向本层下一个节点，尾节点的 forward 指向 NULL；
  • span：forward 指向的节点与本节点之间的元素个数，span 值越大，跳过的节点个数越多。

除了跳跃表节点外，还需要一个跳跃表结构来管理节点，Redis 使用 zskiplist 结构体，定义如下：

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

• header：指向跳跃表头节点。头节点是跳跃表的一个特殊节点，它的 level 数组元素个数为 64。头节点在有序集合中不存储任何 member 和 score 值，ele 值为 NULL, score 值为 0，也不计入跳跃表的总长度。头节点在初始化时，64 个元素的 forward 都指向 NULL,span 值都为 0；
• tail：指向跳跃表尾节点；
• length：跳跃表长度，表示除头节点之外的节点总数；
• level：跳跃表的高度。

它的结构实现如下图所示：