数据结构设计：订单簿的核心选择
做撮合引擎，说白了就是在跟订单簿打交道。
订单簿就是那个记录所有买单卖价的账本。你想想看，每秒可能有几千笔订单砸进来，每一笔都要找到合适的对手方成交。数据结构选错了，系统就卡死了。
我当年第一次做撮合引擎时，就踩过这个坑。当时图省事，直接用了个数组加链表，结果压测到500笔/秒就崩了。后来老老实实研究数据结构，才明白这里面门道有多深。
订单簿的核心需求
我们先理清楚，订单簿到底要干什么：
- 快速插入：新订单进来，要立刻放到正确的位置
- 快速查询：找到最优的买价和卖价
- 快速删除：订单撤销或成交后，要能迅速移除
- 范围查询：比如查询某个价格区间内的所有订单
嗯，这几个需求，不同的数据结构表现天差地别。
三种主流数据结构对比
| 数据结构 | 插入 | 查询最优 | 删除 | 范围查询 |
|---|---|---|---|---|
| 红黑树 | O(log n) | O(log n) | O(log n) | O(log n + k) |
| 跳表 | O(log n) | O(log n) | O(log n) | O(log n + k) |
| 优先队列 | O(log n) | O(1) | O(n) | 不支持 |
看到没？优先队列查最优价最快，但删除和范围查询就拉胯了。红黑树和跳表各方面都比较均衡。
我的建议：生产环境用红黑树或跳表。优先队列只适合做演示或极简场景。
红黑树：最稳妥的选择
红黑树是平衡二叉搜索树的一种。它保证了最坏情况下操作也是O(log n)。
我习惯用红黑树做价格维度的索引。每个价格节点下面挂一个订单链表，这样价格排序和订单管理就分开了。
// 伪代码示例：红黑树 + 价格队列
class PriceNode {
double price;
OrderList orders; // 该价格下的订单链表
Color color; // 红黑树节点颜色
PriceNode left, right, parent;
}
class OrderBook {
RedBlackTree<PriceNode> buyTree; // 买单红黑树
RedBlackTree<PriceNode> sellTree; // 卖单红黑树
}这里有个细节：红黑树的旋转操作在并发场景下要小心。我遇到过因为旋转时没加锁，导致两个线程同时修改树结构，直接挂了。后来改成了读写锁分离才解决。
跳表：并发友好的替代方案
跳表本质上是个多层链表。它用概率来保证平衡，而不是像红黑树那样用旋转。
为什么说跳表并发友好？因为它的修改操作是局部性的，只需要锁住相邻的几个节点就行。红黑树的旋转可能影响整棵树。
// 跳表节点结构
class SkipListNode {
double price;
OrderList orders;
SkipListNode[] forward; // 不同层的指针
int level; // 节点层数
}经验之谈：如果你的撮合引擎是单线程的，红黑树完全够用。如果是多线程的，跳表可能更省心。
价格队列与时间优先队列
光有价格排序还不够。同一个价格下，订单还要按时间排序。这就是价格队列和时间优先队列的组合。
价格队列的结构很简单：
class OrderList {
Order head; // 链表头
Order tail; // 链表尾
int count; // 订单数量
}
class Order {
long orderId;
long timestamp;
long quantity;
Order prev, next;
}时间优先队列，说白了就是先进先出。同一个价格，先来的订单先成交。这个用链表实现最合适，插入到尾部O(1)，从头部取出也O(1)。
注意：时间戳的精度问题。我曾经遇到过两个订单在同一微秒到达，结果时间戳一样，导致排序出问题。后来我改用全局自增序列号来保证时间顺序。
整体架构图
下面这张图展示了订单簿的核心结构：
实际选型建议
说了这么多，到底怎么选？我给出几个场景：
- 单线程撮合引擎：红黑树 + 链表。简单可靠，性能足够。
- 多线程撮合引擎：跳表 + 链表。并发性能更好。
- 极高频交易：可以考虑用数组 + 价格分桶。牺牲灵活性换速度。
- 学习演示：优先队列 + 链表。代码简单，容易理解。
一个小技巧：不管用哪种数据结构，记得把价格和订单分开存储。价格用树或跳表索引，订单用链表管理。这样修改订单时不用动树结构，效率高很多。
嗯，数据结构这块就聊这么多。记住一句话：没有最好的数据结构，只有最适合你场景的。选之前，先想清楚你的瓶颈在哪里。