数据结构选型：为什么Python原生list不适合高频订单簿？
大家好，我是你们的讲师。今天我们来聊一个很基础、但又很关键的问题——数据结构选型。
你可能觉得，不就是个列表吗？Python的list用起来多顺手啊。但我要告诉你，在高频交易场景下，用list来维护订单簿，基本等于自杀。这话不是我危言耸听，是我在实盘环境里踩过的坑。
先说说订单簿到底长什么样
订单簿，说白了就是买卖双方的排队队列。买盘从高到低排，卖盘从低到高排。每一档价格上，挂着多少手单子，一目了然。
举个例子：
卖五：10.05 200手
卖四：10.04 150手
卖三：10.03 300手
卖二：10.02 100手
卖一：10.01 250手
-------------------
买一：10.00 180手
买二：9.99 220手
买三：9.98 160手
买四：9.97 90手
买五：9.96 300手嗯，这就是最经典的订单簿结构。每一笔新的报单进来，要么插入到合适的位置，要么修改已有的档位，要么删除某个档位。你想想看，这些操作在Python list里做，会是什么效果？
Python list的致命伤
Python的list，底层是动态数组。动态数组有个特点：随机访问快，但插入和删除慢。
为什么会这样？
因为数组在内存里是连续存储的。你要在中间插入一个元素，后面的所有元素都得往后挪一位。删除也是同理，后面的元素要往前补位。这个操作的时间复杂度是O(n)。
我举个例子你就明白了：
# 假设订单簿有1000档价格
order_book = [9.90, 9.91, 9.92, ..., 10.90]
# 现在要插入一个9.95的价格
# 需要找到插入位置，然后把后面的所有元素往后移
index = bisect_left(order_book, 9.95) # 二分查找O(log n)
order_book.insert(index, 9.95) # 插入操作O(n)你看，虽然查找用了二分法，时间复杂度是O(log n)，但插入这一步直接把整体拖成了O(n)。1000档还好说，要是10000档呢？要是每秒有几千笔报单呢？
我曾经在回测系统里用list维护订单簿，数据量一上来，回测速度直接崩了。后来一分析，90%的时间都花在list的插入和删除上。那叫一个惨。
那数组呢？C++里的vector也不行吗？
如果你用C++，可能会想到std::vector。它和Python list本质一样，都是动态数组。同样的问题——中间插入删除是O(n)。
但C++有个优势：你可以用环形缓冲区或者预分配大数组来优化。比如，你知道订单簿最多只有100档价格，那就直接开一个固定大小的数组，用索引来模拟插入删除。这样能避免内存搬移。
不过，这属于"取巧"的做法。真正的低延迟场景，我们一般不这么干。
链表：插入快，但查找慢
链表呢？插入和删除确实是O(1)，只要你已经找到了位置。但问题在于——查找位置本身是O(n)。
订单簿里，你每次操作都需要先找到正确的价格档位。链表不支持随机访问，只能从头遍历。1000档价格，平均要遍历500次才能找到目标位置。
你说，那用哈希表存位置映射？嗯，这倒是个思路。但哈希表本身有开销，而且订单簿的价格是连续区间，哈希冲突也会影响性能。
我个人习惯是：链表只适合写多读少的场景。订单簿是读写都频繁，链表扛不住。
跳表：折中的王者
那有没有一种数据结构，既能快速查找，又能快速插入删除？
有，跳表（Skip List）。
跳表的本质，是在链表的基础上，增加了多层索引。每一层索引都跳过一部分节点，让查找时能"跳着走"，而不是一个个遍历。
你看这张图就明白了：
查找的时候，从最高层开始，往右走。如果下一个节点比目标大，就往下跳一层。这样，查找的时间复杂度降到了O(log n)。
插入和删除呢？也是O(log n)。因为你先用O(log n)找到位置，然后执行O(1)的指针操作。
核心结论：跳表在查找、插入、删除三个操作上，都做到了O(log n)的时间复杂度。对于订单簿这种读写均衡的场景，跳表是最优解之一。
三种数据结构的对比
| 操作 | Python list | 链表 | 跳表 |
|---|---|---|---|
| 查找 | O(1) 随机访问 O(log n) 二分查找 |
O(n) | O(log n) |
| 插入 | O(n) 内存搬移 | O(1) 已知位置 | O(log n) |
| 删除 | O(n) 内存搬移 | O(1) 已知位置 | O(log n) |
| 内存开销 | 低 | 中（指针开销） | 较高（多层索引） |
| 适用场景 | 只读、小数据量 | 写多读少 | 读写均衡 |
避坑指南：我曾经在早期版本里用Python list + bisect模块做订单簿，觉得二分查找很快。结果实盘一跑，延迟直接飙到毫秒级。后来换成跳表，延迟降到了微秒级。差距就是这么大。
那Python里怎么用跳表？
Python标准库没有跳表实现。但你可以自己写一个，或者用第三方库。我个人建议自己写，因为订单簿的跳表有一些特殊需求：
- 价格是浮点数，需要处理精度问题
- 同一价格可能有多个订单，需要支持FIFO队列
- 需要快速获取最优买卖价，即跳表的首尾节点
一个简单的跳表节点定义：
class SkipNode:
__slots__ = ('price', 'volume', 'forward', 'height')
def __init__(self, price, volume, height):
self.price = price
self.volume = volume
self.forward = [None] * (height + 1)
self.height = height注意我用了__slots__，这是Python性能优化的一个小技巧。它能减少每个对象的内存开销，提升属性访问速度。
嗯，这里要注意：跳表虽然好，但不是银弹。如果你的订单簿只有几十档价格，用list反而更快。因为跳表的索引维护有额外开销。我一般建议，超过100档价格，才考虑用跳表。
总结一下
Python原生list不适合高频订单簿，根本原因在于插入和删除的O(n)时间复杂度。在高频场景下，每秒几千笔报单，O(n)的操作就是灾难。
链表虽然插入快，但查找慢，不适合订单簿这种需要频繁定位的场景。
跳表通过多层索引，把查找、插入、删除都优化到了O(log n)，是目前订单簿实现的主流选择。
当然，还有更极致的数据结构，比如红黑树、B树，甚至是一些定制的内存结构。这些我们后面章节再聊。
记住一句话：选对数据结构，比优化代码逻辑更重要。数据结构选错了，后面再怎么优化都是白费力气。