在构建高频交易系统、数字货币交易所或任何需要高性能撮合引擎的场景中，订单簿（Order Book）是其绝对核心。订单簿的性能直接决定了整个系统的吞吐量和延迟。工程师们通常会下意识地想到使用平衡二叉搜索树（如红黑树）来实现，毕竟这是教科书中的标准答案。然而，在真实的一线高并发场景下，一种基于概率的数据结构——跳表（SkipList），往往是更优的选择。本文将从底层原理、代码实现、并发控制到架构演进，深度剖析为何跳表能在与红黑树的对决中胜出。
现象与问题背景：订单簿的核心诉
求
订单簿本质上是一个按价格优先、时间优先原则维护买单（Bids）和卖单（Asks）的集合。对于买单，价格越高越优先；对于卖单，价格越低越优先。在同一价格上，先提交的订单优先成交。这要求订单簿的数据结构必须高效支持以下核心操作：
- 插入（Add Order）：一个新订单进入市场，需要以 O(log N) 的时间复杂度插入到正确的位置。
- 删除（Cancel Order）：用户撤销订单，需要以 O(log N) 的时间复杂度快速定位并移除。
- 查找（Find Best Bid/Ask）：快速找到最高买价和最低卖价，这通常是 O(1) 操作，因为它们位于数据结构的两端。
- 遍历（Market Depth）：按价格顺序遍历订单，以生成市场深度信息。
在一个活跃的市场，每秒可能有数十万甚至数百万次的订单变更。这意味着底层数据结构必须在承受极高写入负载（插入和删除）的同时，保持极低的延迟。任何操作的延迟抖动都可能导致交易滑点，甚至引发系统性的风险。因此，选择一个理论和实践性能都极其出色的数据结构，是系统设计的第一个关键决策点。
关键原理拆解：从链表到跳表的多级加速
（学术风）
要理解跳表，我们必须回到最基础的有序数据结构——有序链表。一个普通的有序链表，虽然插入和删除操作在找到位置后是 O(1) 的，但查找特定元素却需要 O(N) 的线性扫描，这在我们的场景中是完全不可接受的。
如何加速查找？想象一下为链表建立“索引”或“快速通道”。我们可以从原始链表中，每隔一个节点提取一个节点，形成一个更高级别的链表。查找时，我们首先在高级别链表中查找，这使得我们可以一次性“跳过”多个节点。例如，要查找元素 X，我们在高级别链表中找到最后一个小于 X 的节点，然后下降到原始链表中继续进行线性查找。这已经将查找效率提高了一个数量级。
跳表将这个思想推向了极致。它不是只建立一级索引，而是建立多级索引。一个跳表由多个“层”（Level）组成，最底层（Level 0）是包含所有元素的完整有序链表。每一层都是其下一层链表的一个稀疏“子序列”。一个节点可以在多个层中出现，它在第 i 层出现，就意味着它有一个指向第 i 层下一个节点的指针。一个节点的层数（或高度）是在插入时随机决定的。
查找过程：从最高层的头节点开始，向右遍历，直到找到一个节点，其下一个节点的值大于或等于目标值。然后，从当前节点下降一层，重复这个向右遍历的过程。这个过程持续进行，直到到达最底层。整个路径就像在一个楼梯上不断向右和向下移动，最终在 Level 0 精确找到目标位置。由于每一层都能跳过大量节点，其平均查找、插入和删除的时间复杂度都是 O(log N)。
概率性平衡：与红黑树等平衡二叉树通过复杂的旋转操作来维持平衡不同，跳表的平衡性是通过概率来保证的。在插入一个新节点时，我们会通过一个随机过程来决定这个新节点的高度（即它会出现在多少层中）。通常的做法是，从 Level 1 开始，抛硬币，如果是正面，就将层数加一，并继续抛，直到出现反面为止。这种设计使得高层节点数量呈指数级递减，从而在统计学上保证了结构的平衡和 O(log N) 的性能。这种“无为而治”的平衡策略，正是其工程实现优势的关键来源。
核心模块设计与实现
（极客风）
理论是优雅的，但魔鬼在细节里。我们来看一下一个订单簿跳表的具体实现。假设我们只实现卖单侧（Ask side），价格越低越靠前。
节点定义
首先是节点结构。除了订单信息（价格、数量等），核心是 `forward` 指针数组，它的大小在节点创建时动态决定。
// Order 代表一个订单实体
type Order struct {
ID uint64
Price int64 // 为方便比较，价格通常用定点整数表示
Quantity int64
Timestamp int64
}
// Node 是跳表中的一个节点
type Node struct {
order *Order
// forward 指针数组，forward[i] 表示在第 i 层的下一个节点
forward []*Node
}
插入操作实现
插入操作是跳表最精髓的部分。它分为两步：1. 查找每一层需要更新的前驱节点；2. 创建新节点并将其“拼接”到链表中。
这里的关键是 `update` 数组。`update[i]` 存储了在第 `i` 层，新节点应该插入位置的前一个节点。这个数组是在查找过程中“沿途”记录下来的，避免了二次查找。
// SkipList 结构
type SkipList struct {
header *Node
level int // 当前跳表的最大层数
maxLevel int // 可允许的最大层数
p float32 // 用于决定层数的概率因子
}
// Insert 插入一个新订单
func (sl *SkipList) Insert(order *Order) {
// update 数组用于记录每层需要更新的前驱节点
update := make([]*Node, sl.maxLevel)
current := sl.header
// 1. 从最高层开始，为每一层找到新节点的前驱节点
for i := sl.level - 1; i >= 0; i-- {
for current.forward[i] != nil && current.forward[i].order.Price < order.Price {
current = current.forward[i]
}
update[i] = current
}
// 2. 生成一个随机的层数
newLevel := sl.randomLevel()
// 3. 如果新层数超过当前最大层数，需要扩展 header 并更新 update 数组
if newLevel > sl.level {
for i := sl.level; i < newLevel; i++ {
update[i] = sl.header
}
sl.level = newLevel
}
// 4. 创建新节点
newNode := &Node{
order: order,
forward: make([]*Node, newLevel),
}
// 5. 将新节点“拼接”到每一层的链表中
for i := 0; i < newLevel; i++ {
newNode.forward[i] = update[i].forward[i]
update[i].forward[i] = newNode
}
}
// randomLevel 通过抛硬币的方式生成一个随机层数
func (sl *SkipList) randomLevel() int {
level := 1
// sl.p 通常取 0.25 或 0.5
for rand.Float32() < sl.p && level < sl.maxLevel {
level++
}
return level
}
代码直白得可怕。没有旋转，没有颜色变换，就是纯粹的指针操作。这种简单性在高并发环境下是巨大的优势，因为它让锁的粒度和持续时间变得更可控，甚至为无锁实现打开了大门。
并发安全与无锁实现
在交易系统中，订单簿的读写比极高，简单的用一个全局互斥锁（Mutex）会立刻导致系统成为性能瓶颈。多个线程（如行情推送、订单处理）会因为争抢同一个锁而串行化。跳表的结构天然适合更细粒度的并发控制。
一个进阶的方案是无锁（Lock-Free）跳表。其核心是利用 CPU 提供的原子指令，特别是 CAS（Compare-And-Swap）。CAS 操作 `CAS(p, old, new)` 会原子性地检查内存地址 `p` 处的值是否为 `old`，如果是，则更新为 `new`，并返回成功；否则什么都不做，返回失败。
无锁插入的核心思想是：在找到插入点并准备好新节点后，使用 CAS 尝试将前驱节点的 `forward` 指针从 `old_next` 更新为 `newNode`。如果 CAS 失败，意味着在当前线程操作期间，有其他线程修改了链表，此时只需简单地重试整个查找和插入过程即可。
// 伪代码展示无锁插入的关键部分
// 假设 update[i].forward[i] 是一个原子指针类型
func (sl *SkipList) LockFreeInsert(order *Order) {
// ... 省略 update 数组的查找过程 ...
// 创建新节点
newNode := &Node{...}
// 从底层开始，尝试原子性地插入新节点
for i := 0; i < newLevel; i++ {
for {
// 读取前驱节点在第 i 层的下一个节点
oldNext := atomic.LoadPointer(&update[i].forward[i])
newNode.forward[i] = oldNext
// 尝试将前驱节点的 forward 指针从 oldNext 更新为 newNode
if atomic.CompareAndSwapPointer(&update[i].forward[i], oldNext, newNode) {
// CAS 成功，继续处理上一层
break
}
// CAS 失败，说明链表被其他线程修改，需要重新查找该层的前驱节点并重试
// ... 重新查找 update[i] 的逻辑 ...
}
}
}
无锁实现非常复杂，需要处理 ABA 问题、内存回收（使用险象指针或基于纪元的内存回收）等难题，但它能提供极致的并发性能，让读写操作之间几乎没有相互阻塞，这对于撮合引擎至关重要。
对抗与权衡：跳表 vs. 红黑树的深度对决
现在，我们可以正面回答最初的问题了：为什么是跳表，而不是我们更熟悉的红黑树？
- 实现复杂度: 跳表胜出。一个基础的跳表实现，代码量和逻辑复杂度远小于红黑树。红黑树的插入和删除伴随着复杂的分情况讨论和左旋、右旋、变色等重平衡操作，极易出错，且难以调试。跳表的逻辑则统一和简洁得多。
- 单线程性能与缓存行为: 红黑树微弱优势。在纯单线程环境下，红黑树的性能通常略优于跳表。原因是红黑树的节点内存分配更紧凑，其树形结构使得父子节点在内存中物理位置上可能更接近，从而有更好的 CPU 缓存局部性。跳表的节点是离散分配的，查找过程中的指针跳转更容易导致 Cache Miss。然而，这个差距在现代 CPU 大容量缓存下并不显著。
- 并发性能: 跳表压倒性胜出。这是决定性的因素。红黑树的重平衡操作（旋转）可能会影响树中从根到叶路径上的多个节点，甚至改变树的根。这意味着对树的一次修改可能需要对一个很大范围的节点加锁，锁的粒度非常大。如果要实现细粒度锁，锁协议会变得异常复杂，容易产生死锁。而跳表的插入和删除操作是高度“局部化”的，它只影响待操作节点和它的直接前驱。这种局部性使得实现无锁或细粒度锁变得现实。在多核环境下，红黑树的全局锁或大范围锁会成为瓶颈，而无锁跳表则可以充分利用多核的优势，实现极高的并发吞吐。
- 内存开销: 红黑树胜出。跳表每个节点平均持有 1/(1-p) 个指针（p=0.25时约1.33个，p=0.5时2个），而红黑树每个节点固定持有父、左、右三个指针和一个颜色位。通常跳表的内存开销会比红黑树高出约 30%-50%。但在内存廉价的今天，这点开销换来巨大的并发性能和实现简单性是完全值得的。
总结：在高并发、写密集的订单簿场景下，并发性能是首要矛盾。跳表以其对并发的天然友好性、实现的相对简单性，压倒了红黑树在缓存和内存上的微弱优势，成为工程上的更优选。
架构演进与落地路径
一个成熟的订单簿系统不是一蹴而就的，它会经历一个清晰的演进过程。
-
阶段一：原型验证 (基于标准库)
在项目初期，或对于交易量不大的场景，直接使用语言标准库提供的有序字典（如 C++ 的 `std::map` 或 Java 的 `TreeMap`，底层通常是红黑树）构建订单簿。外部用一个大的互斥锁来保证线程安全。这个阶段的目标是快速验证业务逻辑，而不是追求极致性能。
-
阶段二：性能优化 (引入加锁跳表)
当标准库的方案成为瓶颈时，第一步是替换掉底层的红黑树。可以自己实现一个带有读写锁的跳表。读写锁允许多个读线程（如行情查询）并发执行，提升了读的性能。但写操作（下单、撤单）依然是串行的。这一步将系统的瓶颈从“所有操作串行”转移到了“写操作串行”。
-
阶段三：并发突破 (实现无锁跳表)
这是迈向高性能撮合引擎的关键一步。投入研发力量实现一个生产级的无锁跳表。这一阶段的挑战不仅仅是 CAS 算法本身，更在于设计一套健壮的内存回收机制，防止因“ABA问题”或野指针导致的崩溃。一旦成功，订单簿模块的并发处理能力将得到数量级的提升，能够轻松应对数百万 TPS 的订单请求。
-
阶段四：极致压榨 (硬件亲和性优化)
在无锁跳表的基础上，可以进行更深度的优化。例如，使用自定义的内存分配器（如对象池、Slab Allocator）来减少 `malloc` 带来的系统调用开销和内存碎片，并提升缓存局部性。在多路 CPU（NUMA）架构的服务器上，可以将不同的交易对（如 BTC/USDT 和 ETH/USDT）的订单簿绑定到不同的 NUMA 节点上，确保处理某个交易对的线程总是在本地内存上操作，避免跨NUMA节点的昂贵内存访问延迟。这是在微秒级延迟竞争中拉开差距的终极手段。
最终，一个看似简单的数据结构选择，背后是从算法理论、并发编程、操作系统内存管理到硬件体系结构的全方位考量。跳表之所以能在高性能交易领域占据一席之地，正是因为它在现代多核处理器架构下，于“并发”这个核心矛盾上，给出了比传统平衡树更优秀的工程答案。
延伸阅读与相关资源
-
想系统性规划股票、期货、外汇或数字币等多资产的交易系统建设，可以参考我们的
交易系统整体解决方案。 -
如果你正在评估撮合引擎、风控系统、清结算、账户体系等模块的落地方式，可以浏览
产品与服务
中关于交易系统搭建与定制开发的介绍。 -
需要针对现有架构做评估、重构或从零规划，可以通过
联系我们
和架构顾问沟通细节，获取定制化的技术方案建议。