尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
Redis底层之跳表
跳表Skip List一句话跳表 多层索引的有序链表用空间换时间让有序链表的查询从 O (n) 降到平均 O (log n)。1. 普通有序链表的痛点普通有序链表1 → 3 → 5 → 7 → 9 → 11想找 7只能从头逐个遍历O(n)数据量大很慢。 就算有序也没法像数组一样二分查找链表不支持随机访问。2. 跳表怎么做在原始链表第 0 层保存全部数据之上额外建立多层稀疏索引第 0 层完整有序链表所有数据都在这里第 1 层从第 0 层挑一部分节点作为索引第 2 层再从第 1 层挑更少节点更高层节点更少示例层2: 1 ---------- 7 ---------- 11 层1: 1 ---- 3 ----7 ----9 ----11 层0: 1 →3 →5 →7 →9 →10 →11查找 7从最高层层 2开始找到不大于目标的节点 1下一个是 7大于目标 →下沉到下一层层 1走到 7下一个 97 →下沉到层 0层 0 找到 7结束3. 核心特点有序底层链表数据始终保持有序随机层数插入节点时用随机算法决定这个节点向上建几层索引概率保证整体平衡不用像红黑树那样做旋转时间复杂度查找 / 插入 / 删除 平均 O (log n)最坏 O (n)空间复杂度O (n)额外索引要占用内存一、Redis 中的跳表zset有两种实现元素少、数据小ziplist 压缩列表元素多skipList跳表 哈希表Redis 跳表特点保存有序数据按score分值排序每个节点随机层数幂次随机不是固定高度不是平衡树那样强制平衡支持范围查询ZRANGE、按分值区间查找、有序遍历这是哈希表做不到的为什么 Redis zset 不用红黑树而选跳表跳表实现简单代码少维护成本低范围遍历更友好链表天然顺序插入删除不需要复杂树旋转CPU 缓存表现不差注意Redis 只有 zset 用跳表String/Hash/List/Set 不用。Redis 跳表节点结构level[] // 多层前进指针每一层指向下一个同层节点 backward // 后退指针反向遍历 score // 排序分值 obj // 存储元素二、MySQL 有没有跳表✅MySQL InnoDB 索引是 B 树不是跳表这点面试高频坑InnoDB 主键 / 二级索引B 树磁盘友好所有数据在叶子节点有序适合磁盘 IOB 树是多路平衡树磁盘页为节点和内存跳表完全不是一类结构。那为什么有人说 MySQL 提到跳表InnoDB内存结构里有少量跳表比如bufferpool缓冲池里部分内存管理、空闲链表会用到跳表做内存快速查找不是磁盘上的索引MySQL 官方存储引擎的索引体系和跳表无关。概括MySQL InnoDB 磁盘索引用 B 树索引不是跳表Redis zset 底层使用跳表实现有序范围查询。三、对比总结表项目跳表B 树应用场景Redis zset内存MySQL InnoDB 索引磁盘查找复杂度平均 O (logn)稳定 O (logn)存储介质内存优先磁盘为主范围查询优秀链表顺序遍历优秀叶子节点链表串联实现难度简单无旋转复杂分裂合并节点平衡随机高度非强制平衡严格多路平衡
RELATED

相关推荐

C#联合Halcon匹配算法实战:选型、调参与避坑指南

C#联合Halcon匹配算法实战:选型、调参与避坑指南

简介:这份资源面向具备一定C#基础、希望入门机器视觉的开发者,聚焦在C#环境中调用Halcon库实现模板匹配算法,并配套WPF界面展示匹配结果。内容涉及灰度值匹配、形状匹配、颜色匹配等方法的选型思路,以及Halcon .NET接口的引用配置…

📅 2026/10/5 11:34:03
工程车辆目标检测数据集:YOLO格式标注与YOLOv8训练实战

工程车辆目标检测数据集:YOLO格式标注与YOLOv8训练实战

简介:工程车辆目标检测数据集面向建筑工地智能监控、交通物流管理及自动驾驶环境感知等场景,为算法工程师、计算机视觉研究者与工程类院校师生提供即用型训练数据。数据集聚焦混凝土搅拌车、自卸卡车与挖掘机三类核心工程车辆,覆盖真实建筑与…

📅 2026/10/5 11:34:03
独立站谷歌SEO实操全攻略:从关键词研究到FAQPage结构化数据落地

独立站谷歌SEO实操全攻略:从关键词研究到FAQPage结构化数据落地

如果你做网站也有段时间了,肯定能感受到一个扎心的现实:内容写得再认真,没人搜到就等于白写。我早年做独立站的时候,就吃过这个亏——产品图片精修了三天,详情页文案改了五版,结果上架一个月,自…

📅 2026/10/5 11:34:03
MORE NEWS

更多资讯

📰

恶意代码开发(免杀)(2)——SGN加密

恶意代码开发(免杀)(1)-CSDN博客 SGN 加密 SGN(Shikata Ga Nai)是一个多态二进制编码器,主要用于生成静态上无法被检测的二进制 payload。它通过加法反馈循环对二进制指令进行编码,使输出结果与随机数据完…

📰

MySQL InnoDB核心机制:从SQL执行到事务日志的完整解析

1. 一条SQL从客户端到InnoDB的完整路径 1.1 连接器:会话不是一锤子买卖 你打开终端,敲下 mysql -u root -p ,输入密码回车,看到欢迎横幅的同时,MySQL服务端实际上只做了一件看起来简单的事:创建一条会话…

📰

STM32F103驱动57闭环步进电机:接线、参数与代码实战

年末整理设备间的时候,翻出一套一直没拆封的57闭环步进电机套件,配的驱动器是市面上很常见的国产闭环驱动,电机本体带一千线编码器。最近正好在给一台小型点胶机构做运动控制改造,控制板用的是STM32F103ZET6,索性就把这…

📰

插件加载失败深度解析:web boot的did not activate报错排查手册

最近“plugins”这个词连带一串搜索热词一起冲了出来,尤其是“failed to load plugins web boot: 2 entries did not activate linxin666/dsh-p”和“harness failed to load plugins web boot: 1 entry did not activate huayu-yuan”这种报错,隔着屏幕…

📰

插件加载失败怎么排查?从IAR到Harness,一次讲透插件机制与修复方法

前阵子一个朋友给我转来一长串截图,全是同一个主题: harness failed to load plugins web boot: 2 entries did not activate 。扫一眼没头没尾,但类似的报错我在不同工具里见过太多次了。紧接着嵌入式群又有人问“iar plugins 是干什么的”…

📰

基于特征值分析法的电力系统次同步振荡稳定性研究

简介:这份PDF文献面向电力系统专业研究人员、电气工程研究生及从事电网稳定性分析的工程技术人员,聚焦基于特征值分析法的电力系统稳定性研究,尤其针对串补输电系统中次同步谐振(SSO)的机理与判别问题。资源包内含1个P…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