订单簿数据结构的选择

订单簿是撮合引擎在每一条消息上都要触碰的那个数据结构。它的形态决定了你的 p50——更重要的是，决定了你的 p99。本页讲的就是如何选择它：不是按教科书上的 Big-O，而是按每种方案在热路径上、在真实订单流下、在真实硬件上的实际表现。

先亮结论：没有放之四海而皆准的赢家。 正确的选择取决于你订单簿的形态——价格带有多宽、价位被填得有多密、每个价位上排了多少单。快速订单簿领域的经典参考正是这么说的：最佳选择「主要取决于订单簿的稀疏程度」。¹ 流动性就是这个稀疏程度，所以我们在下文专门给它开了一节。

每个订单簿都是同样的三样东西

比较结构之前，先固定解剖结构。无论你选哪种，一个限价订单簿都是三个协作的部件：

价位索引（price-level index）——把价格映射到坐落在该价格上的价位。这就是本页要选的那个结构。 数组、树、跳表、链表、hash 还是基数树——它们都只是回答同一个问题的不同方式：「价格 P 上的价位在哪里，此刻的最优价又是多少？」
每个价位一条 FIFO 队列——价格-时间优先意味着每个价位是一条先进先出的挂单队列。它几乎总是一条双向链表的订单节点，而且无论上面选哪种索引，它都一样。
order-ID → order 映射——一张 hash 表（或者交回给客户端的一个 intrusive 指针），能在 O(1) 内定位任意挂单，无需遍历订单簿。这就是让撤单/改单变便宜的东西，它同样与价位索引无关。

部件 2 和 3 基本是固定的。整个设计决策就在部件 1——而它之所以微妙，原因在部件 3 的负载，下面就说。

承重约束：撤单占主导

关于真实订单流最重要的一个事实是：它压倒性地是撤单，而不是成交。在美国股票市场，97% 的订单在成交之前就被撤销了。² 挂单-撤单的翻搅——来自做市和报价算法不停地重新报价——比成交多出一个数量级不止。

这重塑了对结构的优先级排序：

撤单/改单必须是 O(1)。 这正是 order-ID 映射存在的理由：你从不搜索要撤的那张单；你直接跳到它的节点上把它摘链。下面每种结构都继承了这一点，所以撤单成本在它们之间基本是个常数——真正的区分点是 插入（insert） 和 最优价（best-price） 的成本。
插入是真正会变化的热操作。 新挂单不断到达，必须找到（或创建）它的价位。这里就是价位索引挣钱或赔钱的地方。
最优买价/最优卖价几乎在每条消息上都被读取（用来判断是否成交）。它必须是 O(1)——对下面每种结构而言，这意味着缓存最优价并增量维护，绝不重新搜索。

读下面的比较时，把这个排序记牢——撤单 O(1)（既定）、插入要便宜、最优价要缓存。

六个候选

结构	核心思想	最优/插入/撤单	随订单簿规模的成本	流动性适配
直接索引数组（价格网格）	预分配、按 tick 索引的数组；每个格子是一个价位的 FIFO 队列	O(1) / O(1) / O(1)	受配置的价格带宽度限制——基本为常数	窄带、密集——固定 tick 的流动性好的交易对
平衡二叉搜索树（红黑 / AVL）	每个活跃价位一个树节点	O(1)* / O(log L) / O(1)	随活跃价位数呈 log L 增长	宽带、稀疏——通用
跳表 / 混合	多层索引：先粗查，再短距线性扫描	O(1)* / O(log L) / O(1)	亚线性；随订单簿加深缓慢增长	非常深 / 稀疏的订单簿
链式价位 + 辅助索引	双向链表的价位 + 一张 map/数组用于定位价位节点	O(1) / 近顶部 ~O(1)，深处最坏 O(L)	热路径成本基本与总深度无关	任意带宽，活跃度集中在顶部
Hash map + heap/tree	hash `price → level`；另用一个 heap/tree 追踪最优价	O(1)* / O(log L) / O(1)	取决于负载因子 + log L	不规则 / 稀疏的价格网格
自适应基数树（ART）	对定宽整数 tick 建基数树；节点扇出随占用率自适应（4/16/48/256）	O(1)* / O(k) / O(1)	受键宽 k 限制，与价位数无关	自适应——密集区域趋近数组，稀疏区域保持紧凑

