数据结构之跳跃表
跳跃表
跳跃表(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 …...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
鸿蒙(HarmonyOS5)实现跳一跳小游戏
下面我将介绍如何使用鸿蒙的ArkUI框架,实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...

作为点的对象CenterNet论文阅读
摘要 检测器将图像中的物体表示为轴对齐的边界框。大多数成功的目标检测方法都会枚举几乎完整的潜在目标位置列表,并对每一个位置进行分类。这种做法既浪费又低效,并且需要额外的后处理。在本文中,我们采取了不同的方法。我们将物体建模为单…...
Shell 解释器 bash 和 dash 区别
bash 和 dash 都是 Unix/Linux 系统中的 Shell 解释器,但它们在功能、语法和性能上有显著区别。以下是它们的详细对比: 1. 基本区别 特性bash (Bourne-Again SHell)dash (Debian Almquist SHell)来源G…...
Vue3学习(接口,泛型,自定义类型,v-for,props)
一,前言 继续学习 二,TS接口泛型自定义类型 1.接口 TypeScript 接口(Interface)是一种定义对象形状的强大工具,它可以描述对象必须包含的属性、方法和它们的类型。接口不会被编译成 JavaScript 代码,仅…...
基于Java的离散数学题库系统设计与实现:附完整源码与论文
JAVASQL离散数学题库管理系统 一、系统概述 本系统采用Java Swing开发桌面应用,结合SQL Server数据库实现离散数学题库的高效管理。系统支持题型分类(选择题、填空题、判断题等)、难度分级、知识点关联,并提供智能组卷、在线测试…...