跳表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)存储介质内存优先磁盘为主范围查询优秀链表顺序遍历优秀叶子节点链表串联实现难度简单无旋转复杂分裂合并节点平衡随机高度非强制平衡严格多路平衡