Redis源码解析-skiplist跳跃表

最新推荐文章于 2024-04-12 16:50:01 发布
最新推荐文章于 2024-04-12 16:50:01 发布
阅读量1.6k 收藏
点赞数 2
分类专栏： Redis C语言 后端开发
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/matrixZCL/article/details/111877519
版权

前言

跳跃表是一种有序数据结构，查找和插入操作的平均时间复杂度都是O(log n)。与常用的自平衡搜索树相比，例如红黑树，跳跃表通过多层链表实现，其结构简单易于实现，其查询删除效率通常堪比红黑树。本篇文章会对跳跃表简要说明，并重点分析Redis跳跃表核心源码

其他文章：Redis简单动态字符串SDS源码解析

正文

1. 跳跃表

跳跃表是通过多层有序链表实现的。如下图的有序链表，假设需要查找等于7的元素，必须从头结点（元素为1）依次遍历链表，共经过7次查询比较，找出目标结点。也就是其查询时间复杂度为O(1)，删除同理

假如给单个有序链表加索引会怎么样？

如下图，基于单个有序列表，又添加了几层有序列表，可以理解为索引。那么其查询过程为

  • 第一次，1<7,next=9>7，降级
  • 第二次，1.next=5<7，5.next=9>7,降级
  • 第三次，5.next=7，查找到目标结果

可以看到，只需经过四次查询，三次比较即可找出结果，一个设计良好的跳跃表，其时间复杂度能达到O(logn)。这就是跳跃表，道理就是这么简单。那么下面会详细介绍Redis跳跃表的具体实现，其细节还是比较多的

2. Redis跳跃表数据结构

2.1 跳跃表整体结构

Redis跳跃表的结构如下图，对照着示意图，先对其结构进行简要说明，再分析源码

  • header： 指向表头的指针
  • tail：指向表尾的指针
  • level：层数最大的结点，不包含表头，在图中也就是包含后三个结点
  • BW：backward，后退指针，指向后一个结点
  • score：分值，就是我们用ZADD命令插入时设置的score，1.0，2.0…等
  • sds指针：对应图中o1,o2…，其数据结构为sds，可参考前言

2.2 跳跃表结点源码

zskiplistNode为跳跃表的结点，定义在server.h文件中，其中

  • ele为sds类型字符串，其作用是存储数据
  • level为层级，定义为数组，其中每个元素包含前进指针，和span。注意：层级不包含头节点，头节点再Redis5.0创建跳跃表时会初始化为最大值，也就是64
  • span为当前层当前结点与下一个结点之前跨过的元素个数，span的目的是为了计算rank（排位），也就是第几个元素。例如前面说查询元素7，那么怎么知道7是第几个元素？，每个层结点维护了一个span变量，所以即使跨元素查找，也能通过计算得出rank
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;
---------------------------------------------------
//在头文件引入sds数据结构  
typedef char *sds;
2.3 跳跃表结构源码

有了节点的定义，需要一个结构管理这些节点，Redis定义zskiplist跳跃表结构。如下图，就像上面说明那样，其维护了两个指针，分别指向表头，表尾；还有跳表的长度和层高

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

3. 创建跳跃表

3.1 创建跳跃表结构

可以看到，创建跳跃表结构分为以下几个步骤

  • 声明结构指针，分配空间
  • 初始化结构层级为1（跳表最大层级），长度初始化为0（跳表长度）
  • 创建表头节点，初始化表头层级为ZSKIPLIST_MAXLEVEL=64
  • 将表头的每层的forward指针初始化为null，将span初始化为0
  • 最后将后退指针，以及表尾指针初始化为null
/* Create a new skiplist. */
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;

    zsl = zmalloc(sizeof(*zsl));
    zsl->level = 1;
    zsl->length = 0;
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    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;
}
3.2 zslCreateNode创建节点方法

该方法会创建一个指定层级，指定分数，指定字符串元素的节点

  • 可以看到首先声明zn指针，并指向一块分配好的内存块，通过malloc函数分配，其内存块大小为在zn指针基础上，偏量为移层数 x 每层大小。然后给其元素赋值并返回指针
/* Create a skiplist node with the specified number of levels.
 * The SDS string 'ele' is referenced by the node after the call. */
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
    zskiplistNode *zn =
        zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    zn->score = score;
    zn->ele = ele;
    return zn;
}

