深入了解Redis【六】内部编码数据结构之跳跃表zskiplist

引言

跳跃表(skip list) 可以媲美平衡树(AVL Tree)，是一种插入/删除/搜索都是 O(logN) 的数据结构。
它最大的优势是原理简单、容易实现、方便扩展、效率更高。
因此在一些热门的项目里用来替代平衡树，如 redis, leveldb 等。

在redis中，有序集合键与集群节点中用到跳跃表。

1、数据结构

跳跃表的数据结构有两部分组成：zskiplistNode和zskiplist,位于redis.h源码中。

1.1、跳跃表节点zskiplistNode

/* ZSETs use a specialized version of Skiplists */
/*
 * 跳跃表节点
 */
typedef struct zskiplistNode {
    // 成员对象
    robj *obj;
    // 分值
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
} zskiplistNode;

1.2、跳跃表zskiplist

/*
 * 跳跃表
 */
typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;