3.30--Redis之常用数据结构--跳表之总结篇(总结篇)------加油呀

2023/12/1 9:01:10

跳表

跳表是在链表基础上改进过来的,实现了一种「多层」的有序链表,这样的好处是能快读定位数据

优势是能支持平均 O(logN) 复杂度的节点查找。

只有 Zset 对象的底层实现用到了跳表,zset 结构体里有两个数据结构:一个是跳表,一个是哈希表。

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

这样的好处是既能进行高效的范围查询,也能进行高效单点查询

下图展示了一个层级为 3 的跳表:
在这里插入图片描述
图中头节点有 L0~L2 三个头指针,分别指向了不同层级的节点,然后每个层级的节点都通过指针连接起来

Zset 对象要同时保存「元素」和「元素的权重」,对应到跳表节点结构里就是 SDS类型的 ele 变量和 double 类型的 score 变量。每个跳表节点都有一个后向指针,指向前一个节点,目的是为了方便从跳表的尾节点开始访问节点,这样倒序查找时很方便

zskiplistLevel 结构体类型的 level 数组:
level 数组中的每一个元素代表跳表的一层,比如 leve[0] 就表示第一层,leve[1] 就表示第二层。zskiplistLevel 结构体里定义了「指向下一个跳表节点的指针」和「跨度」,跨度用来记录两个节点之间的距离。

跨度实际上是为了计算这个节点在跳表中的排位

计算某个节点排位的时候,从头节点点到该结点的查询路径上,将沿途访问过的所有层的跨度累加起来,得到的结果就是目标节点在跳表中的排位

如图:
在这里插入图片描述
跳表节点查询过程

查找一个跳表节点的过程时,跳表会从头节点的最高层开始,逐一遍历每一层。在遍历某一层的跳表节点时,会用跳表节点中的 SDS 类型的元素和元素的权重来进行判断,共有两个判断条件:

1.如果当前节点的权重「小于」要查找的权重时,跳表就会访问该层上的下一个节点。
2.如果当前节点的权重「等于」要查找的权重时,并且当前节点的 SDS 类型数据「小于」要查找的数据时,跳表就会访问该层上的下一个节点。
3.如果上面两个条件都不满足,或者下一个节点为空时,跳表就会使用目前遍历到的节点的 level 数组里的下一层指针,然后沿着下一层指针继续查找,这就相当于跳到了下一层接着查找。

跳表节点层数设置

跳表的相邻两层的节点数量最理想的比例是 2:1,查找复杂度可以降低到 O(logN)。

那怎样才能维持相邻两层的节点数量的比例为 2 : 1 呢?

跳表在创建节点的时候,随机生成每个节点的层数

具体的做法是,跳表在创建节点时候,会生成范围为[0-1]的一个随机数,如果这个随机数小于 0.25(相当于概率 25%),那么层数就增加 1 层,然后继续生成下一个随机数,直到随机数的结果大于 0.25 结束,最终确定该节点的层数

在第 i 层中的元素按某个固定的概率 p(通常为 ½ 或 ¼ )出现在第 i + 1层中,产生越高的层数,概率越低
元素层数恰好等于 1 的概率为 1 – p
元素层数大于等于 2 的概率为 p,而元素层数恰好等于 2 的概率为 p * (1 – p)
元素层数大于等于 3 的概率为 p^2,而元素层数恰好等于 3 的概率为 p^2 * (1 – p)
元素层数大于等于 4 的概率为 p^3,而元素层数恰好等于 4 的概率为 p^3 * (1 – p)

一个元素的平均层数是 1 / (1 – p)

为什么用跳表而不用平衡树?

1.从内存占用上来比较,跳表比平衡树更灵活一些。平衡树每个节点包含 2 个指针(分别指向左右子树),而跳表每个节点包含的指针数目平均为 1/(1-p),具体取决于参数 p 的大小。如果像 Redis里的实现一样,取 p=1/4,那么平均每个节点包含 1.33 个指针,比平衡树更有优势。
2.在做范围查找的时候,跳表比平衡树操作要简单。在平衡树上,我们找到指定范围的小值之后,还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造,这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单,只需要在找到小值之后,对第 1 层链表进行若干步的遍历就可以实现。
3.从算法实现难度上来比较,跳表比平衡树要简单得多。平衡树的插入和删除操作可能引发子树的调整,逻辑复杂,而跳表的插入和删除只需要修改相邻节点的指针,操作简单又快速


