关于redis:带你redis从入门到不会系列了解跳跃表只看这篇大概不够

4次阅读

共计 4685 个字符，预计需要花费 12 分钟才能阅读完成。

oh 肉丝
oh 杰克
you jump! i jump!
yeah 一起沉迷在 jump 的喜悦里
明天跟大家来聊聊 redis 的跳跃表

everybody 都须要理解的跳跃表不仅仅是概念还有代码强烈建议浏览《Redis5 设计与源码剖析》陈雷编著

咱们先看看咱们平时罕用的对于 redis 的有序汇合
大家罕用的命令如下

127.0.0.1:6379> zadd jump 1 jack
(integer) 1
127.0.0.1:6379> zadd jump 2 rose
(integer) 1
127.0.0.1:6379> zrange jump 0 1
1) "jack"
2) "rose"

redis的有序汇合的复杂度
ZADD O(M*log(N))，N 是有序集的基数，M 为胜利增加的新成员的数量。
ZRANGE O(log(N)+M)，N 为有序集的基数，而 M 为后果集的基数
ZRANK O(log(N))
ZSCORE O(1)

咱们无妨能够思考下，什么样的数据结构能满足上述，来这时候拿出咱们的数据结构常识储备了。线性表 、 链表 、 栈与队列 、 串、树它全家系列 想想哪种能合乎上述

也是常见问题为什么应用跳表当数据结构

线性表查找合乎增加和删除是 O(n) 不能够
链表增加和删除合乎查找是 O(n) 不能够
树（不论是什么二叉、红黑、B 它全家）如同复杂度能够满足然而咱们看看 zscore 是 O(1) 如同不是内味

而且树的实现有多蛋疼，能够常常听到以下对话
你能够手撕 ** 树吗
我能够爬 ** 树你看能够吗？

zscore 返回有序集 key 中，成员 member 的 score 值。如果是 O（1）的话有链表那味

那么我猜跳表就是链表的它私生子，相对不是树的私生子。

事实上，跳表是一个多层的有序双向链表

有一座楼，有三层高，每个人都会影子分身术，能够每层楼放本人影子 (放不放看每个人的情绪，一旦定了就不能悔恨)，并且每个房间都有通往下一层的楼梯。这里有 3 集体别离狗蛋 A、狗蛋 B、狗蛋 C，有一次考试完结
狗蛋 A 考了 60 分
狗蛋 B 考了 80 分
狗蛋 C 考了 100 分
每个狗蛋依据分数本人排了程序，考的好的站前面。
狗蛋他爸住在最顶楼（第二层）想问问谁考了 100 分
大略图长这个样子

1. 狗蛋他爸问狗蛋 A: 你多少分。狗蛋 A 说:60，这层前面没狗蛋了。
2. 狗蛋他爸在狗蛋 A 的房间往下一层走。
4. 看到了狗蛋 B: 狗蛋 B 说 80 分，前面没有狗蛋了。
5. 狗蛋他爸在狗蛋 B 的房间往下走，发现了狗蛋 C，并且就是考了 100 的那的狗蛋。
路线大略是这样子

有人必定会说，这个还不如有序链表啊搞什么分层

毕竟是洪光光为了省事瞎画的图，咱们再把图粗劣点，咱们再品品这种构造的益处

看了源码你会发现每个狗蛋几层高真的是看狗蛋情绪。

有人说：跳跃表概念我也懂，有本事间接撸源码。
撸就撸，来，大家一起撸～～～～～～～源码

/**
 * 跳跃表节点的构造体
 */
typedef struct zskiplistNode {
    // 用动静字符串的数据 key（member）的类型 如果头节点 NULL
    sds ele;
    // 对应的排序分值 如果头节点 NULL
    double score;
    // 指向前一个节点的戒指 当然头节点指向的 NULL
    struct zskiplistNode *backward;
    // 柔性数组 数组大小 参照 zslRandomLevel(void) 长度为 1 到 64
    struct zskiplistLevel {
        // 指向前一个节点的戒指 当然头节点指向的 NULL
        struct zskiplistNode *forward;
        // 示意该层下的节点数量
        unsigned long span;
    } level[];} zskiplistNode;

/**
 * 跳跃表构造体
 */
typedef struct zskiplist {
    // 指向跳跃表的头和尾部
    struct zskiplistNode *header, *tail;
    // 跳跃表长度 除去头节点
    unsigned long length;
    // 跳跃表的层级
    int level;
} zskiplist;

根据上述的狗蛋图和跳跃表的构造体，看看能不能在心中有个实现思路。如果有的话，就不要往下看了，我怕看了你被我带偏。

1. 层高最多 64 层，具体层高看情绪（随机生成，越大越概率越低）
2. 每层都是有序双向链表（有后退指针和后退指针）
3.header 节点就是相似大学的宿管（晓得每层的房间数和当层下一个房间的指针）
4. 每一层最初的一个节点都是指向 NULL（就是用下个节点是为 NULL 判断是不是本层最初一个）
5. 第 0 层也就是最初一层的节点上数量就是跳跃表的理论长度（想想上述例子，地基都打在第一层，当然能晓得整个具体长度）

