Redis 跳表

跳跃表

跳跃表是一种有序的数据结构，通过在每个节点查找，还可以通过顺序性操作来批处理节点。
跳跃表的效率可以和平衡树媲美，并且因为跳跃表的实现比平衡树简单，所以不少程序都使用跳跃表来代替平衡树。

Redis 有2个地方使用跳跃表：

• 实现有序集合键
• 在集群节点中用作内部数据结构

---

Redis跳跃表

Redis 的跳跃表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构体定义。

跳跃表节点

redis.h/zskiplistNode结构用于保存跳跃表节点的相关信息。

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

• 层
  跳跃表节点的level数组可以包含多个元素，每个元素都包含一直指向其他节点的指针。
  程序可以通过这些层来加快访问其他节点的速度。

• 前进指针

• 跨度
  层的跨度用于记录2个节点之间的距离

  • 2个节点之间的

• 后退指针

• 分值和成员

跳跃表

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

• header
  指向跳跃表的表头节点
• tail
  指向跳跃表的表尾节点
• level
  记录米钱跳跃表层内，层数最大呃那个节点层数。
• length
  记录跳跃表的长度

t跳跃表API

zslCreate

/* 创建并返回一个新的跳跃表 */
zskiplist *zslCreate(void)
{
    zskiplist *zsl = zmalloc(sizeof(*zsl));
    // 设置高度和起始层数
    zsl->level = 1;
    zsl->length = 0;

    // 初始化表头节点，T = O(1)
    zsl->header = zslCreateNode(32, 0, NULL);
    for (int j = 0; j < 32; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    zsl->header->backward = NULL;

    // 设置表尾
    zsl->tail = NULL;
}

image.png

zslFree

void zslFree(zskiplist *zsl) 
{
    zskiplistNode *node = zsl->header->level[0].forward, *next;
}

zslInsert

zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) 
{
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    // 在各个层查找节点的插入位置
    // T_wrost = O(N^2), T_avg = O(N log N)
    x = zsl->header;
    for (i = zsl->level - 1; i >= 0; i--) 
    {
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
    }