撮合引擎的核心数据结构应该怎么设计？

考察意图

• 考察候选人是否能从操作需求反推数据结构。
• 考察是否理解新增、成交、撤单、查询最优价的复杂度要求。

答题思路

1. 先列出撮合需要支持的核心操作。
2. 再给出价格层、订单队列和 orderId 索引。
3. 补充最优价缓存和快照恢复。

参考答案

订单簿至少要支持：找到最优买卖价、追加限价单、按价格成交、按 orderId 撤单、生成行情深度。

常见设计是价格层使用平衡树、跳表或有序 Map。买盘按价格降序，卖盘按价格升序。同一价格层内部使用 FIFO 队列或双向链表。为了快速撤单，需要维护 orderId 到订单节点的哈希表。

Best Bid 和 Best Ask 可以通过树的首尾节点获得，也可以额外缓存。系统还需要能定期生成快照，并配合命令日志或成交日志重放恢复。

加分追问

• 撤单高频时，如果没有 orderId 索引，只靠遍历价格层会非常慢。