数据结构的理论同工程实现之间的鸿沟

从 Redis 的奇妙选择到 C++ 标准库的保守哲学

---

教科书里的数据结构，往往是一种理想状态下的抽象——红黑树永远平衡，哈希表永远优雅，跳表永远概率完美。但真正的工程系统，从不按教科书出牌。Redis 用跳表而不是红黑树实现有序集合，用一个叫 listpack 的压缩序列替代传统链表，甚至会根据数据量的多少，在运行时悄悄切换底层结构。C++ 标准库则走向另一个极端——它宁愿什么都不提供，也不愿意把一个"将就能用"的实现写进标准。

这两种截然不同的态度，背后其实指向同一个真相：数据结构的实现，远比它的定义复杂得多。

---

一、教科书之外的世界

大多数人学数据结构的路径是这样的：数组 → 链表 → 栈和队列 → 树 → 图 → 哈希表。每一种结构都有清晰的定义、漂亮的时间复杂度分析，以及配套的伪代码。

但这套体系有一个隐藏的前提：它假设内存是均匀的，操作是孤立的，数据量是固定的。

现实世界里，这三个假设全部不成立。

CPU 有缓存层级，访问连续内存比跳跃访问快几十倍；操作不是孤立的，并发读写会引入锁竞争；数据量是动态变化的，一个存了 3 个元素的集合和存了 300 万个元素的集合，最优的底层结构根本不是同一种东西。

于是，工程师们开始在理论骨架上生长出各种"变异体"。这些变异体有时面目全非，但每一处改动背后，都有充分的工程理由。

---

二、基础数据结构的标准形态

在进入工程案例之前，先快速回顾一下几种核心数据结构的"教科书版本"，这是理解后续变形的基础。

树族的演化谱系

最朴素的二叉搜索树（BST）在极端情况下会退化成链表，查询复杂度从 O(log n) 跌落到 O(n)。为了解决这个问题，AVL 树引入了严格的高度平衡约束，但代价是频繁的旋转操作。红黑树放宽了平衡条件，用"近似平衡"换取更少的旋转次数，成为工程中最广泛使用的平衡树。

B 树和 B+ 树则是为磁盘 I/O 设计的——通过增大每个节点的"扇出"（即子节点数量），降低树的高度，减少磁盘访问次数。数据库索引几乎清一色使用 B+ 树，原因正在于此。

跳表：链表的概率性升维

跳表（Skip List）是 William Pugh 在 1990 年提出的一种概率性数据结构。它的核心思想是：在普通链表之上，建立多层"快速通道"，每一层都是下一层的稀疏索引。

查找时从最高层开始，快速跳过大量节点，平均时间复杂度同样是 $O(\log n)$，但实现比红黑树简单得多。

哈希表的两种冲突解决策略

哈希表的核心挑战是哈希冲突。主流的解决方案有两种：

• 链地址法（Chaining） ：每个桶维护一个链表，冲突的元素挂在同一个桶里。Redis 和 Java HashMap 都采用这种方式。
• 开放寻址法（Open Addressing） ：冲突时在表内探测下一个空位。Python dict 和 C++ 的某些实现采用这种方式，缓存友好性更好。

---

三、Redis 的实现选择：工程智慧的集中展示

Redis 是理解"理论与工程之间鸿沟"的最佳教材。它的每一个设计决策，都是在内存效率、操作性能和实现复杂度之间精心权衡的结果。

3.1 跳表而非红黑树：ZSet 的核心选择

Redis 的有序集合（ZSet）在数据量较大时，底层使用跳表（skiplist）加哈希表的组合，而不是红黑树。这个选择让很多人感到意外。

antirez（Redis 作者）本人曾在邮件列表中解释过这个决定，理由有三点：

第一，范围查询更自然。 红黑树的范围查询需要中序遍历，实现复杂；跳表的底层就是一个有序链表，范围查询只需要找到起点然后顺序遍历，代码极其简洁。

第二，实现更简单，更容易调试。 红黑树的旋转和变色逻辑是出了名的难以理解，一旦出 bug 极难排查。跳表的逻辑相对直观，代码量也更少。

第三，内存局部性在这个场景下差异不大。 对于 Redis 这种内存数据库，跳表的内存访问模式已经足够好。

3.2 listpack：极致的内存压缩

Redis 7.0 用 listpack 替代了旧版的 ziplist，作为小数据量场景下的紧凑编码格式。

listpack 的设计思路是：把所有元素连续存储在一块内存里，完全消灭指针开销。 每个元素由三部分组成：编码类型、数据内容、以及当前元素的总长度（用于反向遍历）。

传统链表每个节点需要两个指针（前驱和后继），在 64 位系统上就是 16 字节的纯开销。如果存储的是小整数或短字符串，指针的开销甚至比数据本身还大。listpack 彻底消灭了这种浪费。

