限价订单簿高性能实现：基于二叉树与哈希表的算法与数据结构解析

这是国外网站一篇发表于2011年的经典技术文章，深入探讨了如何构建一个高速的限价订单簿（Limit Order Book, LOB）。限价订单簿是交易系统最核心的组件之一，其选用的数据结构将直接为交易模型提供市场信息，因此，确保其绝对正确和极致的速度至关重要。

为了让大家对数据规模有个直观感受，以纳斯达克 TotalView ITCH 数据流为例，它包含了纳斯达克交易的所有工具（股票等）的每一个事件，每日数据量可达 20+ GB，峰值速率超过 3 MB/s。每条消息平均约20字节，这意味着在高流量时段，系统每秒需要处理 10万至20万条 消息。

限价订单簿的核心操作

一个限价订单簿必须实现三个主要操作：添加（Add）、取消（Cancel） 和 执行（Execute）。设计的目标是在 O(1) 时间复杂度内完成这些操作，同时让交易模型能高效地查询诸如：

• “当前最佳买价（Bid）和卖价（Offer）是多少？”
• “价格A到价格B之间有多少成交量？”
• “订单X目前在订单簿中的排队位置？”

在订单簿活动中，做市商为争夺有利位置而产生的添加和取消操作占绝大多数，成交（执行）操作则相对较少。一个添加操作会将订单置于某个特定限价（价格）的订单队列末尾；取消操作可以从订单簿中任意位置移除一个订单；而执行操作则会从订单簿的“内部”（Inside）移除订单——内部定义为最高买价中的最早买单，或最低卖价中的最早卖单。这些操作都基于一个唯一的订单ID（如下方伪代码中的 Order.idNumber），因此，使用哈希表来追踪订单是一个很自然的选择。

数据结构设计

根据订单簿预期的稀疏性（即相邻有成交量的价格之间的平均距离，通常与标的物价格正相关），可以有不同的实现细节。首先，我们定义几个核心对象：

Order
int idNumber;
bool buyOrSell;
int shares;
int limit;
int entryTime;
int eventTime;
Order* nextOrder;
Order* prevOrder;
Limit *parentLimit;

Limit // 代表一个具体的限价（价格水平）
int limitPrice;
int size;
int totalVolume;
Limit *parent;
Limit *leftChild;
Limit *rightChild;
Order* headOrder;
Order* tailOrder;

Book
Limit *buyTree;
Limit *sellTree;
Limit *lowestSell;
Limit *highestBuy;

核心思想是：构建一个按 limitPrice 排序的 Limit 对象二叉树，而每个 Limit 对象自身又是一个 Order 对象的双向链表。

• 买单和卖单的 Limit 应该存放在两棵独立的树中，这样订单簿的内部（即最佳买卖价）就分别对应买单树的最大值和卖单树的最小值。
• 每个 Order 同时也是以 idNumber 为键的映射表（如哈希表）中的一个条目。
• 每个 Limit 同时也是以 limitPrice 为键的映射表中的一个条目。

操作性能分析

凭借这种结构，你可以高效地实现以下关键操作：

• 添加 (Add) – 对于某个价格水平的第一个订单，时间复杂度为 O(log M)，之后的所有订单为 O(1)
• 取消 (Cancel) – O(1)
• 执行 (Execute) – O(1)
• 获取某价位成交量 (GetVolumeAtLimit) – O(1)
• 获取最佳买卖价 (GetBestBid/Offer) – O(1)

其中，M 代表不同价格水平（Limit）的数量（通常远小于订单总数 N）。由于市场订单的特性，订单会从树的一侧移除，同时添加到另一侧，因此需要采用某种策略来保持限价树的平衡。请记住，当删除一个 Limit 节点时，必须能够在 O(1) 时间内更新 Book.lowestSell 和 Book.highestBuy（这正是每个 Limit 都包含一个 *parent 指针的原因），这样才能保证 GetBestBid/Offer 操作始终是 O(1)。

设计方案变体与实现细节

此结构的一种变体是使用稀疏数组而非树来存储 Limit。这将使所有添加操作都变为 O(1)，但代价是当内部价格水平的最后一个订单被删除或执行时，更新 Book.lowestSell/highestBuy 可能需要 O(M) 的时间（尽管对于非稀疏订单簿，实际性能通常远好于 O(M)）。如果你将 Limit 存储在稀疏数组中并以链表串联，那么添加操作又变回 O(log M)，而删除/执行操作保持 O(1)。这些都是很好的实现方案，最佳选择主要取决于订单簿的稀疏性。

通常，明智的做法是使用批量内存分配。如果使用像 Java 这样的垃圾回收语言，则需要为这些实体使用对象池。只要不让垃圾收集器运行，Java 也可以做到足够快以满足高频交易的需求。

关于如何安全、稳健地在多线程环境中提供对订单簿数据的访问，将是另一个话题。

实例解析与时间复杂度理解

为了更好地理解，我们举个例子。假设某股票订单簿如下：

买方 (Bids):

• 102元：150股
• 101元：200股
• 100元：100股

卖方 (Asks):

• 99元：50股
• 100元：150股
• 101元：100股

买卖双方各有3个不同的限价，总计 M=6。

1. 添加一个新买单，限价103元：这是一个新的价格水平，需要在买单的 Limit 二叉树中插入一个新节点。这是一个 O(log M) 的操作，即 O(log 6) ≈ 3 次比较。
2. 在已存在的101元价位添加一个买单：直接将其加入101元 Limit 节点的订单链表末尾，这是一个 O(1) 的操作。
3. 取消一个订单：通过订单ID在哈希表中直接定位到对应的 Order 节点，然后从其所属的 Limit 链表中移除。哈希表查找和链表节点删除都是 O(1)。
4. 执行一笔成交：找到 Book.highestBuy（例如102元）或 Book.lowestSell（例如99元）指向的 Limit，从其链表头部取出订单执行。由于 highestBuy/lowestSell 指针已缓存，这也是一个 O(1) 的操作。

结语

本文详细介绍了构建高性能限价订单簿的核心思想。其关键在于结合哈希表的快速查找和二叉树/链表的高效有序管理，在内存布局和指针操作上精心设计，从而满足金融极速场景下的严苛性能要求。理解和实现这样的底层系统，对于深入系统架构和高性能编程至关重要。如果你对如何具体实现文中提到的某些操作有疑问，欢迎在云栈社区的技术板块深入探讨。