#define ZSKIPLIST_MAXLEVEL 64 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */


/**
 * 随机生产跳跃表节点的层高
 * @return
 */
int zslRandomLevel(void) {
    // 默认层高 1 层
    int level = 1;
    // &0xFFFF = 65535 只取低 16 位 相当于只获取 1 ～ 65535
    // ZSKIPLIST_P -> 0.25
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    // 最终的概率为 1/(1 - ZSKIPLIST_P)
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

你看吧每个狗蛋的层高的真的看情绪。


/**
 * 初始化跳跃表
 * @return
 */
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;
    // 初始化跳跃表内存
    zsl = zmalloc(sizeof(*zsl));
    // 默认一层
    zsl->level = 1;
    // 长度默认 0
    zsl->length = 0;
    // 初始化默认头节点
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    // 默认跳跃表为 64 层
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    // 后退指针
    zsl->header->backward = NULL;
    // 尾指针
    zsl->tail = NULL;
    return zsl;
}

/** 插入跳跃表节点
 *
 * @param zsl 治理跳跃表
 * @param score 分值
 * @param ele 字符串
 * @return
 */
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    serverAssert(!isnan(score));
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        // 有下节点 且 下个节点小于以后的分值 且 (如果节点分值雷同的状况下 比拟 key 的字典)
        while (x->level[i].forward &&
                (x->level[i].forward->score < score ||
                    (x->level[i].forward->score == score &&
                    sdscmp(x->level[i].forward->ele,ele) < 0)))
        {
            // 保留每个层的步长
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        // 记录每个前节点
        update[i] = x;
    }

    // update[i] 记录每个层的前节点
    // rank[i] 记录每个层的须要更新的步长

    // 初始化须要插入节点的层高
    level = zslRandomLevel();
    // 如果插入的节点层高 大于 跳跃表的层高
    if (level > zsl->level) {
        // 须要将多出的层高
        for (i = zsl->level; i < level; i++) {rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }
        zsl->level = level;
    }

    // 创立须要插入跳跃表的节点
    x = zslCreateNode(level,score,ele);
    for (i = 0; i < level; i++) {
        // 每一层为有序链表 参照插入链表的做法
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        // 更新步长
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }
    // 因为插入一个节点 须要每层的 span 都须要 +1
    for (i = level; i < zsl->level; i++) {update[i]->level[i].span++;
    }
    // 每个节点的 后退指针都指向 第一层的 前一个节点 如果插入的节点不是头节点
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    // 如果插入的节点前面有节点
    if (x->level[0].forward)
        // 则前面节点的后退指针指向本人
        x->level[0].forward->backward = x;
    else
        // 如果没有节点 则 插入的节点为最初一个节点 尾指针指向本人
        zsl->tail = x;
    // 减少跳跃表的长度 因为插入一个节点
    zsl->length++;
    return x;
}

当初看不懂具体代码实现没关系，因为本篇文章没打算让你看懂具体实现，具体代码能够本人下载 redis 5.0 版本里 t_zset.c 文件或者能够购买《Redis5 设计与源码剖析》陈雷编著（强烈推荐后者）。

如果你当前成为面试官，问他人有序汇合的底层实现是什么？
如果那个人说是跳跃表。
请你杠回去，有序汇合底层实现应用 跳跃表 和压缩列表 依据参数配置 zset-max-ziplust-entris 和zset-max-ziplist-value决定

 /* Lookup the key and create the sorted set if does not exist. */
    zobj = lookupKeyWrite(c->db,key);
    if (zobj == NULL) {if (xx) goto reply_to_client; /* No key + XX option: nothing to do. */
        if (server.zset_max_ziplist_entries == 0 ||
            server.zset_max_ziplist_value < sdslen(c->argv[scoreidx+1]->ptr))
        {zobj = createZsetObject();
        } else {zobj = createZsetZiplistObject();
        }
        dbAdd(c->db,key,zobj);
    }

毕竟面试官都是杠精

文章如果有形容谬误的中央，恳请留言改正。

正文完

redis

发表至： redis

2020-08-23

0

关于redis:Redis的底层类型之string

关于redis:Redis系列之初识Redis

关于redis:windows下安装Redis-5x版本

关于redis:故障分析-Redis-Cluster-分片内存异常使用不均问题诊断

关于后端:SSM系列教材-一-SpringSping-MVC-Mybatis-三大框架整合详细步骤

关于redis:带你redis从入门到不会系列了解跳跃表只看这篇大概不够

前言

有序汇合

跳跃表

剖析源码

构造体

跳跃表的根本知识点

源码剖析

zslRandomLevel

zslCreate

zslInsert

最初

站内搜索