代价是：插入和删除需要移动内存，时间复杂度是 O(n)。但对于小数据量（通常阈值是 128 个元素），这个代价完全可以接受。

3.3 渐进式 rehash：不阻塞服务器的扩容

Redis 是单线程的（命令处理层面），这意味着任何耗时操作都会阻塞所有客户端请求。传统哈希表扩容时需要一次性重新计算所有键的哈希值并迁移，数据量大时这个操作可能耗时数秒——对 Redis 来说这是不可接受的。

Redis 的解决方案是渐进式 rehash（Progressive Rehash） ：

扩容时，Redis 同时维护两张哈希表（ht[0] 和 ht[1]）。每次对字典进行增删改查操作时，顺带将 ht[0] 中的一个桶迁移到 ht[1]。这样，扩容的开销被均摊到每一次操作上，单次操作的延迟增加极小。

3.4 quicklist：链表与压缩的混合体

Redis 的 List 类型底层使用 quicklist，这是一个"链表套 listpack"的混合结构：

每个 quicklist 节点是一个 listpack，节点之间用双向链表连接。这样既保留了链表两端 $O(1)$ 插入删除的特性，又通过 listpack 的紧凑存储大幅降低了内存占用。

3.5 intset：整数集合的极简实现

当一个 Set 里全是整数，且数量不多时，Redis 不用哈希表，而是用 intset——一个有序的整数数组。

查找用二分搜索，时间复杂度 $O(\log n)$；但内存极其紧凑，CPU 缓存命中率极高。对于小整数集合，实际性能往往优于哈希表。

3.6 小结：Redis 的核心哲学

Redis 的所有这些设计，都遵循同一个原则：

数据类型	小数据量编码	大数据量编码
String	int / embstr	raw (SDS)
List	listpack	quicklist
Hash	listpack	hashtable
Set	listpack / intset	hashtable
ZSet	listpack	skiplist + hashtable

这张表背后的逻辑是：小数据量时，紧凑存储的缓存友好性远比渐进复杂度更重要；数据量大了，才需要真正的 $O(\log n)$ 或 $O(1)$结构。

---

四、C++ 标准库的取舍哲学：宁缺毋滥

如果说 Redis 是"什么好用用什么"的实用主义，C++ 标准库则代表了另一种极端——极度保守的标准化哲学。

4.1 进了标准库的数据结构

C++ 标准库提供的容器其实相当有限：

容器	底层结构	复杂度保证
std::map / std::set	红黑树	O(log n) 查找/插入/删除
std::unordered_map	哈希表（链地址法）	平均 O(1)
std::priority_queue	二叉堆	O(log n) push/pop
std::deque	分段数组	O(1) 两端操作
std::vector	动态数组	O(1) 随机访问

4.2 没有进标准库的数据结构

以下这些在工程中极为常用的结构，至今不在 C++ 标准库中：

• 跳表（Skip List）
• B 树 / B+ 树
• Trie（前缀树）
• 布隆过滤器（Bloom Filter）
• 并查集（Union-Find）
• 线段树（Segment Tree）

为什么？

4.3 标准化的困境：实现细节无法统一

C++ 标准库的设计原则之一是：标准只规定接口和复杂度，不规定实现。 但问题在于，很多数据结构的"最优实现"高度依赖具体场景，根本无法给出一个放之四海而皆准的版本。

以跳表为例：层数应该设多少？概率参数 p 应该取多少（通常是 $\frac{1}{4}$ 或 $\frac{1}{2}$）？节点的内存如何分配？这些参数的不同选择，会导致性能在不同场景下差异巨大。如果标准委员会随意选定一组参数写进标准，那么在某些场景下，这个"标准跳表"可能远不如用户自己实现的版本。

更糟糕的是：一旦进入标准库，实现就被事实上"冻结"了。 所有依赖标准库的代码都假设其行为不变，这使得后续优化极为困难。

4.4 std::regex 的前车之鉴

std::regex 是一个典型的反面教材。它在 C++11 进入标准，但各大编译器的实现性能极差——在某些测试中，std::regex 比 PCRE（一个流行的正则表达式库）慢 10 倍到 100 倍。

原因是标准委员会在没有充分参考实现的情况下，仓促地将接口标准化，导致各家实现都选择了次优的算法（NFA 模拟而非 DFA 构造）。这个问题至今没有完全解决，因为修改实现可能破坏现有代码的行为。

4.5 std::map 的隐藏代价

即便是已经进入标准库的 std::map，也有不少工程师对其实现不满。

std::map 基于红黑树，每个节点都是独立分配的堆内存，节点之间通过指针连接。这意味着遍历 std::map 时，CPU 需要不断追逐指针，缓存命中率极低。对于需要频繁遍历的场景，一个简单的有序 std::vector 加二分搜索，往往比 std::map 快得多。

