3. 内存模型设计：Level2数据存储、价格-数量映射、跳表与红黑树的应用
好，咱们直接进入正题。Level2数据，说白了就是逐笔委托的深度行情。每秒几十万笔的更新，你要是用数据库存，那系统早挂了。必须全部放在内存里。
我个人习惯把内存模型分成三层：存储层、索引层、查询层。存储层管原始数据，索引层管快速定位，查询层管聚合计算。今天重点讲前两层。
3.1 Level2数据存储结构
先看存储层。每个订单簿，其实就是两个价格-数量映射表：一个买盘（Bid），一个卖盘（Ask）。
我见过不少新手直接用Python的dict来存。嗯，小规模没问题，但到了实盘，你会发现dict的哈希冲突和内存碎片会让你头疼。我在项目中遇到过，一个订单簿存了20万档位，Python dict的内存占用直接飙到2GB，还频繁GC。
所以，我建议用数组+指针的方式。每个价格档位是一个固定大小的结构体：
struct PriceLevel {
double price; // 价格
uint64_t volume; // 总量
uint32_t order_count; // 订单数
PriceLevel* prev; // 前驱指针
PriceLevel* next; // 后继指针
};为什么用C风格的结构体？因为内存布局连续，CPU缓存友好。你想想看，遍历一个链表时，如果每个节点都在不同的内存页，那性能得多差。
核心原则：高频交易场景下，内存访问模式比算法复杂度更重要。O(log n)的算法如果导致大量缓存未命中，可能比O(n)的线性扫描还慢。
3.2 价格-数量映射的设计
价格到数量的映射，说白了就是：给定一个价格，快速找到对应的档位，然后更新数量。
最简单的做法是用哈希表。但哈希表有个问题：无法支持范围查询。比如你想查“价格在10.00到10.05之间的所有档位”，哈希表就抓瞎了。
那怎么办？用有序数据结构。这里有两个主流选择：跳表（Skip List）和红黑树（Red-Black Tree）。
| 特性 | 跳表 | 红黑树 |
|---|---|---|
| 查找复杂度 | O(log n) 平均 | O(log n) 严格 |
| 插入复杂度 | O(log n) 平均 | O(log n) 严格 |
| 内存占用 | 较高（多层指针） | 较低（2个指针+颜色位） |
| 实现难度 | 简单 | 复杂（旋转操作） |
| 并发友好度 | 高（无锁实现容易） | 低（需要精细锁） |
我个人更倾向跳表。为什么？因为实现简单，不容易出bug。我曾经在红黑树上栽过跟头——一个旋转操作的边界条件没处理好，导致订单簿数据错乱，回测结果全废了。从那以后，我对于核心数据结构，能简单就简单。
避坑指南：如果你用C++实现跳表，记得用内存池来管理节点。我曾经直接用new/delete，结果内存碎片导致性能抖动。改用固定大小的内存池后，延迟稳定了很多。
3.3 跳表在订单簿中的应用
跳表的核心思想，就是给链表加索引。每一层都是下一层的“快速通道”。
在订单簿里，我们这样用：
- 第0层：完整的价格链表，按价格排序
- 第1层：每隔2个节点取一个，作为索引
- 第2层：每隔4个节点取一个
- 以此类推
查找时，从最高层开始，快速跳过大量节点。插入时，随机决定新节点的层数。
这里有个细节：随机层数的分布。我一般用1/2的概率递增层数，这样平均每个节点有2个指针，内存开销可控。
int randomLevel() {
int level = 1;
while (rand() % 2 == 0 && level < MAX_LEVEL) {
level++;
}
return level;
}嗯，这个随机性保证了跳表的平衡性。虽然不严格，但实际效果很好。
3.4 红黑树的适用场景
虽然我偏爱跳表，但红黑树也有它的用武之地。比如，当你需要严格的最坏情况性能保证时，红黑树更靠谱。
我记得有一次做期权做市商的系统，订单簿的深度要求极高，最坏情况下延迟不能超过10微秒。跳表的随机性导致偶尔出现长路径，虽然概率低，但无法接受。最后换成了红黑树，用内存池+预分配节点的方式，把延迟抖动降到了1微秒以内。
注意：红黑树的实现一定要用迭代器，不要用递归。递归会导致栈溢出，尤其是在深度很大的订单簿中。我曾经见过一个同事的代码，递归深度超过1000层，直接Segmentation Fault。
3.5 核心逻辑流程图
下面这张图展示了订单簿内存模型的核心逻辑：
3.6 实战中的选择建议
说了这么多，到底该用哪个？我总结几条经验：
- 如果你做的是A股Level2行情：数据量不大（约5000档位），用跳表就够了。实现简单，维护方便。
- 如果你做的是加密货币订单簿：数据量巨大（几万到几十万档位），建议用红黑树。性能更稳定，内存更紧凑。
- 如果你做的是期权做市：需要同时管理多个到期日、多个行权价，建议用嵌套结构：外层用红黑树按到期日分组，内层用跳表按价格排序。
我的个人习惯：先用跳表快速实现原型，跑通业务逻辑。等性能瓶颈出现时，再用红黑树替换热点路径。这样既保证了开发效率，又能在关键时刻优化性能。
嗯，内存模型这块就讲这么多。记住一句话：没有银弹。跳表和红黑树各有优劣，关键看你的业务场景。多测试，多压测，用数据说话。
公众号:蓝海数据掘金营，微信deep3321