第4章订单簿数据结构设计

4、订单簿数据结构设计：内存中的订单簿表示

好，咱们直接进入正题。订单簿，说白了就是交易所里那个「挂单的账本」。你想想看，每秒成千上万的订单涌进来，如果数据结构没选好，系统分分钟崩给你看。我个人习惯把订单簿拆成三个核心部分：价格层级、订单队列、以及快照机制。咱们一个一个聊。

4.1 内存中的订单簿表示

先说说整体结构。订单簿在内存里长什么样？我一般用一个 OrderBook 类来封装，里面维护两个核心容器：一个管买单（Bid），一个管卖单（Ask）。

class OrderBook {
    // 价格层级管理
    TreeMap<Double, PriceLevel> bids;  // 买单，价格降序
    TreeMap<Double, PriceLevel> asks;  // 卖单，价格升序
    
    // 订单索引（快速查找）
    HashMap<Long, Order> orderMap;
    
    // 快照版本号
    long snapshotVersion;
}

嗯，这里要注意：买单和卖单的排序方向是反的。买单价格高的优先成交，所以降序排列；卖单价格低的优先成交，所以升序排列。这个细节搞反了，撮合逻辑就全乱了。

  核心思路： 用 TreeMap 管理价格层级，用 HashMap 做订单的 O(1) 查找。两者配合，才能做到「按价格找得快，按订单 ID 也找得快」。

4.2 使用红黑树管理价格层级

为什么选红黑树？说白了，我们需要一个「有序的、能快速插入删除」的数据结构。数组插入太慢，链表查找太慢，哈希表没法排序。红黑树正好满足需求。

Java 里的 TreeMap 底层就是红黑树。每次新价格进来，插入复杂度 O(log N)。价格撤单了，删除也是 O(log N)。我在项目中遇到过极端行情，一秒内价格层级从 100 个暴涨到 5000 个，红黑树依然扛得住。

// 添加订单到指定价格层级
public void addOrder(Order order) {
    double price = order.getPrice();
    PriceLevel level = bids.get(price);
    
    if (level == null) {
        level = new PriceLevel(price);
        bids.put(price, level);  // 红黑树插入 O(log N)
    }
    
    level.addOrder(order);
    orderMap.put(order.getId(), order);
}

避坑指南： 我曾经犯过一个错——直接用 Double 作为 TreeMap 的 key。浮点数精度问题导致两个价格明明一样，却被当成不同 key。后来我改用 long 类型，把价格乘以 10000 转成整数，再也没出过问题。

4.3 使用链表管理订单队列

同一个价格层级下，订单怎么排队？用链表。为什么不用数组？因为订单频繁插入删除，数组的移动成本太高了。链表只需要改几个指针就行。

我一般用双向链表，每个节点存一个订单对象。为什么是双向？因为有时候需要从中间删除某个订单（比如撤单），双向链表可以 O(1) 完成。

class PriceLevel {
    double price;
    LinkedList<Order> orders;  // 订单队列，FIFO 原则
    
    public void addOrder(Order order) {
        orders.addLast(order);  // 新订单排到队尾
    }
    
    public Order removeOrder(long orderId) {
        // 实际项目中用 HashMap 加速查找
        // 这里简化展示
        for (Order o : orders) {
            if (o.getId() == orderId) {
                orders.remove(o);
                return o;
            }
        }
        return null;
    }
}

你想想看，如果同一个价格有 1000 个订单排队，用链表管理，插入是 O(1)，删除如果知道节点位置也是 O(1)。但如果你不知道位置，就得遍历——这就是为什么我们还需要一个全局的 orderMap。

注意： 链表虽然插入删除快，但遍历慢。所以「按订单 ID 查找」这件事，千万别依赖链表，一定要用 HashMap。这是架构设计里的「职责分离」原则。

4.4 订单簿的快照与增量更新

这个部分比较有意思。交易所需要把订单簿的状态推送给订阅者，比如做市商、量化基金。推送方式有两种：快照和增量。

快照：把整个订单簿的当前状态打包发送。优点是简单，缺点是数据量大。每秒发一次快照，带宽就炸了。

增量：只发送变化的部分，比如「新增了一个订单」「撤单了一个订单」。优点是数据量小，缺点是客户端需要自己维护状态。

实际项目中，我一般这样设计：

class SnapshotManager {
    long lastSnapshotVersion = 0;
    List<DeltaEvent> deltaBuffer = new ArrayList<>();
    
    // 生成快照
    public Snapshot takeSnapshot(OrderBook book) {
        Snapshot snap = new Snapshot();
        snap.version = book.snapshotVersion;
        snap.bids = deepCopy(book.bids);
        snap.asks = deepCopy(book.asks);
        return snap;
    }
    
    // 记录增量事件
    public void recordDelta(DeltaEvent event) {
        deltaBuffer.add(event);
    }
    
    // 获取自某个版本以来的增量
    public List<DeltaEvent> getDeltasSince(long version) {
        // 从 deltaBuffer 中筛选出 version 之后的增量
    }
}

  经验之谈： 我建议快照和增量配合使用。比如每 10 秒发一次快照，中间每秒发增量。客户端收到快照后，用增量不断更新本地状态。这样既节省带宽，又能保证数据一致性。

这里有个坑：增量事件必须按顺序处理。如果客户端先收到后面的增量，再收到前面的，状态就乱了。所以增量事件一定要带版本号或者时间戳，客户端按顺序应用。

4.5 整体架构图

下面这张图展示了订单簿的核心数据结构和数据流。我习惯用 SVG 画这种图，清晰又不用加载外部资源。

这张图把整个订单簿的脉络理清楚了。左边是买单，右边是卖单，中间是订单队列，下面是索引和快照管理。你写代码的时候，脑子里要有这张图。

个人习惯： 我每次重构订单簿，都会先画一张这样的架构图。画清楚了再写代码，能省掉 80% 的调试时间。别急着敲键盘，先想清楚数据怎么流。

好了，订单簿的数据结构设计就聊到这儿。核心就三件事：红黑树管价格、链表管队列、快照加增量管推送。把这些搞明白了，订单簿的骨架就搭起来了。

📚 课程目录

4、订单簿数据结构设计：内存中的订单簿表示

4.1 内存中的订单簿表示

4.2 使用红黑树管理价格层级

4.3 使用链表管理订单队列

4.4 订单簿的快照与增量更新

4.5 整体架构图