核心数据结构设计：价格队列与订单条目

好，咱们正式开始搭建订单簿。这一章，我重点聊聊最核心的数据结构设计。

你想想看，一个订单簿本质上在做什么？说白了，就是管理一堆「谁想在什么价格买/卖多少」。那怎么管才高效？这就涉及到三个关键问题：价格怎么组织、订单怎么表示、内存里用什么结构存。

我个人习惯，先想清楚数据模型，再动手写代码。不然写到一半发现结构不合理，重构起来真要命。

价格队列：有序集合的设计

先看价格这一层。订单簿里，价格是有序的——买价从高到低排，卖价从低到高排。为什么？因为撮合逻辑就是「最高买价 vs 最低卖价」。

所以价格队列必须是一个有序集合。我见过不少新手直接用数组存价格，然后每次插入都排序……嗯，数据量小还行，几万笔订单进来就卡成幻灯片了。

价格队列需要支持的操作：

• 按价格顺序遍历（从最优价开始）
• 快速插入新价格
• 快速删除某个价格（当该价格下订单全部撤单时）
• 快速查找某个价格是否存在

这里有个细节：同一个价格下会有多笔订单，所以价格队列的每个节点，其实是一个「价格 + 订单链表/队列」的组合。我习惯叫它 PriceLevel。

订单条目设计：四个核心字段

每个订单条目，最少需要四个字段：

字段	类型	说明
订单ID	uint64 / string	全局唯一，用于撤单、查询
价格	int64 / decimal	注意精度问题，我建议用整数表示（如 1.23 存为 123）
数量	uint64	剩余未成交数量，成交后递减
时间戳	int64 (纳秒)	用于价格相同时的FIFO排序

我曾经在项目中踩过一个坑：订单ID用了自增整数，结果分布式部署时ID冲突了……后来改成UUID+时间戳组合才解决。嗯，这里要注意，订单ID的生成策略要提前想好。

另外，时间戳的精度很重要。如果两个订单价格相同，谁先来谁先成交。用毫秒级时间戳在高频场景下可能不够，我建议用纳秒级，或者加一个自增序列号。

内存数据结构选型：红黑树 vs 跳表 vs 哈希表

好，重头戏来了。价格队列用什么数据结构存？我直接说结论：红黑树和跳表都行，哈希表不行。

为什么哈希表不行？因为哈希表不维护顺序。你没法快速拿到「当前最优买价」——得遍历所有价格才能找到最高价，O(n) 复杂度，订单一多就崩了。

那红黑树和跳表怎么选？我列个对比：

特性	红黑树	跳表
查找时间复杂度	O(log n)	O(log n)
插入/删除	O(log n)，但需要旋转和变色	O(log n)，概率性操作
范围遍历	需要中序遍历，实现稍复杂	天然支持顺序遍历，实现简单
并发性能	锁粒度较粗	可以细粒度锁或无锁
实现复杂度	高（红黑树细节多）	中等

我个人习惯，用跳表。原因有三：

1. 实现简单，不容易出bug。红黑树的旋转和颜色调整，写错一次就够你调一整天。
2. 范围遍历天然支持。订单簿经常需要「从最优价开始往下取N个价格」，跳表直接往前走就行。
3. 并发改造容易。跳表可以按层级加锁，甚至用CAS实现无锁版本。

当然，如果你用C++，std::map就是红黑树，直接用也挺好。但如果是Java，ConcurrentSkipListMap就是现成的跳表实现，我建议优先考虑。

整体结构图

下面这张图展示了订单簿的核心数据组织方式。你可以看到，价格队列是有序的，每个价格下挂着一个订单链表，订单按时间戳排序。

看到没？买盘和卖盘各自维护一个有序的价格队列。每个价格节点下，订单按时间戳排好队。撮合时，直接从买盘最高价和卖盘最低价开始比对。

代码示例：价格队列的跳表实现（伪代码）

下面我用伪代码展示跳表实现价格队列的核心逻辑。实际语言可能是C++、Java或Go，但思路是一样的。

// 价格节点
struct PriceLevel {
    double price;
    OrderQueue orders;  // 该价格下的订单队列（FIFO）
};

// 跳表节点
struct SkipListNode {
    PriceLevel* level;
    SkipListNode* forward[];  // 不同层级的指针
};

// 跳表实现的价格队列
class PriceQueue {
private:
    SkipListNode* head;
    int maxLevel;
    double (*compare)(double a, double b);  // 比较函数，买盘用降序，卖盘用升序

public:
    // 插入价格节点
    void insert(PriceLevel* level) {
        // 从最高层开始找插入位置
        // 随机生成层数
        // 更新各层指针
    }

    // 获取最优价格（买盘最高价 / 卖盘最低价）
    PriceLevel* getBestPrice() {
        return head->forward[0]->level;
    }

    // 删除价格节点（当该价格下订单全部撤单时）
    void remove(double price) {
        // 找到节点并更新各层指针
    }

    // 按顺序遍历所有价格
    void traverse() {
        SkipListNode* cur = head->forward[0];
        while (cur != nullptr) {
            process(cur->level);
            cur = cur->forward[0];
        }
    }
};

总结一下本章要点

• 价格队列必须是有序集合，支持快速插入、删除、按序遍历
• 订单条目最少包含：订单ID、价格、数量、时间戳
• 内存数据结构选型：跳表 > 红黑树 > 哈希表（哈希表不适合）
• 每个价格节点下挂订单链表，按时间戳FIFO排序

嗯，这一章的内容就到这儿。数据结构定好了，下一章我们就可以开始写真正的撮合逻辑了。

---

公众号:蓝海资料掘金营，微信deep3321