4、数据结构设计：价格-数量红黑树、跳表实现、Level2快照与增量更新
好，咱们今天聊点硬核的。
订单簿的核心，说白了就是一张价格到数量的映射表。但问题在于——这张表每秒要更新几千次，还要支持快速查询、插入、删除。普通的数组或哈希表，根本扛不住。
我早年做第一个高频系统时，就吃过这个亏。当时图省事用了Python的dict，结果一到行情爆发，CPU直接飙到100%，订单簿还经常出现价格错位。后来老老实实换了数据结构，才把性能稳住。
4.1 价格-数量红黑树：为什么是它？
红黑树，本质上是一种自平衡的二叉搜索树。它保证在最坏情况下，插入、删除、查找的时间复杂度都是O(log n)。
你想想看，订单簿里价格是有序的——买盘从高到低，卖盘从低到高。红黑树天然支持按序遍历，正好匹配这个需求。
我习惯用C++的std::map来实现，它底层就是红黑树。但要注意，map的迭代器在插入删除时不会失效（除了被删的那个），这点对增量更新特别重要。
// 卖盘红黑树示例（价格升序）
std::map<double, uint64_t, std::less<double>> askTree;
// 买盘红黑树示例（价格降序）
std::map<double, uint64_t, std::greater<double>> bidTree;
// 插入或更新一个价格档位
void updateLevel(std::map<double, uint64_t>& tree, double price, uint64_t qty) {
if (qty == 0) {
tree.erase(price); // 数量为0，删除该档位
} else {
tree[price] = qty; // 插入或更新
}
}
// 获取最优价格（卖一价）
double getBestAsk(const std::map<double, uint64_t>& askTree) {
if (askTree.empty()) return 0.0;
return askTree.begin()->first;
}
4.2 跳表实现：另一种选择
红黑树虽好，但实现复杂，调试起来也头疼。跳表（Skip List）是另一种有序数据结构，它用概率平衡代替了严格平衡。
说白了，跳表就是给链表加了几层“快速通道”。底层是完整的有序链表，上层是稀疏的索引。查找时从顶层开始，快速跳过中间节点。
- 实现简单，代码量只有红黑树的1/3
- 支持无锁并发（CAS操作）
- 范围查询效率高
我有个同事特别喜欢跳表，他说“红黑树旋转来旋转去，脑子都转晕了，跳表多清爽”。确实，跳表的插入和删除只需要调整指针，不需要复杂的旋转操作。
// 跳表节点定义（简化版）
struct SkipNode {
double price;
uint64_t qty;
std::vector<SkipNode*> forward; // 各层的前向指针
SkipNode(double p, uint64_t q, int level)
: price(p), qty(q), forward(level + 1, nullptr) {}
};
// 查找价格档位
SkipNode* find(SkipNode* head, double price) {
SkipNode* cur = head;
for (int i = cur->forward.size() - 1; i >= 0; --i) {
while (cur->forward[i] && cur->forward[i]->price < price) {
cur = cur->forward[i];
}
}
cur = cur->forward[0];
return (cur && cur->price == price) ? cur : nullptr;
}
4.3 Level2快照与增量更新
行情数据有两种：快照（Snapshot）和增量（Incremental）。快照是全量数据，增量是变化部分。
你想想看，如果每次更新都传全量数据，带宽根本扛不住。所以交易所通常的做法是：
- 每隔一段时间（比如100ms）发一次快照
- 两次快照之间，发增量更新
我早期做的一个项目，就是处理深交所的Level2行情。增量更新的格式很简单：
// 增量更新结构
struct Level2Increment {
char side; // 'B' 买盘, 'S' 卖盘
double price; // 价格
uint64_t qty; // 新数量（0表示删除该档位）
uint32_t seq; // 序列号，用于去重和排序
};
处理逻辑也不复杂：收到增量后，更新红黑树或跳表。但有个坑——增量可能乱序到达。比如序列号5的更新先到，序列号3的更新后到。这时候需要做去重和排序。
快照的处理更直接：清空当前订单簿，然后批量插入所有价格档位。但要注意，快照到达时，可能已经有增量在缓存中了。正确的顺序是：先应用快照，再应用快照之后的所有增量。
// 快照应用示例
void applySnapshot(const std::vector<PriceLevel>& bids,
const std::vector<PriceLevel>& asks) {
// 清空当前订单簿
bidTree.clear();
askTree.clear();
// 批量插入买盘
for (const auto& level : bids) {
bidTree[level.price] = level.qty;
}
// 批量插入卖盘
for (const auto& level : asks) {
askTree[level.price] = level.qty;
}
// 记录快照时间戳
lastSnapshotTime = getCurrentTimestamp();
}
4.4 数据结构选型对比
| 特性 | 红黑树 | 跳表 |
|---|---|---|
| 查找时间复杂度 | O(log n) | O(log n) 期望 |
| 插入/删除时间复杂度 | O(log n) | O(log n) 期望 |
| 实现复杂度 | 高（旋转、染色） | 低（指针操作） |
| 内存占用 | 较低（2个指针/节点） | 较高（平均log n层指针） |
| 并发支持 | 困难（需要锁） | 容易（CAS操作） |
| 范围查询 | 好（中序遍历） | 好（底层链表遍历） |
我个人更倾向于红黑树，因为它的性能是确定的，没有概率波动。但在高并发场景下，跳表的无锁特性确实有优势。
4.5 实战中的注意事项
嗯，这里有几个坑，我当年都踩过：
- 浮点数精度问题： 价格用double存储，但比较时要注意精度。我习惯把价格乘以10000转成整数，避免浮点误差。
- 内存分配： 高频场景下，频繁new/delete会导致内存碎片。建议使用内存池或对象池。
- 缓存友好性： 红黑树的节点在内存中不连续，遍历时缓存命中率低。跳表的底层链表是连续的，缓存更友好。
- 增量积压： 如果处理速度跟不上行情速度，增量会积压。需要设计背压机制，比如丢弃旧增量或降级处理。
好了，数据结构这块就聊这么多。记住一点：没有银弹。红黑树和跳表各有优劣，关键看你的场景。如果追求确定性性能，选红黑树；如果追求实现简单和并发支持，选跳表。