说起来，

你是否在实际项目中遇到以下困惑？

• 教科书里的数据结构看起来很完美，却在生产环境里频繁崩溃；
• 面对海量数据，不知道该选用哪种底层实现才能兼顾性能与内存；
• C++ 标准库提供的容器远不能满足业务需求，却又担心自行实现会埋下隐蔽的性能坑。

如果这些痛点让你夜不能寐。那么下面的内容将帮助你从理论到工程，实现一次“弥合鸿沟”的跨越。

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

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

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

一、教科书之外的世界

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

痛点一：理论假设与真实硬件不匹配。 这套程序有一个隐藏前提：它假设内存是均匀的。操作是孤立的，数据量是固定的。

现实世界里这三个假设全部不成立。CPU 有缓存层级，访问连续内存比跳跃访问快几十倍；并发读写会引入锁竞争，数据量是动态变化的，一个存了 10 个元素的集合和存了 10⁶ 个元素的集合。最优的底层结构根本不是同一种东西。

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

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

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

树族的演化谱系

最朴素的二叉搜索树在极端情况下会退化成链表，查询复杂度从 O 跌落到 O。说起来，为了解决这个问题。L 树引入了严格的高度平衡约束，但代价是频繁的旋转操作。红黑树放宽了平衡条件，用“近似平衡”换取更少的旋转次数。成为工程中最很多人在用的平衡树。

B 树和 B+ 树则是为磁盘 I/O 设计——通过增大每个节点的“扇出”。降低树高，从而减少磁盘访问次数。数据库索引几乎清一色使用 B+ 树，因为它兼具顺序遍历和高效定位。

再看跳表，链表的概率性升维

跳表是 William Pugh 在 1990 年 提出的一种概率性数据结构。它在普通链表之上建立多层“快速通道”，每一层都是下一层稀疏索引。 其实，

graph LR
subgraph Level1
H3 --> N3_1 --> N3_4 --> T3
end
subgraph Level2
H2 --> N2_1 --> N2_3 --> N2_4 --> N2_6 --> T2
end
subgraph Level3
H1 --> N1_1 --> N1_2 --> N1_3 --> N1_4 --> N1_5 --> N1_6 --> T1
end

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

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

哈希冲突 是所有哈希表必须面对的问题。至于主流方案有，

• 链地址法：每个桶维护一个链表。冲突元素挂在同一个桶里，Redis 和 Java HashMap 都采用此法。
• 开放寻址法：冲突时探测下一个空位。Python dict 和部分 C++ 实现采用此法，更加缓存友好。

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

跳表而非红黑树：ZSet 的主要选择

ZSet 在数据量较大时使用跳表 + 哈希表组合，而不是红黑树。这让很多人感到意外，

Pain Point 二：C++ 开发者习惯于直接使用 a std::map却忽视了范围查询在实际业务中的实现成本。Redis 给出了更易维护、更高效的一条路。

• #1 范围查询更自然：红黑树需要中序遍历实现复杂；跳表底层就是有序链表，只需找到起点后顺序遍历即可。
• #2 实现更简单。更容易调试：红黑树旋转、变色逻辑繁琐，一旦出现 bug 极难排查；跳表逻辑直观，代码量更少。怎么说呢，
• #3 内存局部性差异不大：M​emory‑resident 场景下两者缓存命中率相当。而跳表省去大量指针操作带来的维护成本。

graph TD
A --> B{数据量判断}
B -->|元素数 <128 且单个元素 <64字节| C
    B -->|超过阈值| D
D --> E
D --> F

listpack：极致压缩 & 小数据量利器

listpack 替代旧版 ziplist，是 Redis 为小对象设计的一体化紧凑编码格式。所有元素连续存储，无指针开销，每个元素仅包含类型、内容和自身长度信息。从而消灭指针导致的大量空间浪费。

Pain Point 三：C++ 中常见 “std::list” 每节点两个指针，在处理大量小对象时会导致内存使用爆炸。tag listpack  展示了 “把指针去掉” 的直接收益。

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

C++ 标准库中的哈希容器在扩容时会一次性搬迁全部桶，这对实时程序来说不可接受。而 Redis 采用渐进式 rehash 维护两张哈希表。每次普通操作顺带迁移部分旧桶，将扩容成本均摊到后续请求上，实现毫秒级延迟增长。

quicklist：链表 & 压缩双模组合

LList  底层使用quicklist 。怎么说呢，每个 quicklist 节点是一段 listpack，使得两端插入/删除保持 O。同时内部保持连续内存，提高缓存命中率，实现了 “速度 + 空间” 双赢。

从intset来看，整数集合极简实现

intset。不过，二分搜索提供 O 查找，同时内存使用仅为原始整数大小数倍。明显提高 CPU 缓存命中率。这正对应 C++ 开发者常见 “std::unordered_set` 在小集合场景下浪费严重”的痛点。

再看小结。Redis 的主要哲学

这张图背后的逻辑是：小规模时紧凑存储更关键，大规模时才需要对数或常数时间复杂度的数据结构。​ ​ ​ ​ ​ ​ ​ ​ ​