*最优价在所有情况下都是 O(1)，仅仅因为你缓存并增量维护了 min/max。L = 活跃价位数（它 << 订单数）；k = 价格键的固定字节宽度（64 位 tick 时 ≤ 8），所以 O(k) 是一个硬性的常数上界，而不是订单簿规模的函数。

1. 直接索引数组（价格网格）

预分配一个覆盖某价格带的扁平数组；用 (price − floor) / tick 来索引。该索引处的格子存放这个价位的 FIFO 队列。插入、撤单、最优价全都变成 O(1) 的数组索引。¹ 没有搜索、没有再平衡、没有指针追逐——而且因为数组是连续的，它对缓存极其友好（见下文机械同感）。

代价是内存和有界性：不管价位有没有被填，你都要为整个带宽付费，而带外的价格需要一条兜底路径。经典的快速订单簿文章指出，纯数组变体「对 add 操作永远给出 O(1)，代价是让内侧价位上最后一张单的删除/成交变成 O(M)」——除非你也增量追踪最优价位，而这你确实会做，靠的就是那个缓存的最优价指针。¹ 对一个在已知、固定 tick 上流动性好的标的——典型的现货加密交易对——这往往是存在的最快结构。³

2. 平衡二叉搜索树（红黑 / AVL）

每个活跃价位一个节点，保持有序。插入或移除一个价位是 O(log L)；如果你缓存了 min（卖侧）/ max （买侧）节点并在移除时刷新，最优价就是 O(1)。这是教科书设计，也是最通用的——它能处理任意稀疏、无界的价格，无需配置带宽。在 C++ 里，std::map 是一棵红黑树，其搜索/插入/删除都是对数级，⁴ 它也是无数引擎的默认首版实现。

它的弱点是机械层面的，而非渐进复杂度：树节点散布在堆上，所以每次插入都要从根到叶跨越多条缓存行做指针追逐，再平衡的写入还会碰更多。在微突发下这会造成尾延迟尖刺——一份对标准「链表串在平衡树上」设计的分析把尖刺归因于恰好两项成本：「为到达插入点而做的指针追逐遍历，以及为定位目标价位而做的从根到叶的搜索」。⁵ 理论干净，但对深订单簿它会伤害 p99。

3. 跳表 / 二分-线性混合

跳表通过堆叠的「快车道」给出概率意义上的 O(log L) 搜索，然后做一次短距的局部扫描。有些引擎用一种混合：先粗查到一个价格带，再对该带里那寥寥几个价位做线性扫描。它的吸引力在于亚线性成本，且随订单簿变得非常深时退化平缓，并发也比平衡树简单。

实践中它有和树一样的软肋——快车道仍然是指针，所以它照样追逐缓存行——而且专门的、有基准数据的跳表订单簿在文献里出奇地少。把它当作一个对非常深/稀疏订单簿站得住脚的 O(log L) 选项，但别指望它在热路径延迟上赢过调优过的数组。³

4. 链式价位 + 辅助索引

把价位保持成一条双向链表（每个价位知道它的邻接价位），外加一张辅助 map 或数组用于直接跳到某个价位节点。最优价附近的操作是 ~O(1)——你本来就在链表头部——但在没有索引的情况下要够到订单簿深处的某个价位，是一次 O(L) 的行走。由于订单活跃度聚集在内侧，热路径基本与总深度无关。这本质上就是经典快速订单簿设计所描述的结构：一条有序的价位链表，每个价位一条 FIFO 队列，外加一张 price → level 的 map 作为索引，避免那次深度行走。¹ 它高度依赖 free-list 和精细的指针/节点池管理来保持零分配。

5. Hash map 按价格 + heap/tree

用 hash price → level 做期望 O(1) 的价位查找，再单独维护一个 heap（或 tree）以每次更新 O(log L) 追踪最优价。撤单靠 ID 映射仍是 O(1)。它对那种数组会浪费内存、又不需要树的有序性的不规则或非常稀疏的价格网格很灵活。