这就是为什么 Abseil（Google 的 C++ 基础库）提供了 absl::btree_map——用 B 树替代红黑树，大幅提升缓存友好性，同时保持相同的接口。

---

五、数据结构实现的隐藏复杂度

教科书只告诉你时间复杂度，但真正决定性能的，往往是这些"隐藏变量"。

5.1 内存分配策略

标准的 new/delete 操作涉及系统调用，开销不可忽视。高性能系统通常使用专用的内存分配器：

• Arena 分配器：预先申请一大块内存，然后线性分配，释放时整块归还。适合生命周期一致的对象。
• 内存池（Pool Allocator） ：为固定大小的对象预分配内存块，完全消灭分配开销。Redis 的 zmalloc 就是一种定制分配器。
• Slab 分配器：Linux 内核使用的分配策略，按对象大小分类管理内存块。

同一种数据结构，配合不同的内存分配策略，性能可以相差数倍。

5.2 缓存友好性：现代性能的第一要素

现代 CPU 的内存访问速度与缓存命中率密切相关：

存储层级	访问延迟
L1 缓存	~4 个时钟周期
L2 缓存	~12 个时钟周期
L3 缓存	~40 个时钟周期
主内存（RAM）	~200 个时钟周期

这意味着，一个"缓存不友好"的数据结构，每次访问都可能付出 50 倍的延迟代价。

这正是为什么：

• 数组比链表快（连续内存 vs 指针跳跃）
• B 树比红黑树更适合大数据集（更少的指针追逐）
• Redis 的 listpack 在小数据量下性能出色（所有数据在一块连续内存里）

5.3 并发安全与锁粒度

单线程环境下的最优数据结构，在多线程环境下可能完全不适用。

以哈希表为例：

• 全局锁：实现简单，但并发度极低
• 分段锁（Segment Lock） ：Java 的 ConcurrentHashMap 早期实现，将哈希表分成多个段，每段一把锁
• 无锁（Lock-Free） ：使用 CAS（Compare-And-Swap）原子操作，实现复杂但并发性能最佳

Redis 通过单线程模型完全规避了并发问题，这也是它能使用如此多"非线程安全"数据结构的根本原因。

5.4 平台差异与 SIMD 指令

现代 CPU 提供了 SIMD（单指令多数据）指令集，可以一次操作 128 位、256 位甚至 512 位的数据。针对 SIMD 优化的数据结构，在字符串匹配、数组搜索等场景下，性能可以提升 4 到 16 倍。

但这种优化是高度平台相关的——x86 的 AVX2 指令在 ARM 上完全不可用。这也是为什么标准库很难将这类优化写进规范。

---

六、工程选型的决策框架

面对如此多的选择，工程师如何决定用哪种数据结构？以下是一个实用的决策框架。

6.1 数据规模决定结构形态

Redis 的动态编码切换，本质上就是在自动执行这个决策树。

6.2 读写比例决定优化方向

场景	推荐结构	理由
读多写少	有序数组 + 二分搜索	读性能极佳，写入可以批量处理
写多读少	LSM Tree	写入顺序化，读取时合并
读写均衡	红黑树 / 跳表	均衡的 $O(\log n)$ 保证
点查为主	哈希表	$O(1)$ 平均查找
范围查询为主	B+ 树 / 跳表	有序结构天然支持范围扫描

6.3 内存 vs 速度的永恒权衡

• 空间换时间：哈希表、缓存、预计算索引
• 时间换空间：压缩编码（listpack）、流式处理
• 两者兼顾：往往需要混合结构，如 Redis 的 quicklist

---

七、结语：数据结构是活的

回到最初的问题：为什么 Redis 的实现和教科书差那么远？为什么 C++ 不把跳表和 B 树放进标准库？

答案其实是同一句话：数据结构不是一个静态的数学对象，而是一个活在特定约束条件下的工程产物。

Redis 的每一个"奇怪"选择，都是在内存、速度、单线程模型、实际数据分布这些约束下，做出的最合理决策。C++ 标准库的保守，则是对"一旦标准化就难以改变"这一现实的清醒认知——std::regex 的教训告诉我们，仓促的标准化比没有标准化更糟糕。

对于程序员来说，这意味着：理解数据结构的原理是基础，但真正的功力在于理解约束——知道在什么条件下，哪种实现是最合适的。教科书给你的是地图，而工程给你的是地形。地图永远比地形简单，但没有地图，你也看不懂地形。

跳表不比红黑树"更好"，listpack 也不比链表"更先进"——它们只是在各自的约束条件下，恰好是正确的答案。

---

参考来源：

• How Redis Dict (Hash Table) Implementation Works, OneUptime Blog, 2026
• Why Does Redis Use Skip Lists To Implement Sorted Sets? , Level Up Gitconnected
• Redis Deep Dive Part 2 - The Building Blocks, thuva4.com
• Redis underlying data structure: Everything you need to know, DevOps.dev Blog