skiplist - 跳表

article/2025/8/7 21:57:27

一 前言

跳表(skiplist、跳跃表) 是一个很优秀的数据结构，比如用于 Redis、levelDB等出名的开源项目上。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。

它的结构特点在名称能很好的体现出来，就像兔子一样，蹦蹦跳跳。可以结合下面的图有个初步的印象。

在这里插入图片描述

是不是看起来很形象了，接下来看看 Redis 是怎么实现跳表。

二 源码解读

本文讲解的版本为 Redis 6.0 ，可以在 server.h 头文件中找到对 skiplist 结构的定义。在 Redis 中，目前使用到跳表的只有 有序集合(zset)。

定义结构体处有段注释，也指明了跳表在 Redis 中的使用范围了。

ZSETs use a specialized version of Skiplists

// 有序集合的结构体
typedef struct zset {dict *dict;  // 哈希表是一种实现方式。zskiplist *zsl; // 本文主题 跳表 实现方式。
} zset;// 跳表结构体
typedef struct zskiplist {struct zskiplistNode *header, *tail;  // zskiplistNode 跳表节点, *header, *tail 头尾指针 unsigned long length;  // 节点的数量int level; // 最大层数
} zskiplist;// 跳表节点结构体
typedef struct zskiplistNode {sds ele;  // 成员对象double score;  // 分值   作为索引struct zskiplistNode *backward;   // 后退指针// 节点层结构 数组struct zskiplistLevel {struct zskiplistNode *forward;  // 前进指针unsigned long span; // 该层向前跨越的节点数量} level[];
} zskiplistNode;

看完上面的注视想必大家脑海中也构建出一张图了，它应该是长的和下图差不。
在这里插入图片描述
比如现在需要查找元素 56。

若是普通的链表就需要遍历整个链表，直到找到为止。如上图就需要查找 6 次。

但在跳表中，首先判断节点 56 是大于 34，则去下一层。 节点 56 < 节点 78，然后遍历 节点 34～ 节点 78中间。这时候只有一个节点 56。所以需要查找 3 次就可以找到了。

三 操作接口

操作结构的实现在 t_zset.c 文件中（不像 ziplist、quicklist 等是同名的一组文件）。

3.1 创建跳表


zskiplist *zslCreate(void) {int j;zskiplist *zsl; zsl = zmalloc(sizeof(*zsl)); //  申请内存zsl->level = 1; // 默认层级zsl->length = 0;  // 默认长度// 头指针创建， ZSKIPLIST_MAXLEVEL 最大层级为 32，可容纳  2^64   个节点。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;}//  上面遍历 32 次，生成下面这段结构。//   struct zskiplistLevel {//       struct zskiplistNode *forward;  // 前进指针//       unsigned long span; // 该层向前跨越的节点数量//    } level[];zsl->header->backward = NULL;zsl->tail = NULL;return zsl;}

3.2 节点插入


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];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;}// 调用 zslInsert 的地方需要在 hash 中判断当前插入的元素是否已经存在集合中。// 元素不能重复，但是元素的分数是可以重复的。// 生成随机值 代表需要插入的层级。 下面会讲解具体实现。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;// 插入新节点后需要更新前后节点对应的span值。 span 是到下一个节点的跨度 x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);update[i]->level[i].span = (rank[0] - rank[i]) + 1;}// 更新 其他level增加 span 值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;elsezsl->tail = x;zsl->length++;return x;
}// 这里需要单独说下这个随机值生成的规则。int zslRandomLevel(void) {int level = 1;// ZSKIPLIST_P = 0.25 ，虽然跳表的时间复杂度和二分查找一样，但是这里并不是 50% 的概率来控制一个节点是否放到下一层，而是 25%。 所以同一层节点下一层间的元素个数并不是一样的哦。// 还有的说法是这个值为 0.27更合适。 就是自然常数 e (2.7)。// random() 生成的随机数和 0xFFFF(16个1) 做 与运算。// 其实就是获取random()（32位）的前16位（或者说低位）。while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))level += 1;return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

3.3 节点删除


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;}// 找到分数和值都一样的元素。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; // 没找到
}// 删除的具体逻辑
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {int i;// 更新 每一层forward、span。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;}// 若删除的层级没有元素 层级减 1。while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)zsl->level--;// 元素长度减 1。zsl->length--;
}

源码解读就先到这里，更多的可以直接查看源码。

四 总结

跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。

