数据结构的理论同工程实现之间的鸿沟
从 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(logn)O(log n)O(logn)，但实现比红黑树简单得多。
哈希表的两种冲突解决策略
哈希表的核心挑战是哈希冲突。主流的解决方案有两种：
- 链地址法（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)O(1)O(1) 插入删除的特性，又通过 listpack 的紧凑存储大幅降低了内存占用。
3.5 intset：整数集合的极简实现
当一个 Set 里全是整数，且数量不多时，Redis 不用哈希表，而是用 intset——一个有序的整数数组。
查找用二分搜索，时间复杂度 O(logn)O(log n)O(logn)；但内存极其紧凑，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(logn)O(log n)O(logn) 或 O(1)O(1) 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 应该取多少（通常是 14frac{1}{4}41 或 12frac{1}{2}21）？节点的内存如何分配？这些参数的不同选择，会导致性能在不同场景下差异巨大。如果标准委员会随意选定一组参数写进标准，那么在某些场景下，这个"标准跳表"可能远不如用户自己实现的版本。
更糟糕的是：一旦进入标准库，实现就被事实上"冻结"了。 所有依赖标准库的代码都假设其行为不变，这使得后续优化极为困难。
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(logn)O(log n)O(logn) 保证 |
| 点查为主 | 哈希表 | O(1) O(1)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
