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

说到订单簿的数据结构，我见过不少新手一上来就拍脑袋选个哈希表，结果上线后延迟直接炸了。订单簿这东西，说白了就是「价格优先、时间优先」的活字典。你想想看，每秒几万笔订单进来，既要快速插入，又要按价格排序，还得支持撤销和修改——这可不是随便一个数据结构就能扛住的。

我个人习惯把订单簿拆成两个核心维度：价格队列和订单映射。价格队列负责维护买卖盘口的价差结构，订单映射负责根据订单ID快速定位和操作。不同的场景，选的数据结构天差地别。

3.1 红黑树：最稳的「价格排序器」

红黑树，说白了就是一颗自平衡的二叉搜索树。它的插入、删除、查找都是 O(log n) 的复杂度。在订单簿里，我最常用它来维护限价单的价格队列。

为什么选它？因为订单簿的核心操作就是「按价格排序」。红黑树天然支持中序遍历，能直接输出从小到大的价格序列。我在做期货高频系统时，买卖盘口各维护一棵红黑树，每个节点挂一个价格队列（FIFO）。这样既能快速找到最优买卖价，又能保证同价位的订单按时间顺序成交。

不过红黑树也有坑。我记得有一次，我在实现撤销订单时，忘了更新红黑树中价格节点的引用计数，结果导致内存泄漏。嗯，这里要注意：红黑树节点和订单对象要分开管理，别把订单对象直接塞进树里。

// 伪代码：红黑树 + 价格队列
class PriceNode {
    double price;
    Queue<Order> orderQueue;  // 同价位的订单队列
    // 红黑树节点指针
    PriceNode left, right, parent;
    boolean isRed;
}

class OrderBook {
    RedBlackTree<PriceNode> bidTree;  // 买单红黑树
    RedBlackTree<PriceNode> askTree;  // 卖单红黑树
    
    void addOrder(Order order) {
        PriceNode node = findOrCreate(order.price);
        node.orderQueue.enqueue(order);
    }
    
    Order getBestBid() {
        return bidTree.getMax().orderQueue.peek();
    }
}

3.2 跳表：并发场景下的「无锁利器」

跳表，很多人觉得它就是个「带索引的链表」。其实它比红黑树更适合高并发场景。为什么？因为跳表支持无锁并发操作，而红黑树的旋转操作在并发下很难做到无锁。

我曾在做加密货币交易所时，用跳表替代了红黑树。当时团队里有人质疑：「跳表不是概率性的吗？万一索引层数不够怎么办？」其实跳表的期望复杂度就是 O(log n)，而且实现起来比红黑树简单得多。你想想看，红黑树那套左旋右旋、颜色翻转的逻辑，写起来多容易出 bug？

跳表还有一个隐藏优势：范围查询。比如你想查「价格在 100.5 到 101.0 之间的所有买单」，跳表只需要找到下界节点，然后沿着链表往后遍历就行。红黑树虽然也能做，但需要中序遍历，实现起来更复杂。

// 跳表节点结构
class SkipListNode {
    double price;
    Queue<Order> orders;
    SkipListNode[] forward;  // 不同层级的指针数组
    int level;
}

// 查找最优卖价
SkipListNode findBestAsk(SkipList list) {
    SkipListNode cur = list.head;
    for (int i = list.maxLevel - 1; i >= 0; i--) {
        while (cur.forward[i] != null && 
               cur.forward[i].price <= currentAskPrice) {
            cur = cur.forward[i];
        }
    }
    return cur.forward[0];  // 第0层就是最接近的节点
}

3.3 哈希表：订单ID的「快速定位器」

哈希表在订单簿里不是用来排序的，而是用来快速定位订单的。你想想看，一个订单进来后，可能被部分成交、修改、撤销，这些操作都需要根据订单ID找到对应的订单对象。哈希表的 O(1) 查找速度，在这里就是降维打击。

我习惯把哈希表作为订单簿的「辅助索引」。主结构（红黑树或跳表）维护价格队列，哈希表维护订单ID到订单对象的映射。这样，撤销订单时只需要 O(1) 时间找到订单，然后从价格队列中移除即可。

哈希表还有一个容易忽略的问题：哈希冲突。在订单ID这种高并发场景下，如果哈希函数设计不好，冲突率会很高。我建议用开放地址法或者链地址法，同时把哈希表容量设成 2 的幂次，这样取模运算可以用位运算加速。

// 订单ID到订单对象的哈希映射
class OrderMap {
    Order[] table;
    int capacity = 1 << 20;  // 1048576 个槽位
    
    int hash(long orderId) {
        return (int)(orderId ^ (orderId >>> 32)) & (capacity - 1);
    }
    
    void put(Order order) {
        int idx = hash(order.id);
        // 开放地址法解决冲突
        while (table[idx] != null) {
            idx = (idx + 1) & (capacity - 1);
        }
        table[idx] = order;
    }
}

3.4 三种数据结构的对比与选型

说了这么多，到底怎么选？我整理了一张对比表，你可以根据实际场景来权衡：

我个人习惯的选型策略是这样的：

• 低延迟、单线程场景（比如做市商策略）：红黑树 + 哈希表组合。红黑树负责价格队列，哈希表负责订单定位。
• 高并发、多线程场景（比如交易所撮合引擎）：跳表 + 哈希表组合。跳表支持无锁操作，哈希表用分段锁。
• 纯内存、低数据量场景（比如回测系统）：直接用哈希表 + 排序数组。数据量小的时候，排序数组的二分查找也够用。

3.5 知识体系结构图

下面这张图展示了订单簿中三种数据结构的协作关系：

从这张图可以看出，订单簿的核心是「价格排序」和「订单定位」两个维度。红黑树/跳表负责前者，哈希表负责后者。两者通过价格节点中的订单队列关联起来。嗯，这个架构我在多个生产系统中验证过，稳定性和性能都经得起考验。

最后说一句：没有银弹。每种数据结构都有自己的适用场景。你需要在理解业务需求的基础上，结合数据量、并发度、延迟要求来选型。别盲目追求「最牛」的数据结构，适合的才是最好的。