数据结构之跳跃表
跳跃表
跳跃表(skiplist)是一种随机化的数据, 由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出, 跳跃表以有序的方式在层次化的链表中保存元素, 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成, 并且比起平衡树来说, 跳跃表的实现要简单直观得多。
从图中可以看到, 跳跃表主要由以下部分构成:
- 表头(head):负责维护跳跃表的节点指针。
- 跳跃表节点:保存着元素值,以及多个层。
- 层:保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针,为了提高查找的效率,程序总是从高层先开始访问,然后随着元素值范围的缩小,慢慢降低层次。
- 表尾:全部由 NULL 组成,表示跳跃表的末尾。
因为跳跃表的定义可以在任何一本算法或数据结构的书中找到,所以本章不介绍跳跃表的具体实现方式或者具体的算法, 而只介绍跳跃表在 Redis 的应用、核心数据结构和 API 。
跳跃表的实现
为了满足自身的功能需要, Redis 基于 William Pugh 论文中描述的跳跃表进行了以下修改:
- 允许重复的 score 值:多个不同的 member 的 score 值可以相同。
- 进行对比操作时,不仅要检查 score 值,还要检查 member :当 score 值可以重复时,单靠 score 值无法判断一个元素的身份,所以需要连 member 域都一并检查才行。
- 每个节点都带有一个高度为 1 层的后退指针,用于从表尾方向向表头方向迭代:当执行 ZREVRANGE 或 ZREVRANGEBYSCORE 这类以逆序处理有序集的命令时,就会用到这个属性。
这个修改版的跳跃表由 redis.h/zskiplist 结构定义:
typedef struct zskiplist {// 头节点,尾节点struct zskiplistNode *header, *tail;// 节点数量unsigned long length;// 目前表内节点的最大层数int level;} zskiplist;
跳跃表的节点由 redis.h/zskiplistNode 定义:
typedef struct zskiplistNode {// member 对象robj *obj;// 分值double score;// 后退指针struct zskiplistNode *backward;// 层struct zskiplistLevel {// 前进指针struct zskiplistNode *forward;// 这个层跨越的节点数量unsigned int span;} level[];} zskiplistNode;
小结
- 跳跃表是一种随机化数据结构,查找、添加、删除操作都可以在对数期望时间下完成。
- 跳跃表目前在 Redis 的唯一作用,就是作为有序集类型的底层数据结构(之一,另一个构成有序集的结构是字典)。
- 为了满足自身的需求,Redis 基于 William Pugh 论文中描述的跳跃表进行了修改,包括:
- score 值可重复。
- 对比一个元素需要同时检查它的 score 和 memeber 。
- 每个节点带有高度为 1 层的后退指针,用于从表尾方向向表头方向迭代。
为啥 redis 使用 跳表 (skiplist) 而不是使用 red-black?
- 实现简单。
- 区间查找快。跳表可以做到O(logn)的时间复杂度定位区间的起点,然后在原始链表中顺序往后遍历就可以了。
- 并发环境优势。红黑树在插入和删除的时候可能需要做一些rebalance的操作,这样的操作可能会涉及到整个树的其他部分,而skiplist的操作显然更加局部性一些,需要锁住的节点更少,因此在这样的情况下性能好一些。
相关文章:

数据结构之跳跃表
跳跃表 跳跃表(skiplist)是一种随机化的数据, 由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出, 跳跃表以有序的方式在层次化的链表中保存元素, 效率和平衡树媲美 —— …...
搜维尔科技:动作捕捉解决方案:销售、服务、培训和支持
动作捕捉解决方案:销售、服务、培训和支持 搜维尔科技:动作捕捉解决方案:销售、服务、培训和支持l...

数据库管理-第184期 23ai:干掉MongoDB的不一定是另一个JSON数据库(20240507)
数据库管理184期 2024-05-07 数据库管理-第184期 23ai:干掉MongoDB的不一定是另一个JSON数据库(20240507)1 JSON需求2 关系型表设计3 JSON关系型二元性视图3 查询视图总结 数据库管理-第184期 23ai:干掉MongoDB的不一定是另一个JSON数据库(20…...

刷代码随想录有感(58):二叉树的最近公共祖先
题干: 代码: class Solution { public:TreeNode* traversal(TreeNode* root, TreeNode* p, TreeNode* q){if(root NULL)return NULL;if(root p || root q)return root;TreeNode* left traversal(root->left, p, q);TreeNode* right traversal(r…...

[开发|安卓] Android Studio 开发环境配置
Android Studio下载 Android Studio下载地址 下载SDK依赖 1.点击左上角菜单 2.选择工具 3.打开SDK管理中心 4.下载项目目标Android版本的SDK 配置安卓虚拟机 1.打开右上角的设备管理 2.选择合适的手机规格 3.下载并选择项目目标Android系统 4.点击完成配置 …...

开发 Chrome 浏览器插件入门
目录 前言 一,创建插件 1.创建一个新的目录 2.编写清单文件 二,高级清单文件 1.编写放置右窗口 2.常驻的后台JS或后台页面 3.event-pages 短周期使用 三,Chrome 扩展 API 函数 1.浏览器操作函数 2.内容脚本函数 3.后台脚本函数 4…...

在数字化转型的浪潮中,CBDB百数服务商如何破浪前行?
在信息化时代,传统咨询企业面临着数字化转型的挑战与机遇。如何利用数字化技术提升业务效率、增强客户黏性,成为了行业关注的焦点。云南析比迪彼企业管理有限公司(CBDB)作为云南地区的企业咨询服务提供商,率先与百数展…...

程序员的实用神器
在软件开发的海洋中,程序员的实用神器如同航海中的指南针,帮助他们导航、加速开发、优化代码质量,并最终抵达成功的彼岸。这些工具覆盖了从代码编写、版本控制到测试和部署的各个环节。然而,程序员们通常会有一套自己喜欢的工具集…...

spss 导入数据的时候 用于确定数据类型的值所在的百分比95%是什么意思,数据分析,医学数据分析
在SPSS中,当提及“数据类型的值所在的百分比95%”时,这通常与数据的统计分布或置信区间有关,而不是直接关于数据类型的定义。 导入数据的时候需要定义数据类型,那么根据提供的数据,来定义,有时候ÿ…...
Python进阶之-上下文管理器
✨前言: 🌟什么是上下文管理器? 在Python中,上下文管理器是支持with语句的对象,用于为代码块提供设置及清理代码。上下文管理器广泛应用于资源管理场景,例如文件操作、网络连接、数据库会话等,…...

什么年代了,还在拿考勤说事
最近,看到了某公司的一项考勤规定:自然月内,事假累计超过3次或者累计请假时间超过8小时的,不予审批,强制休假的按旷工处理。 真的想吐槽,什么年代了,还在拿考勤说事,这是什么公司、什…...

泰迪智能科技中职大数据实验室建设(职业院校大数据实验室建设指南)
职校大数据实验室是职校校园文化建设的重要部分,大数据实训室的建设方案应涵盖多个方面,包括硬件设施的配备、软件环境的搭建、课程资源的开发、师资力量的培养以及实践教学体系的完善等。 打造特色,对接生产 社会经济与产业的…...

Qt QThreadPool线程池
1.简介 QThreadPool类管理一个QThread集合。 QThreadPool管理和重新设计单个QThread对象,以帮助降低使用线程的程序中的线程创建成本。每个Qt应用程序都有一个全局QThreadPool对象,可以通过调用globalInstance来访问该对象。 要使用其中一个QThreadPool…...

无人机+三维建模:倾斜摄影技术详解
无人机倾斜摄影测量技术是一项高新技术,近年来在国际摄影测量领域得到了快速发展。这种技术通过从一个垂直和四个倾斜的五个不同视角同步采集影像,从而获取到丰富的建筑物顶面及侧视的高分辨率纹理。这种技术不仅能够真实地反映地物情况,还能…...

Window(Qt/Vs)软件添加版本信息
Window(Qt/Vs)软件添加版本信息 文章目录 Window(Qt/Vs)软件添加版本信息VS添加版本信息添加资源文件添加版本定义头自动更新版本添加批处理脚本设置生成事件 Qt添加版本信息添加资源文件文件信息修改自动更新版本 CMake添加版本信…...

工厂模式+策略模式完成多种登录模式的实现
前提 (简单工厂不属于设计模式,而是一种编程思想【抽象一层出来】)工厂方法模式、抽象工厂模式 以上都是为了解耦,如果考虑多个纬度(如需要同时考虑多种电器,多种品牌)则优先考虑抽象工厂。 …...

赋能企业数字化转型 - 易点易动固定资产系统与飞书实现协同管理
在当前瞬息万变的商业环境下,企业如何借助信息化手段提升管理效率,已经成为摆在各行各业面前的紧迫课题。作为企业数字化转型的重要一环,固定资产管理的信息化建设更是不容忽视。 易点易动作为国内领先的企业资产管理服务商,凭借其全方位的固定资产管理解决方案,助力众多企业实…...

Sectigo 通配符SSL证书的优势分析!
Sectigo 通配符证书是一种专为需要保护同一主域名下的多个子域名而设计的安全解决方案。以下是Sectigo通配符证书的主要优势和特点: 1. 域名灵活性:使用通配符(*)符号,一张Sectigo通配符证书即可覆盖一个主域名及其所有…...
nuxt2路由,以及重构以前项目,路由使用
Nuxt.js根据pages目录结构自动生成vue-router模块的路由配置。 配置生成的路由可在.nuxt文件下的router.js文件中查看到,如: export const routerOptions {mode: history,base: /,linkActiveClass: nuxt-link-active,linkExactActiveClass: nuxt-link…...
eureka报错:链接8761被拒绝
eureka报错:链接8761被拒绝 来龙去脉 在idea环境中运行没有问题 我的配置是: server: port: 8001 spring: application: name: registry-server eureka: instance: hostname: localhost client: fetch-registry: false register-with-eureka: false …...

RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...

UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...

【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...