当前位置: 首页 > news >正文

数据结构之跳跃表

跳跃表

跳跃表(skiplist)是一种随机化的数据, 由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出, 跳跃表以有序的方式在层次化的链表中保存元素, 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成, 并且比起平衡树来说, 跳跃表的实现要简单直观得多。

image
从图中可以看到, 跳跃表主要由以下部分构成:

  • 表头(head):负责维护跳跃表的节点指针。
  • 跳跃表节点:保存着元素值,以及多个层。
  • 层:保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针,为了提高查找的效率,程序总是从高层先开始访问,然后随着元素值范围的缩小,慢慢降低层次。
  • 表尾:全部由 NULL 组成,表示跳跃表的末尾。

因为跳跃表的定义可以在任何一本算法或数据结构的书中找到,所以本章不介绍跳跃表的具体实现方式或者具体的算法, 而只介绍跳跃表在 Redis 的应用、核心数据结构和 API 。

跳跃表的实现

为了满足自身的功能需要, Redis 基于 William Pugh 论文中描述的跳跃表进行了以下修改:

  1. 允许重复的 score 值:多个不同的 member 的 score 值可以相同。
  2. 进行对比操作时,不仅要检查 score 值,还要检查 member :当 score 值可以重复时,单靠 score 值无法判断一个元素的身份,所以需要连 member 域都一并检查才行。
  3. 每个节点都带有一个高度为 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 论文中描述的跳跃表进行了修改,包括:
    1. score 值可重复。
    2. 对比一个元素需要同时检查它的 score 和 memeber 。
    3. 每个节点带有高度为 1 层的后退指针,用于从表尾方向向表头方向迭代。

为啥 redis 使用 跳表 (skiplist) 而不是使用 red-black?

  1. 实现简单。
  2. 区间查找快。跳表可以做到O(logn)的时间复杂度定位区间的起点,然后在原始链表中顺序往后遍历就可以了。
  3. 并发环境优势。红黑树在插入和删除的时候可能需要做一些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%”时,这通常与数据的统计分布或置信区间有关,而不是直接关于数据类型的定义。 导入数据的时候需要定义数据类型,那么根据提供的数据,来定义,有时候&#xff…...

Python进阶之-上下文管理器

✨前言: 🌟什么是上下文管理器? 在Python中,上下文管理器是支持with语句的对象,用于为代码块提供设置及清理代码。上下文管理器广泛应用于资源管理场景,例如文件操作、网络连接、数据库会话等&#xff0c…...

什么年代了,还在拿考勤说事

最近,看到了某公司的一项考勤规定:自然月内,事假累计超过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 …...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

微信小程序之bind和catch

这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦&#xff0…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...