它之所以在最严格的热路径上罕见，是因为一种你无法调度的开销：hash 有可变的延迟和缓存未命中行为，而 heap 只给你单个最优价——不给你当一张可成交订单扫穿多个价位时所需的那片有序邻域。这是工程判断，不是被引用的定律，但这就是为什么热路径设计倾向于甩掉 hash/heap 的间接层，转向数组或 intrusive 链式价位。

6. 自适应基数树（Adaptive Radix Tree，ART）

对价格的定宽整数表示建一棵基数（前缀）树，外加让它变得实用的那个关键改动：每个内部节点会根据实际持有的子节点数量自适应地调整大小（Node4 → Node16 → Node48 → Node256），而路径压缩（path compression）加惰性展开（lazy expansion）消除了普通 trie 在稀疏键上浪费的那些单子链。⁶ 因为价格 tick 是定宽键，每个操作的成本都是键字节长度的 O(k)——64 位 tick 最多 8 次字节跳转， 与存在多少价位无关——而且键保持按位字典序，所以 min/max、范围扫描、「沿最优价的有序邻域行走」全都原生可用——恰好是 hash+heap 组合难以提供的那些有序操作。⁶

ART 在这里配得上一席之地的原因，是它能横跨下文的各个流动性分档自我适应，而不是只押一端：

在订单簿的密集区域，热节点会长成 Node256——字面上就是一个按下一个键字节索引的 256 槽数组—— 于是查找退化趋近直接索引数组的单次查表行为。⁶
在稀疏区域，小节点类型加路径压缩让内存与活跃价位数成比例（论文证明了每键最坏 52 字节的上界），而价格网格数组要为整条空带付费。⁶

旗舰实现是 exchange-core，一个开源 Java 撮合引擎：它的 OrderBookDirectImpl 用一个定制的 LongAdaptiveRadixTreeMap 同时索引买卖双侧的价位桶和 order-ID 映射；其 README 报告约 5M ops/s，在 1M ops/s 下 p50 ≈ 0.5 µs / p99 ≈ 4 µs——数字是自报的，但实现是开源可读的。⁷ 诚实的告诫：ART 订单簿在实践中很少见——一个知名引擎及其分支，而非行业默认——而且 ART 在节点之间仍然要追逐指针，所以在一条小而密、范围已知的价格带上，它部分模仿的那个扁平数组仍是需要击败的对象。

流动性如何决定选择

上面的一切归结为一个问题：你的流动性长什么样？ 流动性不是单个数字——它是三个相互独立的杠杆，每个都推向不同的结构。把这三个搞对，选择自然浮现。

三个杠杆

价格带宽度 = (最高价 − 最低价) / tick = 可能的价格槽位数量。这就是数组的全部成本模型：窄带（一个钉在稳定价格附近、tick 较粗的流动性好的交易对）是一个又小又便宜的网格；宽带（一个报到八位小数的低单价代币，或一个大幅波动的远期标的）是一个大部分为空的巨大网格。数组的内存是 O(带宽)，与实际被填了多少价位无关。
价位密度 / 占用率 = 活跃价位数 L 相对带里可能槽位数之比。密集的订单簿在顶部附近填满了大多数槽位；稀疏的订单簿把寥寥几个价位散布在一个很宽的区间上。树和跳表的成本是 O(log L)——它们根本不关心带宽，只关心实际存在多少价位。这正是经典参考里说的「订单簿的稀疏程度」那条轴。¹
每带订单数（每价位队列深度） = N / L，订单数除以活跃价位数。当很多订单堆在同一个价格上时，即便订单总数 N 很大，L 仍然很小——而由于价位索引的成本是 L 的函数，深队列让每种结构的索引都变便宜（工作转移进了每价位的 FIFO 里，而它的操作全是 O(1)）。当每个价位只挂一两张单时，L 会朝 N 膨胀，此时占主导的就是索引结构的每价位成本。这就是为什么该领域的经验法则是 L << N（价位数远少于订单数）：¹ 它挂得越深，你的索引选择就越不重要。

分档矩阵

