数据结构设计：订单簿的底层数据结构

聊到订单簿的底层实现，我脑子里第一个蹦出来的问题就是——用什么数据结构来存这些挂单？

你可能觉得这有啥好纠结的，不就是存一堆价格和数量嘛。但实际做量化交易系统的时候，你会发现这个选择直接决定了你的撮合引擎能跑多快。我在早期做的一个回测系统里，就吃过这个亏。当时图省事用了普通的数组，结果订单一多，插入和删除操作直接把CPU干到100%。嗯，从那以后我再也不敢轻视数据结构的选择了。

三种主流方案：红黑树、跳表、哈希表

目前业界做订单簿底层存储，主要就这三种路子。咱们一个一个来看。

1. 红黑树（Red-Black Tree）

红黑树说白了就是一种自平衡的二叉查找树。它保证在最坏情况下，插入、删除、查找的时间复杂度都是 O(log n)。

为什么适合订单簿？

• 订单簿需要按价格排序（买盘从高到低，卖盘从低到高）
• 需要快速找到最优买卖价格（即盘口的最高买价和最低卖价）
• 需要频繁插入和删除订单

红黑树天然支持有序遍历，你想想看，要找到最优价格，直接取最左或最右节点就行了，多方便。

我在项目中遇到过一个问题：C++ STL 里的 std::map 底层就是红黑树，但直接用的时候要注意，它默认按 key 升序排列。对于卖盘（ask）这没问题，但买盘（bid）需要降序排列，你得传一个自定义比较器。

// 卖盘：价格升序排列（默认）
std::map<double, OrderList> askBook;

// 买盘：价格降序排列
std::map<double, OrderList, std::greater<double>> bidBook;

2. 跳表（Skip List）

跳表这玩意儿，我第一次看到的时候觉得挺神奇的。它本质上就是链表加多层索引。你想想看，普通链表查找是 O(n)，但跳表通过随机建索引，把查找效率提升到了 O(log n)。

跳表 vs 红黑树：

对比维度	红黑树	跳表
实现复杂度	高（旋转、变色逻辑复杂）	低（纯链表操作）
并发性能	差（需要全局锁）	好（可以分段加锁）
范围查询	好（中序遍历）	好（链表遍历）
内存占用	低（每个节点2个指针）	较高（多层索引指针）

我个人习惯在需要高并发读写的场景下用跳表。比如做高频交易系统时，多个线程同时操作订单簿，跳表的分段锁机制比红黑树的全局锁要友好得多。

// 跳表节点的简单定义
struct SkipListNode {
    double price;
    OrderList orders;
    std::vector<SkipListNode*> forward; // 各层的前向指针
    int level; // 当前节点层数
};

3. 哈希表（Hash Table）

哈希表？你可能觉得奇怪——哈希表不是无序的吗？订单簿不是需要按价格排序吗？

没错，纯哈希表确实不适合直接做订单簿的主数据结构。但它在某些场景下非常好用。

哈希表的用武之地：

• 按订单ID快速查找/撤销订单
• 存储订单的辅助索引
• 配合有序结构一起使用（比如红黑树+哈希表的混合方案）

我曾经在一个项目里用过「红黑树 + 哈希表」的双索引方案。红黑树负责价格排序，哈希表负责订单ID的快速定位。撤销订单时，先通过哈希表找到订单所在的价格节点，再在红黑树里删除。这样既保证了有序性，又实现了 O(1) 的订单查找。

// 双索引方案示意
struct OrderBook {
    // 价格索引（红黑树）
    std::map<double, OrderList, std::greater<double>> bidTree;
    std::map<double, OrderList> askTree;
    
    // 订单ID索引（哈希表）
    std::unordered_map<uint64_t, OrderInfo> orderIndex;
};

我的选择建议

说了这么多，到底该用哪个？我个人的经验是这样的：

• 做回测系统或低频交易： 红黑树就够了。实现简单，性能稳定，C++/Java/Python 都有现成的库。
• 做高频交易或实时撮合： 优先考虑跳表。并发性能好，而且实现起来比红黑树容易得多。
• 需要快速撤销订单： 一定要加哈希表做辅助索引。别问我怎么知道的——我早期那个回测系统就是撤销订单时遍历整个树，慢得让人崩溃。

知识体系结构图

下面这张图展示了订单簿底层数据结构的核心逻辑和选择路径：

---

公众号:蓝海资料掘金营，微信deep3321