第4章内存数据结构

内存数据结构：红黑树、跳表、哈希表在订单簿中的应用

订单簿，说白了就是交易所里那个「买一卖一」的实时快照。但背后要支撑每秒几万笔的撮合，数据结构选错了，延迟直接爆炸。

我个人习惯把订单簿拆成两层：价格层和订单层。价格层管理所有档位的价格，订单层管理每个价格下的订单队列。不同层，用的数据结构完全不同。

红黑树是一种自平衡二叉搜索树。它的插入、删除、查找都是 O(log n)。

为什么订单簿的价格层需要它？因为价格是离散的，而且我们需要按价格排序——买盘从高到低，卖盘从低到高。红黑树天然支持有序遍历。

我在项目中遇到过一个问题：用 std::map（底层就是红黑树）来存价格档位。每次新价格进来，插入 O(log n)；价格被吃掉，删除 O(log n)。看起来完美。

但实际跑起来，发现一个问题：红黑树的常数太大了。每次插入都要旋转、变色，CPU 缓存命中率也不高。对于只有几十个价格档位的订单簿，O(log n) 和 O(n) 差别不大，但红黑树的 cache miss 反而更伤。

  适用场景：价格档位数量较多（几百个以上），且需要频繁按价格范围查询的场景。

我的建议：如果价格档位不超过 200 个，直接用有序数组 + 二分查找，性能反而更好。别迷信红黑树。

跳表是另一种有序数据结构。它用多层链表实现，插入和删除也是 O(log n)。但它的常数比红黑树小，而且实现简单。

为什么跳表在订单簿里用得少？因为它的内存开销大。每个节点要存多个 forward 指针，层数越高，指针越多。对于内存敏感的 HFT 系统，这不太友好。

不过，我记得有个同事在某个期权做市系统里用了跳表。原因是那个系统的价格档位会动态变化，而且需要支持「范围查询」——比如查某个价格区间内的所有订单。跳表在这类场景下，比红黑树好写得多。

避坑指南：我曾经在跳表里踩过一个坑——随机层数生成器的种子没处理好，导致大量节点集中在同一层，退化成链表。后来改用线程安全的随机数生成器才解决。

订单层，也就是每个价格下的订单队列，用哈希表最合适。为什么？因为订单 ID 是唯一的，而且我们只需要根据 ID 快速找到订单，然后修改或删除。

哈希表的插入、删除、查找都是 O(1)。对于订单层来说，这是最优解。

但哈希表有个问题：冲突处理。我见过有人用开放地址法，结果订单量一大，冲突链变长，性能急剧下降。我个人习惯用链地址法，并且把桶的大小设成 2 的幂次，这样取模运算可以用位运算代替。

  核心思路：价格层用红黑树（或有序数组），订单层用哈希表。两层组合，才能支撑高频撮合。

你想想看，一个真实的订单簿，价格档位通常只有几十个，但每个价格下的订单可能有几千笔。所以价格层用红黑树其实有点「杀鸡用牛刀」。我见过不少 HFT 系统，价格层直接用数组 + 双向链表，因为价格档位变化不频繁，数组的 cache 友好性远胜红黑树。

订单层则完全不同。订单 ID 是随机生成的，哈希表能保证 O(1) 的查找速度。但要注意哈希函数的设计——别用 std::hash 直接套，它可能产生大量冲突。我习惯用 MurmurHash 或 CityHash，冲突率低，速度也快。

一个小技巧：如果订单量特别大（比如几十万笔），可以考虑用「两级哈希」——先按价格哈希，再按订单 ID 哈希。这样能减少单个哈希表的负载。

下面这张图展示了订单簿中价格层和订单层的数据结构组合方式：

嗯，这里要注意：价格层和订单层是独立的。价格层的每个节点，都指向一个订单层的哈希表。这样设计的好处是，价格变动时只需要操作价格层，订单变动时只需要操作订单层，互不干扰。

  总结一下：红黑树适合价格层，但别迷信它；跳表是工程上的折中，但内存开销大；哈希表是订单层的不二之选。实际项目中，根据数据量和访问模式灵活选择，才是正道。