摘要：本文将从面试题切入，盘点 Redis 全系数据类型，并深入剖析“跳表”这一核心数据结构，探讨它在 Lucene、Java中的应用，以及它与B+树的异曲同工。
一、 Redis 数据类型全景
在面试中，如果只回答 "String, Hash, List, Set, ZSet"，只能算刚及格。作为高级工程师，我们需要展示对业务场景的深度理解。
1. 基础类型（必知必会）
- String: 最基本类型，不仅存字符串，还能做计数器（INCR）、分布式锁（SETNX）。
- Hash: 适合存储对象，如用户信息。
- List: 双向链表，常用于简单的消息队列（LPUSH/RPOP）或最新列表。
- Set: 无序集合，用于去重、共同好友（交集）、抽奖。
- ZSet (Sorted Set): 核心考点。有序集合，用于排行榜、带权重的队列。底层就是跳表。
2. 高级类型（加分项）
- Bitmap: 位图。极度节省空间，适合做签到统计、用户在线状态（1亿用户仅需十几MB）。
- HyperLogLog: 基数统计。用于统计网站 UV，误差 0.81%，但空间占用极小。
- Geo: 地理位置。基于 GeoHash，用于“附近的人”、“距离计算”。
- Stream: Redis 5.0 引入，真正的轻量级消息队列，支持消费者组，解决了 List 做队列的痛点。
- 底层结构 vs 对外类型映射表
| 底层结构分类 | 数据结构 | 核心地位 | 底层原理 | 关键特性 (优缺点) | 主要应用场景 |
|---|---|---|---|---|---|
| 一、连续内存类 (空间效率极高) |
SDS (简单动态字符串) |
Redis 的“原子”结构，无处不在 | C 语言字符数组 + len (长度) + alloc (容量) |
1. O(1) 获取长度 2. 空间预分配（减少 malloc） 3. 二进制安全（不依赖 \0） |
String 类型、所有 Key、内部缓冲区 |
| IntSet (整数集合) |
Set 存储纯整数且量少时的专用结构 | 有序整数数组 (int16/32/64) |
1. 极致省内存 2. 二分查找 O(logN) 3. 只能升级不能降级 |
Set (纯整数小数据) | |
| Listpack (紧凑列表) |
新一代神器 (Redis 7.0 标配)，替代 Ziplist | 连续内存，元素只记录自身长度 | 1. 彻底解决“连锁更新”问题 2. 省去指针开销，缓存命中率高 3. 中间修改需内存拷贝 |
Hash (小对象)、ZSet (少数据)、List (Quicklist 的节点) | |
| 二、索引查找类 (访问速度极快) |
Hashtable (字典/哈希表) |
Redis 的骨架，整个 DB 就是个大 Hash | 数组 + 链表 (拉链法) | 1. 双哈希表 (ht[0]/ht[1])2. 渐进式 Rehash (分摊扩容压力，不卡主线程) |
Redis 全局 DB、Hash (大数据)、Set (非纯整数/大数据) |
| Skiplist (跳表) |
ZSet 排序与范围查找的核心 | 有序链表 + 随机多层索引 | 1. 比红黑树实现简单 2. 范围查找 (Range Query) 极快 3. 并发优化容易 |
ZSet (大数据量) | |
| 三、组合/混合型 (平衡时间与空间) |
Quicklist (快速列表) |
List (列表) 的专用结构 | 双向链表 + Listpack | 1. 宏观是链表 (插入快) 2. 微观节点是 Listpack (省内存) 3. 减少了纯链表的指针开销 |
List |
| 四、特殊树型 (针对特定场景) |
Radix Tree (Rax / 基数树) |
Stream 和 Cluster 的专用结构 | 压缩的前缀树 | 1. 前缀压缩 (相同前缀只存一次) 2. 效率取决于 Key 长度而非数据量 |
Stream 消息 ID (时间戳前缀)、集群槽位管理 |
总结概括
- 小数据/小对象：优先使用 Listpack/IntSet（以时间换空间，极致压缩）。
- 大数据/大对象：升级为 Hashtable/Skiplist（以空间换时间，保证 O(1) 或 O(logN)）。
- List 特例：使用 Quicklist 这种“链表+数组”的混合体来平衡两者的优缺点。
- Stream 特例：使用 Rax 处理高重复前缀的消息 ID。
二、 跳表 (Skip List) —— 以空间换时间的艺术
为什么 Redis 的 ZSet 选择跳表而不是红黑树？
1. 什么是跳表？
简单来说，跳表是一个多层的有序链表。
普通链表查找元素需要 O(N) 的时间。跳表通过提取“索引层”，每隔几个节点就提取一个指针指向上层，形成类似二分查找的结构，将查询时间复杂度降低到 O(logN)。
2. 为什么是跳表？
- 实现简单: 相比红黑树复杂的旋转和平衡逻辑，跳表的代码实现不到其 1/10。
- 并发友好: 这是关键。在多线程并发下，红黑树的平衡操作（Rebalance）可能锁住大范围节点；而跳表只需要局部更新指针，支持高并发写入。
- 范围查找: ZSet 常用于
ZRANGE，跳表本身就是有序链表，范围查找效率极高。
三、 跳表还在哪里使用？
跳表不仅仅存在于 Redis 中，它是现代高性能存储引擎的基石。
1. Lucene (Elasticsearch 的核心)
Lucene 的核心是倒排索引（Inverted Index）。当我们需要做多条件查询（例如 Term A AND Term B）时，需要对两个文档 ID 列表做交集。
Lucene 在压缩的倒排链表中加入了 Skip Data。这使得在查找特定文档 ID 时，可以利用跳表结构快速跳过大量不匹配的数据（Skip Scanning），极大提升了 AND 查询的性能。
3. Java JUC
JDK 中的 ConcurrentSkipListMap 是 Java 标准库中唯一线程安全的有序 Map。如果你需要在多线程下进行范围查询，它是唯一的选择。
四、 跳表 vs B+ 树 (为何内存选跳表？而磁盘选B+树)
B+ 树和跳表（Skip List）虽然物理结构截然不同，但在逻辑功能上非常相似
一、 核心相似点 (逻辑层面)
在功能和算法复杂度上，它们几乎是“双胞胎”：
- 有序性：
- 两者都维护数据的有序排列。这使得它们都支持二分查找思想的快速检索。
- 查找复杂度：
- 平均时间复杂度都是 O(log N)。无论是查一个数，还是插入一个数，效率在一个数量级。
- 支持范围查询 (Range Query)：
- 这是它们区别于哈希表（Hash Map）的关键。
- B+ 树：找到起点后，通过叶子节点的链表向后遍历。
- 跳表：找到起点后，通过最底层的链表向后遍历。
- 两者处理
SELECT * FROM table WHERE id > 100这种查询都非常高效。
二、 核心不同点 (物理与架构层面)
这是面试和架构选型的关键所在，决定了为什么 MySQL 用 B+ 树，而 Redis 用跳表，这里涉及到一个核心概念：页分裂 (Page Split)。
1. 结构与平衡机制 (Deterministic vs. Probabilistic)
- B+ 树（严格平衡）：
- 机制：通过自底向上的节点分裂（Split）和合并（Merge）来维持树的平衡。
- 特点：树的高度是严格受控的，通常非常矮胖（3-4层）。
- 跳表（概率平衡）：
- 机制：通过随机函数（掷硬币）决定一个新节点有多少层索引。
- 特点：它不强制每一层索引完美分布，而是依赖概率保证整体的平衡。实现简单，不需要复杂的旋转或分裂。
2. 存储单元 (Page vs. Node)
- B+ 树：
- 以“页/块”(Page) 为单位。一个节点通常对应磁盘的一个页（如 16KB）。
- 优势：极度迎合磁盘的顺序读写特性，一次 I/O 读入大量索引。
- 跳表：
- 以“节点”(Node) 为单位。每个节点是内存中独立的对象，通过指针连接。
- 劣势：如果在磁盘上用跳表，跨节点遍历会导致大量的随机 I/O（磁头乱跳），性能会极其低下。
3. 写入代价 (Page Split vs. Pointer Update)
- B+ 树：
- 重型操作。当页满时，需要申请新页、移动数据、修改父指针，甚至引发连锁分裂。
- 并发难：为了保证树结构的完整性，分裂期间往往需要锁住涉及的路径，影响并发写性能。
- 跳表：
- 轻型操作。只需要创建一个新节点，修改前后几个节点的指针即可。
- 并发易：通过 CAS (Compare-And-Swap) 操作即可完成指针更新，更容易实现无锁（Lock-Free）或细粒度锁，高并发写入性能优于 B+ 树。
4. 空间利用率
- B+ 树：
- 存在页内碎片。如果一个页只填了 60% 的数据，剩下的 40% 空间在分裂前是不可用的（但在磁盘上是预占的）。
- 跳表：
- 存在指针开销。每个节点平均需要维持 1.33 个指针（取决于概率参数），在内存中这部分是指针的空间损耗。
三、 总结对比表
| 维度 | B+ 树 (B+ Tree) | 跳表 (Skip List) |
|---|---|---|
| 典型应用 | MySQL | Redis (ZSet) |
| 主要场景 | 磁盘存储 | 内存存储 |
| 查找复杂度 | $O(\log N)$ (底数大，树极矮) | $O(\log N)$ (底数小，层级多) |
| 数据结构单位 | 固定大小的 Page (页) | 独立的 Node (节点) |
| 插入操作 | 可能触发 页分裂 (Split)，开销大 | 局部指针更新，无须全局调整 |
| 并发能力 | 较差 (分裂需锁结构) | 极强 (CAS 原子更新) |
| I/O 特性 | 顺序 I/O 友好 (索引紧凑) | 随机 I/O (节点分散，不适合磁盘) |
| 代码复杂度 | 极高 (处理分裂、合并、边界) | 较低 (不到 B+ 树的 1/10) |
四、 灵魂拷问：为什么不能反过来？
- 为什么 MySQL 不用跳表？
- 因为 MySQL 的数据主要在磁盘上。跳表的节点在物理内存/磁盘上是分散的。如果要查一个位于跳表深处的节点，可能需要读取几十次磁盘（随机 I/O），这会让数据库卡死。而 B+ 树把几千个索引挤在一个页里，一次 I/O 就能读到，3 次 I/O 就能定位任何数据。
- 为什么 Redis 不用 B+ 树？
- Redis 是纯内存操作，不涉及磁盘 I/O 慢的问题。B+ 树为了维持“矮胖”和“不分裂”，写代码非常复杂，且在内存中并没有节省时间的优势（内存中指针跳转极快）。跳表代码简单、省内存（不用预留页空间）、且并发写性能更好，完美契合 Redis 的需求。
结语
从 Redis 的 ZSet 到搜索引擎的倒排索引，再到大数据底层的 LSM-Tree，跳表这一数据结构凭借其简单的实现和卓越的并发性能，成为了架构设计中的“瑞士军刀”。