3. 订单簿数据结构选型
在逐笔事件重建订单簿时，最先要做的工程决策不是“用哪个库”，而是“订单簿在内存里到底长什么样”。这个决策直接决定了重建精度、内存占用、更新延迟，以及后续策略能拿到什么粒度的信息。本节围绕两条主线展开：价格档位聚合（Price Level Aggregation）与订单级队列（Order-Level Queue），并给出常见数据结构的对比与选型依据。
两种建模粒度：聚合档位 vs 订单级队列
价格档位聚合把同一价格上的所有挂单合并为一个档位，只保留该价位的总量与订单数量。例如买一价 100.02 上共有 3 笔订单、合计 850 股，聚合模型只记录 (100.02, 850, 3)。它的优点是结构简单、内存小、撮合与盘口计算快；缺点是丢失了队列内部顺序，无法回答“排在我前面的还有多少量”“某笔撤单具体撤的是哪一档的哪一笔”。
订单级队列为每一笔挂单保留独立节点，记录订单号、方向、价格、剩余数量、进入时间（或队列序号），并按价格档位组织成 FIFO 队列。它能精确还原队列位置、支持逐笔撤单与成交归属，是研究队列位置、订单簿不平衡、微观结构信号的必备粒度。代价是节点数量大、指针跳转多、内存与缓存压力显著上升。
关键认识是：两者不是互斥的。工程上常见做法是订单级为主存储、聚合档位为派生视图——用订单级队列保证精度，用增量维护的聚合档位保证盘口查询的 O(1) 访问。选型的本质是决定“谁是真相源、谁是缓存”。
常见数据结构对比
订单簿的核心操作有四类：按价格定位档位、档位内追加/删除订单、按订单号查找并修改订单、按价格有序遍历盘口。不同结构对这四类操作的支持差异很大。
| 结构 | 价格定位 | 档内增删 | 订单号查找 | 有序遍历 | 内存/缓存 | 适用场景 |
|---|---|---|---|---|---|---|
| 定长数组（价格映射下标） | O(1) | O(1) 追加 | 需哈希表 | 需扫描 | 大但连续 | 价格范围窄、tick 固定的品种 |
| 哈希表 + 双向链表 | O(1) 平均 | O(1) | O(1) 平均 | 需额外排序结构 | 指针多、碎片化 | 订单级队列的通用实现 |
| 平衡树（红黑树/跳表） | O(log n) | O(log n) | 需哈希表 | O(log n) 定位 + 顺序遍历 | 节点开销中等 | 档位多、需频繁取最优 N 档 |
| 数组 + 有序索引（堆/跳表） | O(1) 数组 / O(log n) 索引 | O(1) 追加 | 哈希表 | 索引有序 | 较优 | 聚合档位视图的高性能实现 |
需要强调：上表的复杂度是渐近意义下的，真实性能还取决于常数因子与内存局部性。订单级队列若用“哈希表 + 每档双向链表”，单次更新是若干次随机内存访问；而聚合档位若用“价格下标数组”，更新几乎全在连续内存上，缓存命中率高出一个量级。这就是为什么很多低延迟系统在撮合侧用聚合、在分析侧才展开订单级。
选型依据：从需求反推结构
选型不应从“哪种结构更高级”出发，而应从四个问题反推：
- 精度需求：是否需要还原队列位置、逐笔撤单归属、单笔成交对应的挂单？需要则必须保留订单级节点，聚合档位只能作为派生视图。
- 查询模式：主要是取最优 N 档盘口，还是要遍历全簿、统计档位分布？前者偏向“数组 + 有序索引”，后者偏向平衡树或跳表。
- 更新频率与事件类型：逐笔委托/成交/撤单混合高频时，订单号到节点的映射必须是 O(1)，否则每次撤单都要线性搜索，延迟不可接受。
- 内存与品种规模：价格范围窄、tick 固定（如某些期货合约）适合定长数组；价格范围宽、档位稀疏（如多档位股票）适合哈希或树结构。
一个可落地的混合结构示例
下面给出一个教学用的混合结构设计（参数为示例假设，非实测）：以订单级队列为真相源，聚合档位为增量维护的派生视图。
// 订单级节点（真相源）
struct OrderNode {
uint64_t order_id;
Side side; // 买/卖
int64_t price; // 以最小价格单位表示的整数
uint64_t qty; // 剩余数量
uint64_t seq; // 进入队列的序号，用于 FIFO
OrderNode *prev, *next; // 同档位双向链表
};
// 聚合档位（派生视图）
struct PriceLevel {
int64_t price;
uint64_t total_qty; // 该档位总量
uint32_t order_cnt; // 该档位订单数
OrderNode *head, *tail; // 指向订单级队列首尾
};
// 顶层容器
unordered_map<uint64_t, OrderNode*> id_index; // 订单号 -> 节点
map<int64_t, PriceLevel> bid_levels, ask_levels; // 价格 -> 档位（有序）更新逻辑的关键点：新增委托时，先在 id_index 插入节点，再按价格找到或创建 PriceLevel，把节点追加到该档位链表尾部，同时累加 total_qty 与 order_cnt；撤单时通过 id_index O(1) 定位节点，从链表摘除并扣减档位统计，若档位订单数归零则从有序 map 中删除该价格；成交时按剩余数量扣减，部分成交只改 qty 与档位总量，全部成交则走撤单路径。这样盘口查询只需读 bid_levels.rbegin() 与 ask_levels.begin()，而队列位置信息始终保留在订单级链表中。
下图展示了该混合结构中“一笔新委托进入买一档”时的数据流向与两个视图的同步关系：
图中实线表示写入路径：委托事件同时写入订单级队列与聚合档位，并通过哈希表建立订单号索引；虚线表示派生视图的增量同步——档位总量与订单数随订单级变化而更新。盘口查询只读聚合视图，队列位置分析只读订单级链表，两条路径互不干扰。
选型中的常见误区
误区一：只建聚合档位就够用。如果策略只关心盘口总量，聚合确实够；但一旦需要做队列位置估计、撤单率分析或成交归属，聚合模型无法回溯，只能事后重建，代价更高。建议在数据接入层就保留订单级事件，聚合视图按需派生。
误区二：订单级队列一定比聚合慢。慢的是“每次查询都遍历链表”。若把订单号索引和档位统计做成增量维护，订单级结构的单次更新也是常数级操作，只是常数因子更大。真正的性能差异来自内存局部性，而非渐近复杂度。
误区三：用一套结构同时承担真相源与查询视图。这会让结构越来越臃肿，更新路径互相牵制。清晰的做法是明确“谁是真相源”，其余结构都是可重建的缓存，重建逻辑本身也是校验数据一致性的好手段。
总结来说，价格档位聚合与订单级队列的权衡，本质是精度与效率的权衡。对逐笔重建类任务，推荐以订单级队列为真相源、聚合档位为派生视图的混合方案；数据结构上以哈希表承担订单号定位、以有序 map 或数组索引承担价格排序，再根据品种的价格范围与更新频率微调具体实现。选型没有唯一答案，但判断依据可以很清晰：先问精度，再问查询，最后问规模。