4. 插入节点

我们知道在单链表中，插入一个结点n需要维护前一个结点信息，以便改变指针实现插入。Redis跳表同样的道理，不过它维护的是一个长度为64的数组update[]，还需要维护一个rank[]数组用来计算排位。其源码如下

从zslInsert方法看起，它传入zskiplist结构指针，代表向哪个跳跃表插入元素，需要插入元素的分数，和字符串值。首先声明两个数组就是上面说的。可以看到首先定义一个zskiplistNode指针类型x，从头部依次遍历

4.1 查找要插入的位置
  • 意思为最高层开始，每次循环降低一层
  • 重点关注其中的while循环，如果forward指向的下个元素分数小于等于当前分数，则向后继续向后遍历
  • while循环同时还会计算排位，可以看到rank排位是通过当前层的span累加得出
  • 最后赋值update
for (i = zsl->level-1; i >= 0; i--) {
        /* store rank that is crossed to reach the insert position */
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        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;
    }
4.2 生成随机层高

这里的算法类似幂次定律，层高概率为，越高的层概率越小。其中ZSKIPLIST_P=0.25。整个算法过程为

  • 生成随机数取低16位，与0.25 x 0xffff比较，来判断是否level+1。
/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
4.3 调整最大层级

当插入的结点level大于跳表最大层高，需要更新level

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;
    }
4.4 插入节点

其方式跟单链表插入大同小异

  • 把x当前层的forward指针指向update的当前层下一个结点
  • 再将update当前层的forward指向x
  • 最后是更新span的值
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;

    /* update span covered by update[i] as x is inserted here */
    x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
    update[i]->level[i].span = (rank[0] - rank[i]) + 1;
 }
4.5 收尾工作
  • 更新上层span值
  • 调整backward指针，update[0]相当于第一层，用来存储backward指针
/* increment span for untouched levels */
    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++;

完整的插入代码如下

//插入整体代码
/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

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--) {
        /* store rank that is crossed to reach the insert position */
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        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;
    }
    /* we assume the element is not already inside, since we allow duplicated
     * scores, reinserting the same element should never happen since the
     * caller of zslInsert() should test in the hash table if the element is
     * already inside or not. */
    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;

        /* update span covered by update[i] as x is inserted here */
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }

    /* increment span for untouched levels */
    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;
}

5. 删除结点

根据分值来删除结点的代码如下

  • 首先第一个for跟创建结点前的查找逻辑相似
  • 然后比较分值，如果相同则通过zslDeleteNode删除结点
int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    int i;

    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        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)))
        {
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    /* We may have multiple elements with the same score, what we need
     * is to find the element with both the right score and object. */
    x = x->level[0].forward;
    if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
        zslDeleteNode(zsl, x, update);
        if (!node)
            zslFreeNode(x);
        else
            *node = x;
        return 1;
    }
    return 0; /* not found */
}

zslDeleteNode为真正删除结点的函数，源代码如下

  • 删除结点前，首先更新前一个结点每层的的span
  • 然后将每层的前一个结点的forward指向被删除结点只想的结点（基础的链表删除元素操作）
  • else语句说明update[i]大于当前层高，因此删除结点需要更新当前层span值，减1
  • 最后是调整被删除元素下一个元素的backward指针
/* Internal function used by zslDelete, zslDeleteByScore and zslDeleteByRank */
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
    int i;
    for (i = 0; i < zsl->level; i++) {
        if (update[i]->level[i].forward == x) {
            update[i]->level[i].span += x->level[i].span - 1;
            update[i]->level[i].forward = x->level[i].forward;
        } else {
            update[i]->level[i].span -= 1;
        }
    }
    if (x->level[0].forward) {
        x->level[0].forward->backward = x->backward;
    } else {
        zsl->tail = x->backward;
    }
    while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
        zsl->level--;
    zsl->length--;
}

总结

跳跃表是有序集合的实现方式之一，由zskiplist，zskiplistNode两个构成，zskiplist可以看作是一种管理跳表的数据结构，而zskiplistNode为跳跃表结点的数据结构。其更多的API源代码实现，可以参考t_zset.c源文件