http://www.jnnr.cn/a/369278.html

相关文章

FasterNet实战:使用FasterNet实现图像分类任务(二)

文章目录训练部分导入项目使用的库设置随机因子设置全局参数图像预处理与增强读取数据设置Loss设置模型设置优化器和学习率调整算法设置混合精度,DP多卡,EMA定义训练和验证函数训练函数验证函数调用训练和验证方法运行以及结果查看测试热力图可视化展示一…

【数据库管理】⑤归档日志Archive Log

1.日志归档的概述和用途 日志归档是指将数据库的归档日志文件保存到指定的位置,以便在需要时进行恢复和回滚操作。在Oracle数据库中,日志归档是一种重要的备份和恢复策略,可以保证数据库的数据完整性和可靠性。 日志归档的主要用途包括&#…

CVE-2020-1948 Apache dubbo远程命令执行漏洞

预备知识 Dubbo是阿里巴巴公司开源的一个高性能优秀的服务框架,使得应用可通过高性能的RPC实现服务的输出和输入功能,可以和Spring框架无缝集成。 RPC是远程过程调用的简称,广泛应用在大规模分布式应用中,作用是有助于系统的垂直…

Netty组件

Netty组件 EventLoop 事件循环对象 EventLoop本质是一个单线程执行器(同时维护了一个Selector,里面有run方法处理Channel上源源不断的io事件 它的继承关系比较复杂 一条线是继承自 j.u.c.ScheduledExecutorService 因此包含了线程池中所有的方法另一条线是继承…

R 语言基础

R 语言基础 一门新的语言学习一般是从输出 “Hello, World!” 程序开始&#xff0c;R 语言的 “Hello, World!” 程序代码如下&#xff1a; ## 实例&#xff08;helloworld.R&#xff09;myString <- "Hello, World!"print ( myString )以上实例将字符串 “Hell…

SQL注入进阶练习(二)常见绕过手段、防御的解决方案

常见绕过手段、防御的解决方案1.常用SQL注入绕过手段1.1 注释符绕过1.2 大小写绕过1.3 内联注释绕过1.4 双写关键字绕过1.5 特殊编码绕过1.6 空格过滤绕过1.7 过滤 or and xor (异或) not 绕过1.8 过滤等号绕过1.9 过滤大小于号绕过1.10 过滤引号绕过1.11 过滤逗号绕过1.12 过滤…

★LDO相关

1.型号 TPS79501 TPS79301 2.PSRR值&#xff0c;频率 TPS795_50dB&#xff0c;10kHz TPS793_70dB&#xff0c;10kHz 电源抑制比&#xff1a;供电电压纹波对输出电压影响&#xff0c;值越高越好&#xff08;某个频段的AC从输入到输出的衰减程度&#xff0c;衰减越高&#x…

提升集群吞吐量与稳定性的秘诀: Dubbo 自适应负载均衡与限流策略实现解析

作者&#xff1a;刘泉禄 整体介绍 本文所说的“柔性服务”主要是指 consumer 端的负载均衡和 provider 端的限流两个功能。在之前的 Dubbo 版本中&#xff0c;负载均衡部分更多的考虑的是公平性原则&#xff0c;即 consumer 端尽可能平等的从 provider 中作出选择&#xff0c;…

笔记本电脑自带录屏在哪?一步教您找到

案例&#xff1a;怎么找到笔记本电脑上的自带录屏功能&#xff1f; “从网上了解到笔记本电脑有自带的录屏功能&#xff0c;但我不知道笔记本自带的录屏叫什么名字&#xff0c;也不知道笔记本自带录屏在哪。有没有小伙伴知道&#xff1f;” 随着科技的不断进步&#xff0c;越…

【面试题】简单的说说对原型链的了解

大厂面试题分享 面试题库 前后端面试题库 &#xff08;面试必备&#xff09; 推荐&#xff1a;★★★★★ 地址&#xff1a;前端面试题库 web前端面试题库 VS java后端面试题库大全 前言 作为Javascript的基础之一&#xff0c;原型一直贯穿我们的JS代码并且成为面试的常考…

基于Python长时间序列遥感数据处理及在全球变化、物候提取、植被变绿与固碳分析、生物量估算与趋势分析等领域中的应用

植被是陆地生态系统中最重要的组分之一&#xff0c;也是对气候变化最敏感的组分&#xff0c;其在全球变化过程中起着重要作用&#xff0c;能够指示自然环境中的大气、水、土壤等成分的变化&#xff0c;其年际和季节性变化可以作为地球气候变化的重要指标。此外&#xff0c;由于…

eclipse上的Java静态分析工具

相比动态测试而言。静态分析效率高&#xff0c;成本较低&#xff0c;对于提高产品质量非常重要。 下面介绍几个elcipse上的静态分析插件 1. findugs a) 安装findbugs插件 1&#xff09;点击菜单 Help ->Eclipse Marketplace 在弹出窗口中的搜索条件中输入 ”findbugs“后…

[素数筛][容斥原理]:埃拉托斯特尼筛法

求解问题&#xff1a;不超过一个给定正整数N的素数的个数 方法介绍&#xff1a; 根据合数的性质&#xff1a;一个合数可以被一个不超过它的平方根的素数整除 这里举例N100&#xff1a; 介绍&#xff1a;为了找出不超过100的素数个数&#xff0c;首先根据合数的性质可以知道…

Docker详解,windows上安装与使用

Hi I’m Shendi Docker详解&#xff0c;windows上安装与使用 Docker详解 Docker 容器是一个开源的应用容器引擎&#xff0c;让开发者可以以统一的方式打包他们的应用以及依赖包到一个可移植的容器中&#xff0c;然后发布到任何安装了docker引擎的服务器上&#xff08;包括流行的…

面试时被问:为什么裁员只裁你,不裁别人,该怎么回答?

面试官总有各种奇奇怪怪的问题&#xff0c;比如这个&#xff1a;为什么裁员裁了你&#xff0c;而不是裁别人&#xff1f;这个充满恶意的问题该怎么回答&#xff1f;网友给出了各种各样的答案&#xff0c;有人说&#xff0c;就说行业动荡&#xff0c;不稳定。有人说&#xff0c;…

Golang每日一练(leetDay0023)

目录 67. 二进制求和 Add Binary &#x1f31f; 68. 文本左右对齐 Text Justification &#x1f31f;&#x1f31f;&#x1f31f; 69. x 的平方根 Sqrt x &#x1f31f; &#x1f31f; 每日一练刷题专栏 &#x1f31f; Golang每日一练 专栏 Python每日一练 专栏 C/C…

vscode软件设置头文件路径的方法

一. 设置头文件路径原因 在使用 vscode 软件进行 C 开发过程中&#xff0c;有些 .c 文件引用的头文件&#xff0c;提示会找不到头文件路径。因此&#xff0c;vscode 软件需要设置头文件路径。 二. vscode设置头文件路径 在 vscode 软件打开的情况下&#xff0c;默认打开一…

UNIX环境高级编程——UNIX基础知识

1.1 引言 所有操作系统都为它们所运行的程序提供服务&#xff0c;典型的服务包括&#xff1a; 执行新程序打开文件读文件分配存储区获得当前时间… 1.2 UNIX体系结构 可将操作系统定义为一种软件&#xff0c;它控制计算机硬件资源&#xff0c;提供程序运行环境&#xff0c;…

JAVA打飞机游戏的设计与实现

手机软件现状 在信息社会中&#xff0c;手机及其他无线设备越来越多的走进普通百姓的工作和生活&#xff0c;随着信息网络化的不断进展&#xff0c;手机及其他无线设备上网络势在必行。但是传统手机存在以下弊端&#xff1a; 1. 传统手机出厂时均由硬件厂商固化程序&#xf…

Spring Boot使用GraphQL开发Web API

目录前言Spring Boot中GraphQL的实现方案前言 传统的Restful API 存在诸多的问题&#xff0c;首先它无法控制返回的字段&#xff0c;前端也无法预判后端的返回结果&#xff0c;另外不同的返回结果对应不同的请求地址&#xff0c;这就导致了多次请求的问题。而GraphQL正是基于这…
最新文章