数据结构选型：红黑树 vs 跳表 vs 平衡二叉树，为什么交易所偏爱跳表？
做订单簿系统，第一个绕不开的问题就是：用什么数据结构来存订单？
我见过不少刚入行的同学，上来就拍脑袋说「用红黑树啊，STL 里现成的」。嗯，理论上是没错。但真到了交易所那种每秒百万笔订单的场景下，你会发现事情没那么简单。
今天我们就来掰扯掰扯，红黑树、跳表、平衡二叉树这三兄弟，到底谁更适合做订单簿的底层骨架。
先说说平衡二叉树（AVL）
AVL 树是最早的自平衡二叉搜索树。它的核心思想很简单：每个节点的左右子树高度差不超过 1。
好处是什么？查找极快，O(log n) 稳稳的。坏处呢？插入和删除时的旋转操作太频繁了。每次插入或删除，都可能触发一连串的旋转，这在高频交易场景下是致命的。
我记得有一次，团队里有人用 AVL 树做订单簿原型，结果压测时发现，当订单簿深度达到 5000 层时，一次订单插入居然花了 3 微秒。3 微秒听起来不多，但乘以每秒 50 万笔订单，你就知道问题有多大了。
红黑树：STL 的默认选择
红黑树是平衡二叉树的「改良版」。它放宽了平衡条件——不再要求左右子树高度差不超过 1，而是通过红黑节点的颜色规则来保证大致平衡。
这样做的好处是：插入和删除的旋转次数大大减少。平均情况下，红黑树的插入只需要 O(1) 次旋转，而 AVL 可能需要 O(log n) 次。
所以 C++ STL 的 map 和 set 底层都用红黑树，不是没有道理的。
但是，红黑树有个硬伤：对缓存不友好。它的节点在内存中是分散存储的，每个节点通过指针相连。当你遍历订单簿时，CPU 缓存会频繁失效，因为相邻的订单在内存中可能隔得很远。
你想想看，在交易所这种场景下，我们经常需要按价格顺序遍历订单簿（比如扫单）。红黑树的遍历性能，说实话，不太行。
跳表：交易所的「真香」选择
好了，重点来了。为什么那么多交易所最终选择了跳表？
说白了，跳表有三个核心优势：
- 对缓存友好：跳表的节点在内存中是连续存储的（通常用数组实现），遍历时 CPU 缓存命中率极高。
- 实现简单：跳表的代码量大概是红黑树的 1/3，出 bug 的概率也低得多。
- 并发友好：跳表的锁粒度可以控制得很细，甚至可以用无锁编程。
我参与过的一个项目，最初用的是红黑树，后来切换到跳表，订单簿重建时间从 12 毫秒降到了 3 毫秒。你没看错，4 倍的提升。
三种数据结构的对比
| 特性 | AVL 树 | 红黑树 | 跳表 |
|---|---|---|---|
| 查找复杂度 | O(log n) | O(log n) | O(log n) |
| 插入复杂度 | O(log n) | O(log n) | O(log n) |
| 删除复杂度 | O(log n) | O(log n) | O(log n) |
| 范围遍历 | 差（缓存不友好） | 中（缓存不友好） | 优（内存连续） |
| 实现难度 | 高 | 高 | 低 |
| 并发友好度 | 差 | 中 | 优 |
| 实际性能（订单簿场景） | 差 | 中 | 优 |
跳表的实现要点
如果你决定用跳表做订单簿，有几个细节要注意：
- 层数选择：通常 16 层就够了，再高收益不大。我习惯用 1.25 作为概率因子，这样平均每 4 个节点升一层。
- 内存池：跳表节点用内存池分配，避免频繁 malloc/free。我曾经见过一个系统，不用内存池时，跳表性能比红黑树还差——因为内存分配的开销太大了。
- 预分配：如果订单簿深度已知（比如最多 10000 层），可以预分配好所有节点，这样插入时就是 O(1) 的。
一个简单的跳表实现片段
// 跳表节点
struct SkipListNode {
double price; // 价格
uint64_t order_id; // 订单ID
uint32_t volume; // 数量
SkipListNode** next; // 指向下一层的指针数组
int level; // 当前节点层数
};
// 跳表核心
class SkipList {
private:
SkipListNode* head;
int max_level;
double probability;
public:
void insert(double price, uint64_t order_id, uint32_t volume) {
// 1. 随机生成层数
int level = random_level();
// 2. 从最高层开始查找插入位置
SkipListNode* current = head;
SkipListNode** update = new SkipListNode*[max_level + 1];
for (int i = level; i >= 0; i--) {
while (current->next[i] != nullptr &&
current->next[i]->price < price) {
current = current->next[i];
}
update[i] = current;
}
// 3. 创建新节点并插入
SkipListNode* new_node = create_node(price, order_id, volume, level);
for (int i = 0; i <= level; i++) {
new_node->next[i] = update[i]->next[i];
update[i]->next[i] = new_node;
}
}
};
为什么交易所最终选择了跳表？
其实原因很简单：工程上的综合表现最优。
红黑树和 AVL 树在理论复杂度上并不输给跳表，但在实际工程中，跳表的内存局部性、实现简单度、并发友好度这三个优势太明显了。
我见过一个极端案例：某交易所用红黑树做订单簿，结果在行情快照重建时，因为红黑树的遍历性能太差，导致快照生成时间超过了 100 毫秒。换成跳表后，直接降到了 20 毫秒以内。
你想想看，100 毫秒的延迟，在交易所里意味着什么？可能已经错过了好几个 tick 了。
所以，如果你现在要设计一个订单簿系统，我个人建议：别犹豫，直接上跳表。除非你有非常特殊的理由（比如必须用现成的 STL 容器），否则跳表是性价比最高的选择。
嗯，以上就是我对这三种数据结构的理解。说白了，选型没有银弹，但在订单簿这个特定场景下，跳表确实是最优解。希望这些经验能帮你少走一些弯路。