跳表中的搜索、插入、删除操作的时间均为 O(logn)，最坏情况(（level = 1）时间复杂性为 O(n) 。相比之下，在一个有序数组或链表中进行插入/删除操作的时间为 O(n)，最坏情况下为 O(n)。

它采用随机技术决定链表中哪些节点应增加向前指针以及在该节点中应增加多少个指针。跳表结构的头节点需有足够的指针域，以满足可能构造最大级数的需要，而尾节点不需要指针域。

不好之处就是多层结构会占用额外的空间，是典型的空间换时间的操作。

五 其他文章

  • SDS-简单动态字符串
  • Redis - String 类型数据结构（SDS、Int）图文详解
  • ziplist-压缩列表
  • zipmap-压缩字典
  • quicklist-快速列表
  • skiplist-跳表
  • dict-字典
  • intset-整数数组
  • redis 通信协议讲解
  • listpack-紧凑列表
  • Redis7.0 新特性（超详细）
  • Redis 请慎用String类型
  • Redis 为什么使用单线程？
  • Redis AOF日志备份原理
  • Redis - ACID分析

http://chatgpt.dhexx.cn/article/UpQPlOqL.shtml

相关文章

Leveldb skiplist 实现及解析

Leveldb skiplist 实现及解析

skiplist 原理介绍 skiplist 由William Pugh 在论文Skip Lists: A Probabilistic Alternative to Balanced Trees 中提出的一种数据结构，skiplist 是一种随机化存储的多层线性链表结构，插入，查找，删除的都是对数级别的时间复杂度。skiplist 和平衡树有相同的时间复杂度，但…
阅读更多...
跳表SkipList介绍与实现

跳表SkipList介绍与实现

目录 一.跳表介绍 二.实现思路 &#xff08;一&#xff09;.结点结构 &#xff08;二&#xff09;.检索 &#xff08;三&#xff09;.插入 &#xff08;四&#xff09;.删除 三.实现代码 一.跳表介绍 跳表是一种随机化数据结构&#xff0c;主要用于快速检索数据。实质上…
阅读更多...
SkipList(跳表)

SkipList(跳表)

SkipList(跳表) 文章目录 SkipList(跳表)参考前言跳表的原理跳表的插入和删除插入操作删除操作 跳表的时间空间复杂度分析时间复杂度空间复杂度 调表的基本操作插入数据删除数据 Go 实现小结 参考 https://juejin.cn/post/6844903955831619597#heading-2https://blog.csdn.net…
阅读更多...
每日一博 - 如何理解跳表(SkipList)

每日一博 - 如何理解跳表(SkipList)

文章目录 什么是跳跃表SkipList跳表关键字Why Skip ListCode跳表-查询跳表-删除跳表-插入 小结完整Code 什么是跳跃表SkipList 跳跃表(简称跳表)由美国计算机科学家William Pugh于1989年发明 论文&#xff1a; Skip lists: a probabilistic alternative to balanced trees 跳…
阅读更多...
Skiplist（跳表）实现

Skiplist（跳表）实现

前言&#xff1a;跳表本质是一种查找结构&#xff0c;相较于AVL树、红黑树、哈希表&#xff0c;实现起来要更加简单&#xff0c;而且效率也不差。 一.Skiplist概念 跳表本质也是一种查找结构&#xff0c;用于解决算法中的查找问题&#xff0c;跟平衡搜索树&#xff08;AVL树、红…
阅读更多...
跳表(SkipList)设计与实现(java)

跳表(SkipList)设计与实现(java)

微信搜一搜「bigsai」关注这个有趣的程序员&#xff0c;一起做个朋友 新人原创公众号&#xff0c;求支持一下&#xff01;你的点赞三连肯定对我至关重要&#xff01; 文章已收录在 我的Github bigsai-algorithm 欢迎star 前言 跳表是面试常问的一种数据结构&#xff0c;它在很…
阅读更多...
SkipList和java中ConcurrentSkipListMap的实现

SkipList和java中ConcurrentSkipListMap的实现

文章目录 简介SkipListConcurrentSkipListMapSkipList的实现concurrent的实现 总结 SkipList和java中ConcurrentSkipListMap的实现 简介 一开始听说SkipList我是一脸懵逼的&#xff0c;啥&#xff1f;还有SkipList&#xff1f;这个是什么玩意。 后面经过我的不断搜索和学习&a…
阅读更多...
跳表（SkipList）及ConcurrentSkipListMap源码解析

跳表（SkipList）及ConcurrentSkipListMap源码解析

二分查找和AVL树查找 二分查找要求元素可以随机访问&#xff0c;所以决定了需要把元素存储在连续内存。这样查找确实很快&#xff0c;但是插入和删除元素的时候&#xff0c;为了保证元素的有序性&#xff0c;就需要大量的移动元素了。 如果需要的是一个能够进行二分查找&#…
阅读更多...
Redis数据结构之——跳表skiplist

Redis数据结构之——跳表skiplist

写在前面 以下内容是基于Redis 6.2.6 版本整理总结 一、跳表&#xff08;skiplist&#xff09; 如何理解跳表&#xff1f;在了解跳表之前&#xff0c;我们先从普通链表开始&#xff0c;一点点揭开跳表的神秘面纱~ 首先&#xff0c;普通单链表来说&#xff0c;即使链表是有序…
阅读更多...
redis中ziplist，skiplist

redis中ziplist，skiplist

ziplist压缩表 ziplist主要是为了节约内存&#xff0c;他将元素存储在一块连续的内存空间中&#xff0c;这样在查询数据的时候也可以利用CPU的缓存访问数据&#xff0c;加快查询的效率 相较于数组而言。我们知道,数组要求每个元素的大小都相同,如果我们要存储不同长度的字符串…
阅读更多...
跳表-skiplist的简单实现

跳表-skiplist的简单实现

文章目录 1、什么是跳表-skiplist2、skiplist的效率如何保证&#xff1f;3、skiplist的实现4、skiplist跟平衡搜索树和哈希表的对比 1、什么是跳表-skiplist skiplist本质上也是一种查找结构&#xff0c;用于解决算法中的查找问题&#xff0c;跟平衡搜索树和哈希表的价值是一样…
阅读更多...
跳表:Skiplist原理介绍和优缺点

跳表:Skiplist原理介绍和优缺点

skiplist介绍 不要求上下相邻两层链表之间的节点个数有严格的对应关系&#xff0c;而是为每个节点随机出一个层数(level)。比如&#xff0c;一个节点随机出的层数是3&#xff0c;那么就把它链入到第1层到第3层这三层链表中。为了表达清楚&#xff0c;下图展示了如何通过一步步的…
阅读更多...
skiplist 跳跃表详解及其编程实现

skiplist 跳跃表详解及其编程实现

skiplist介绍 跳表(skip List)是一种随机化的数据结构&#xff0c;基于并联的链表&#xff0c;实现简单&#xff0c;插入、删除、查找的复杂度均为O(logN)。跳表的具体定义&#xff0c; 请参考参考维基百科 点我&#xff0c;中文版。跳表是由William Pugh发明的&#xff0c;这…
阅读更多...
浅析SkipList跳跃表原理及代码实现

浅析SkipList跳跃表原理及代码实现

转载请注明&#xff1a;http://blog.csdn.net/ict2014/article/details/17394259 SkipList在leveldb以及lucence中都广为使用&#xff0c;是比较高效的数据结构。由于它的代码以及原理实现的简单性&#xff0c;更为人们所接受。我们首先看看SkipList的定义&#xff0c;为什么叫…
阅读更多...
跳表（skiplist）的理解

跳表（skiplist）的理解

听到跳表（skiplist）这个名字，既然是list，那么应该跟链表有关。 跳表是有序链表，但是我们知道，即使对于排过序的链表，我们对于查找还是需要进行通过链表的指针进行遍历的，时间复杂度很高依然是O(n)，这个显然是不能接受的。是否可以像数组那样，通过二分法进行查找呢，但…
阅读更多...
SkipList详解

SkipList详解

本文参考&#xff1a;《大数据日知录》 概念 SkipList是一种用来代替平衡树的数据结构。 虽然在最坏的情况下SkipList的效率要低于平衡树&#xff0c;但是大多数情况下效率仍然非常高&#xff0c;其插入、删除、查找的时间复杂度都是O(log(N))。 除了高效外&#xff0c;其实现…
阅读更多...
跳表（skipList）

跳表（skipList）

一、为何有skipList这种数据结构的出现 我们知道二分查找算法之所以能达到 O(logn) 这样高效的一个重要原因在于它所依赖的数据结构是数组&#xff0c;数组支持随机访问一个元素&#xff0c;通过下标很容易定位到中间元素。而链表是不支持随机访问的&#xff0c;只能从头到尾依…
阅读更多...
跳表 skiplist 简介

跳表 skiplist 简介

跳表 skiplist 跳表 (Skip List) 是由 William Pugh 在 1990 年发表的文章 Skip Lists: A Probabilistic Alternative toBalanced Trees 中描述的一种查找数据结构&#xff0c;支持对数据的快速查找&#xff0c;插入和删除。 对于 AVL 树、红黑树等平衡树&#xff0c;在插入过…
阅读更多...
SkipList(跳跃表)详解

SkipList(跳跃表)详解

Introduction: skiplist本质上也是一种查找结构&#xff0c;用于解决算法中的查找问题&#xff08;Searching&#xff09;&#xff0c;即根据给定的key&#xff0c;快速查到它所在的位置&#xff08;或者对应的value&#xff09; 一般用于解决查找问题的数据结构分为两个大类…
阅读更多...
docker中国镜像

docker中国镜像

一,如果是像redis,mysql等官方的镜像,直接配置阿里云的镜像就可以 1,注册阿里云账号,并登录 2,打开这个网址 https://cr.console.aliyun.com/cn-hangzhou/instances/mirrors 3,页面上会教怎么设置,如下面的截图 二,如果是私有仓库的镜像 非常感谢原作者:https://www.jiansh…
阅读更多...
推荐文章

Copyright @ 2022~2023