数据结构选型：数组 vs 链表 vs 跳表 vs 红黑树
订单簿的核心，说白了就是一张价格-数量的映射表。但怎么存这张表，直接决定了你的撮合引擎能扛住多大的压力。我见过不少团队，一开始图省事用数组，结果一到行情爆发就崩。今天咱们把这四种结构掰开揉碎，看看在订单簿场景下，谁才是真正的王者。
一、数组：简单但致命
数组的优点是啥？连续内存，CPU缓存友好，随机访问O(1)。听起来很美对吧？
但订单簿不是静态的。价格档位会不断新增、删除、修改。数组的插入和删除是O(n)的——你想想看，每次撤单都要把后面所有元素往前挪，这谁受得了？
数组唯一能用的地方，是价格档位固定且稀疏度极低的情况。比如某些期货合约只有几十个活跃档位，用数组+位图标记，勉强能跑。但别指望它扛大并发。
二、链表：插入快，查询慢
链表插入是O(1)的，这很诱人。但问题是，订单簿需要按价格排序。链表要找到插入位置，得从头遍历——O(n)。
我个人的习惯是，链表只用在内存池里做空闲节点管理。真正的价格队列，别用链表做主结构。为什么？因为订单簿的查询频率远高于修改频率。你每秒钟可能查几千次最优买卖价，但修改可能只有几百次。链表每次查最优价都得遍历，这太亏了。
三、跳表：工程上的最优解
跳表是我在订单簿项目里用得最多的结构。它本质上是多层链表，用概率平衡代替了红黑树的严格平衡。插入、删除、查询都是O(log n)，而且实现简单，不容易出bug。
我记得有一次做期权做市系统，订单簿需要支持按价格区间批量查询。红黑树要实现区间遍历得写递归，跳表直接沿着底层链表走就行，代码量少了一半。
// 跳表节点示例
struct SkipListNode {
double price; // 价格
uint64_t volume; // 总量
int order_count; // 订单数
std::vector<SkipListNode*> forward; // 各层指针
SkipListNode(double p, int level)
: price(p), volume(0), order_count(0), forward(level + 1, nullptr) {}
};跳表还有个好处：无锁化改造相对容易。我做过一个无锁跳表版本，用CAS操作管理指针，在40核机器上做到了单线程10倍吞吐。红黑树想做无锁？那难度直接翻十倍。
四、红黑树：理论最优，工程噩梦
红黑树插入删除也是O(log n)，而且比跳表更稳定——跳表有概率退化，红黑树不会。但问题在于：
- 实现复杂。你能手写一个无bug的红黑树吗？我反正不能。
- 内存局部性差。每个节点分散在堆里，CPU缓存命中率低。
- 并发改造难。旋转操作涉及多个指针，CAS很难搞定。
我见过一个团队用std::map（红黑树）做订单簿，结果性能瓶颈不在算法复杂度，而在内存分配。每次插入都new一个节点，每次删除都delete，内存碎片化严重。后来换成跳表+内存池，性能直接翻倍。
红黑树唯一不可替代的场景，是需要严格保证最坏情况延迟的场合。比如某些交易所的风控系统，要求每次操作都在1微秒内完成，这时候红黑树的确定性比跳表的概率性更安全。
五、四种结构对比总结
| 特性 | 数组 | 链表 | 跳表 | 红黑树 |
|---|---|---|---|---|
| 插入 | O(n) | O(1)（已知位置） | O(log n) | O(log n) |
| 删除 | O(n) | O(1)（已知位置） | O(log n) | O(log n) |
| 查询 | O(1)（随机） | O(n) | O(log n) | O(log n) |
| 区间遍历 | O(k) | O(k) | O(log n + k) | O(log n + k) |
| 实现难度 | 低 | 低 | 中 | 高 |
| 并发友好 | 差 | 中 | 好 | 差 |
| 缓存友好 | 好 | 差 | 中 | 差 |
六、我的选型建议
嗯，这里直接给结论：
- 做原型验证：用std::map（红黑树），最快出活。
- 做生产系统：用跳表+内存池，性能与可维护性兼顾。
- 做极低延迟系统：用数组+位图（如果价格范围固定），或者定制化跳表。
- 做风控系统：用红黑树，保证最坏情况延迟。
我个人习惯是，先拿跳表跑起来，等性能瓶颈明确了再考虑优化。别一开始就搞红黑树，调试起来太痛苦了。
七、知识体系结构图
这张图总结了我的选型逻辑。从左到右，从简单到复杂。记住一点：没有银弹。每种结构都有它的适用场景，关键是你得清楚自己的业务特征。
公众号:蓝海资料掘金营，微信deep3321