企业官网建设流程全解析

跳表（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：

1. 从最高层（层 2）开始，找到不大于目标的节点 1，下一个是 7，大于目标 →下沉到下一层
2. 层 1，走到 7；下一个 9>7 →下沉到层 0
3. 层 0 找到 7，结束

3. 核心特点

1. 有序：底层链表数据始终保持有序
2. 随机层数：插入节点时，用随机算法决定这个节点向上建几层索引（概率保证整体平衡，不用像红黑树那样做旋转）
3. 时间复杂度：查找 / 插入 / 删除 平均 O (log n)，最坏 O (n)
4. 空间复杂度：O (n)，额外索引要占用内存

一、Redis 中的跳表

zset有两种实现：

1. 元素少、数据小：ziplist 压缩列表
2. 元素多：skipList（跳表）+ 哈希表

Redis 跳表特点

1. 保存有序数据，按score分值排序；
2. 每个节点随机层数（幂次随机，不是固定高度），不是平衡树那样强制平衡；
3. 支持：范围查询（ZRANGE）、按分值区间查找、有序遍历；这是哈希表做不到的；
4. 为什么 Redis zset 不用红黑树而选跳表：
   • 跳表实现简单，代码少，维护成本低
   • 范围遍历更友好（链表天然顺序）
   • 插入删除不需要复杂树旋转，CPU 缓存表现不差

注意：Redis 只有 zset 用跳表，String/Hash/List/Set 不用。

Redis 跳表节点结构

level[] // 多层前进指针，每一层指向下一个同层节点 backward // 后退指针（反向遍历） score // 排序分值 obj // 存储元素

二、MySQL 有没有跳表？

✅MySQL InnoDB 索引是 B + 树，不是跳表！这点面试高频坑

• InnoDB 主键 / 二级索引：B + 树，磁盘友好，所有数据在叶子节点有序，适合磁盘 IO；
• B + 树是多路平衡树，磁盘页为节点，和内存跳表完全不是一类结构。

那为什么有人说 MySQL 提到跳表？

1. InnoDB内存结构里有少量跳表：比如bufferpool缓冲池里部分内存管理、空闲链表会用到跳表做内存快速查找；不是磁盘上的索引！
2. MySQL 官方存储引擎的索引体系和跳表无关。

概括：

MySQL InnoDB 磁盘索引用 B + 树，索引不是跳表；

Redis zset 底层使用跳表实现有序范围查询。

三、对比总结表