流动性分档	带宽	价位数 (L)	每价位订单	最佳适配	原因
深而窄——流动性好的加密对，固定 tick	窄	少而密	高	直接索引数组	又小又密的网格 → O(1) 且零指针追逐；队列深度让 L 极小
薄而宽——冷门标的，多位小数，长尾	宽	少但分散	低	平衡树 / 跳表	数组会是一个巨大、大部分为空的网格；`O(log L)` 无视带宽
顶部突发——内侧大量挂/撤翻搅	任意	深尾、热顶	混合	链式价位 + 辅助索引	热路径待在最优价 → ~O(1)；很少触碰的尾部可以很深
大量浅订单簿——一个 cluster 托管上百个薄订单簿	各异	各自都小	低	每个订单簿用紧凑的树 / hash	每订单簿内存占主导；每标的一个数组网格会 ×N 倍浪费内存
混合 / 变动——内侧密集、尾部稀疏，或流动性会迁移	任意	随时间变化	混合	自适应基数树（ART）	节点大小按区域自适应：密集的顶部 ≈ 数组（Node256），稀疏的尾部保持紧凑；O(k) 上界始终成立

当作决策来读

窄带 + 密集（固定 tick 上流动性好的现货加密对）：数组完胜。「对某些市场（比如加密货币，或者价格区间已知的特定品种），一个简单的基于数组的方案可能比树更快。」³ 为了通用性从 std::map 起步的真实实现，一旦确定区间有界，往往会迁移到扁平数组。
宽带 + 稀疏（远期期权、报到多位小数的冷门标的）：树或跳表配得上它的 log 因子。它们的成本跟着 活跃价位走，而不是带宽，所以一个横跨巨大价格区间、却始终只有几十个活跃价位的订单簿依然便宜——而数组会分配（并在其上不断缓存未命中）一个巨大、大部分为空的网格。
无论带宽如何，每价位订单数都很高会让 L 保持很小，这会讨好每一种结构，并拉大数组的领先（小网格、深 O(1) 队列）。每价位订单数很低（大量薄价位）才是惩罚数组内存、奖励对数级结构的情形。
活跃度集中在顶部、无论尾部多深：链式价位 + 索引让热路径接近 O(1)，同时容忍一条很少被触碰的深尾。
无法承诺单一分档——内侧密集、尾部稀疏，或订单簿形态随流动性变化：ART 用一个结构覆盖两端，代价是纯数组永远不用付的那几次指针跳转。它也是对下面那条警告的一个务实回应——波动跳空不会像冲破固定带宽那样冲垮它。

为什么实践中数组能赢过树

上面反复出现的主题——数组和 intrusive 链表在 Big-O 相等甚至更差的情况下仍然获胜——就是机械同感 （mechanical sympathy）：写与硬件配合的软件，这个原则由 HFT 工程师 Martin Thompson（LMAX Disruptor 的作者）发扬光大。⁸ 核心事实：

CPU 以缓存行（通常 64 字节）为单位搬运内存，而硬件预取器奖励可预测的顺序访问。⁸ 一个连续的价位数组会成串地流入缓存；一棵散布在堆上的树节点则挫败预取器，把每一跳都变成一次潜在的缓存未命中。
Big-O 数的是操作数，不是缓存未命中数。对一个热订单簿实际持有的规模，对连续内存做线性扫描往往能赢过一个「更快」的基于指针的结构——对数级结构反超的交叉点可能出奇地大，并且高度依赖元素大小和访问模式。

这正是本站其余部分为 NUMA 与缓存局部性和核隔离所做的同一论证：在热路径上，消除方差比削掉一个渐进因子更重要。树的 O(log L) 是真实的，但真正出现在你 p99 里的，是它的缓存未命中。

如何映射到 Aeron Cluster

在一个 clustered 撮合引擎上，订单簿住在一台单一的确定性状态机里——即每标的一个 actor。这个模型直接带来两个后果：