图文详解Redis跳跃表skiplist
weixin_38582659的博客
05-02 738
Redis跳跃表图文详解 列表 数组实现(ArrayList) 链表实现(LinkedList) 关于有序列表的思考 什么是跳跃表？ 图解跳跃表 跳跃表节点 结构体 图解跳跃表节点 跳跃表 结构体 图解跳跃表 层高算法 上帝也掷骰子 跳表常用操作过程解析 查询 插入 删除
Redis面试系列：跳跃表skiplist实现原理是什么？源码解析（三）
Oooo_mumuxi的博客
05-06 429
前言 之前总是从网上去找跳跃表的实现原理，发现都很难理解，下面我会通过源码和画图分析让你一目了然。 一、skiplist 前面的文章说到了，zset的实现就有skiplist，我们来看一下zset的结构体： typedef struct zset { dict *dict; //字典存放value,以value为key zskiplist *zsl; } zset; 你是否有疑...
Redis_skiplist源码阅读与分析
weixin_45704279的博客
05-12 465
​ 跳跃表，是一种独特的数据结构，它依靠链表，实现了快速的插入，删除。又根据它独特的设计实现了平均O(logN)复杂度下的查询。 并且它的结构相对红黑树来说十分简单。
redis-skipList 源码解析
Knight-ZXW的博客
07-18 459
跳跃表SkipList是在有序链表的基础上进行了扩展，解决了有序链表结构查找特定值困难的问题，查找特定值的时间复杂度为O(logn)，他是一种可以代替平衡树的数据结构。具体的介绍可以参考这篇博文跳跃表的数据结构Redis的跳跃表由节点 server.h/zskiplistNode 和表 server.h/zskiplist 实现. “`c /* ZSETs use a specializ
redis源码解析：skiplist
weixin_34764432的博客
03-11 145
最近学习Redis源码，存储结构相关的知识，在这边总结一下一些重要的知识点。如果有说的不对的地方，希望大家帮忙指正。 Redis的基本数据结构 Redis是一种key-value的数据库存储系统，简称为k-v。key-value形式的存储结构，一般会使用红黑树或者hash表来存储。红黑树的时间复杂度为O(logn)，hash表则是O(1)。Redis内部是有维护一个hash表的，说到hash表，肯定会第一时间想到有相应的hash算法，Redis中的key如果是字符串的话，一定需要通过hash算法将字符串h
redis源码解析-跳表-skiplist(6.2.3版本)
qazwsxwtc的专栏
08-07 239
跳表，是redis中的一中链表数据结构，能够提高链表的查询效率。使用跳表，可以避免遍历一些不必要的节点，从而提高了查询，删除，插入的效率。 1，跳表结构体 typedef struct zskiplistNode { sds ele;//节点元素，字符串 double score;//元素分数，在跳表中按照该分数排放 struct zskiplistNode *backward;//上一个节点 struct zskiplistLevel { struct
redis源码剖析-skiplist
qq_30108661的博客
01-31 188
试想一个业务场景：游戏需要实现一个实时更新的排行榜应该如何实现 首先想到使用有序的双端链表， 因为插入的时间复杂度为O(1) 但是定位的平均时间复杂度为O(N) 当频繁更新排行榜的时候效率比较低 有没有一个结构 能够满足快速定位到相应的位置并插入？跳跃表就能满足这个需求 跳跃表（skiplist） 跳跃表的思想是给数据结点建立索引 从最高层索引根据关键字查找 如果当前结点<关键字 且下一节点>关键字 则降层继续从当前结点开始查找 一直到查找到结点 或 降到第0层 算法平均复杂度...
Redis_Source_code:Redis源码分析-redis source code
03-25
-有序集合：元素有序且不重复，使用跳跃表（Skip List）实现，支持范围查询。 2. Redis的核心组件： - Redis服务器：处理客户端连接，解析命令，执行操作并返回结果。 - RDB持久化：定期将内存中的数据快照到...
redis3源码及解析
01-03
Redis源码解析是一项深入学习数据库系统、内存管理以及并发控制等核心计算机科学概念的宝贵资源。 首先，我们来看Redis中的核心数据结构。Redis支持多种数据类型，包括字符串（String）、哈希表（Hash）、列表...
Redis内部数据结构详解之跳跃表(skiplist)
热门推荐
fmt.Println(
12-15 2万+
一、跳跃表简介 跳跃表是一种随机化数据结构，基于并联的链表，其效率可以比拟平衡二叉树，查找、删除、插入等操作都可以在对数期望时间内完成，对比平衡树，跳跃表的实现要简单直观很多。 以下是一个跳跃表的例图(来自维基百科)： 从图中可以看出跳跃表主要有以下几个部分构成： 1、  表头head：负责维护跳跃表的节点指针 2、  节点node：实际保存元素值，每个节点有一层或多层 3
Redis源码剖析之跳表(skiplist)_跳表 sdscmp
最新发布
2401_84254279的博客
04-12 361
解视频，并且后续会持续更新**
Redis源码剖析——skiplist的实现
ProgrammingLearner的博客
05-12 566
跳跃表skiplist 跳跃表是一种有序的数据结构，它通过用空间换时间，在每个节点中维持多个指向其他节点的指针，从而达到快速访问的目的。跳跃表插入、删除的平均复杂度为O（logN），最坏为O（N），可以和红黑树相媲美，但是在实现起来，比红黑树简单很多。 Redis使用跳跃表来实现有序集合对象 基本结构 // 跳跃表节点 typedef struct zskiplistNode { ...
【redis源码分析】跳跃表--skiplist
raiet
05-22 827
跳跃表实际上可以看作是一种
源码分析redis的有序集合，学习skiplist跳跃表数据结构
青春不谢的专栏
05-03 789
最近在看redis源码，看到跳跃表的插入操作时感觉很头大，网上各种文章都只是在进行一个原理性的分析，唯独这篇文章一行一行代码地讲解，非常仔细和透彻。希望能帮助正在阅读redis源码的你！文章地址源码分析redis的有序集合，学习skiplist跳跃表数据结构
Redis 源码分析跳跃表（skiplist）
CRMEB小程序商城的博客
02-21 850
跳跃表特点 1、按照 score 来排序，如果 score 相等，那么则按照 ele 来排序。 2、平均查询时间复杂度 O(logn)。 跳跃表实现 跳跃表是由 server.h/zskiplistNode 和 server.h/zskiplist 两个结构定义其中 zskiplistNode 结构用于订阅跳跃表的节点，而 zskiplist 结构用于保存跳跃表相关的信息，比如节点的数量，以及想表头节点和表尾节点的指针等 跳跃表实现 server.h/zskiplistNode 结构定义： /* ZSETs
Redis源码解读（八）——基本类型—skiplist
yh88623131的博客
05-16 406
skiplist设计与实现
redis源码分析——5、dict实现
繁华落尽梦一场
10-28 302
dics是一种常用的数据结构，而C语言没有提供内置类型，本文一起看看redis中dict的实现 1. 怎么样自己实现一个dict ​ 不像C++、java等高级语言内置了map，C语言并没有提供dict库，所以如果想使用dict就需要自己实现。那么实现一个dict有方法呢？ 数组法 这也是最容易实现的一种方法，简单说就是开辟一个长度为N的大数组（通常N是一个质数），然后通过一个哈希函数计算key的哈希值d，然后用d%N得到key对于的数组下边。设想一下，如果数组开的足够大，而且哈希函数足够散列，我们.
Redis-跳跃列表原理源码分析
哆啦A梦
01-17 507
1、Redis 的 zset 是一个复合结构，结构特点： 1）需要通过hash 结构来存储 value 和 score 的对应关系 2）要支持按照 score 来排序 3）还要按照指定 score 的范围来获取 value 列表的 4）要实现上诉的功能的结构，作者想到了跳跃列表 5）zset的结构：通过一个hash字典加跳跃列表skiplist   2、跳跃列表结构 1）基本结...
redis底层数据结构--skiplist
xjk201的博客
05-17 308
认识跳表 跳表的提出 跳表首先由William Pugh在其1990年的论文《Skip lists: A probabilistic alternative to balanced trees》中提出。由该论文的题目可以知道两点： 跳表是概率型数据结构。 跳表是用来替代平衡树的数据结构。准确来说，是用来替代自平衡二叉查找树（self-balancing BST）的结构。 看官可能会觉得这两点与之前文章中讲过的布隆过滤器有些相似，但实际上它们的原理和用途还是很不相同的。 由二叉树回归链表 考虑在有
深入解析Redis-3.0.0源码及其系统开源特性
- 散列、集合和有序集合等也有类似的高效实现机制，散列使用了ziplist和hashtable的组合，集合使用了intset或者hashtable，有序集合则使用了跳跃表（skiplist）和hashmap的结合。 2. 网络和通信模块 - Redis作为...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值