单写者意味着不需要并发结构。 因为恰好一条线程拥有一个订单簿并按序处理 replicated log，你永远不需要上面任何结构的无锁或并发变体。你可以挑选最快的单线程布局——这正是数组的机械同感优势对你可用的原因。 Aeron® Cluster 的单写者纪律是使能者，而非约束。
快照会序列化整个订单簿。 Cluster 快照会走遍每个常驻订单簿里的每一张挂单，所以你结构的大小和遍历成本也会变成一项快照时间与恢复时间的成本——这是紧凑、连续布局划算的又一个理由，也是一个宽而稀疏的数组网格伤人的又一个理由。关于异步快照如何把这项成本挪出热路径，见 Cluster Standby 与 HA 设计。

至于 Aeron 如何为缓存局部性布置它自己的 log 和 term buffer 的内部细节，我们交给 The Aeron Files，不在此重复。

反模式

每条消息都重新搜索最优价。 最优买/卖价必须是一个缓存的、增量维护的指针——热路径上绝不做 O(log L) 或 O(L) 的查找。
靠搜索订单簿来撤单。 撤单占主导；² 没有 order-ID 映射，你就把最常见的操作变成了一次行走。永远靠索引做 O(1)。
按平静场景来设定数组的带宽。 一次超出配置带宽的波动跳空会溢出网格；按压力来设定带宽，并为尾部保留一棵树兜底。
在热路径上分配内存。 新价位/订单必须来自预设大小的 free-list 或节点池，否则 GC/malloc 抖动会占据你的 p99。（在 JVM 上，这还会和 GC 停顿及 JIT 预热叠加——见调优方法论。）
在测量之前就专门化成数组。 一个宽或稀疏的订单簿会溢出或浪费价格网格数组；先在你自己的数据上确认带宽窄且被密集填充。

来源

WK Selph，“How to Build a Fast Limit Order Book”（存档）——事实上的从业者参考：一个由 FIFO 队列组成的价位结构，外加一张 price → limit 映射和一张 id → order 映射；数组-对-树的成本权衡「主要取决于订单簿的稀疏程度」，且 M（价位数）「通常 << N（订单数）」。 ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶
Marta Khomyn & Tālis J. Putniņš（2021），“Algos gone wild: What drives the extreme order cancellation rates in modern markets?”，Journal of Banking & Finance 129——「美国股票市场中 97% 的订单在成交前即被撤销。」经同行评审。（开放获取 PDF。） ↩ ↩²
A. Kishlaly，“Building a sub-100µs matching engine”——工程博客：「对某些市场（比如加密货币，或者价格区间已知的特定品种），一个简单的基于数组的方案可能比树更快。」按从业者观点引用。 ↩ ↩² ↩³
cppreference — std::map——「搜索、删除和插入操作具有对数复杂度。map 通常实现为红黑树。」 ↩
Jake Yoon，“The World’s Fastest Matching Engine Algorithm”，arXiv 预印本——把标准「链表串在平衡树上」设计里的尾延迟尖刺归因于指针追逐遍历和从根到叶的搜索。仅按该定性论点引用；其性能数字为未经评审的预印本。 ↩
Viktor Leis、Alfons Kemper、Thomas Neumann，“The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases”，ICDE 2013（DOI）——自适应节点类型 Node4/16/48/256；惰性展开与路径压缩；「所有操作的复杂度都是 O(k)，k 为键长」；键按位字典序有序，支持「范围扫描、前缀查找、top-k、最小值与最大值」；最坏情况空间「任何自适应基数树每键 52 字节」；「密集键……是最好的情形，可以被高效存储」。 ↩ ↩² ↩³ ↩⁴
exchange-core（Apache-2.0）——OrderBookDirectImpl 声明了 LongAdaptiveRadixTreeMap<Bucket> askPriceBuckets / bidPriceBuckets 以及一个 ART 支撑的 order-ID 索引；其 ART 类（exchange-core/collections，ArtNode4/16/48/256）直接引用 Leis 等人的论文。README 的性能数字（约 5M ops/s；1M ops/s 下 p50 0.5 µs / p99 4 µs）是该项目自己的基准——自报数字，仅覆盖撮合+风控，不含网络与日志持久化。 ↩
Martin Fowler，“Mechanical Sympathy” principles——该术语由 HFT 工程师 Martin Thompson 发扬光大；内存以 64 字节的缓存行搬运，预取器奖励可预测的顺序访问。 ↩ ↩²