有哪些好的数据结构可以存储大型订单簿？

Question

我正在编写一个从交易所获取订单簿的比特币交易应用程序。一个典型的订单簿看起来像这样：https : //www.bitstamp.net/api/order_book/（它有两部分，“bids”和“asks”，它们应该分开存储，但使用相同的数据结构）。一个解决方案是只存储这个大订单的一部分，这将解决访问效率问题，但它引入了一组与一致性和更新限制有关的其他问题。所以现在，似乎更好的解决方案是获取订单并不断更新它。

现在，此交易者应用程序稍后会使用新订单和已删除订单更新此获取的订单簿。例如，如果您在订单簿中以 900 美元的价格购买 1.5BTC 的订单，它可能会被完全取消，或者可能会更新为包含更多或更少的 BTC。此外，可以在低于或高于该价格的情况下添加新订单。

有两个关键操作：

1. 快速找到价格完全相同的订单（在更新或取消的情况下）

2. 快速找到与提供的价格最接近但低于该价格的订单

在更新的情况下，我们可能实际上并不知道它是一个更新，因此我们可能会开始执行（2）并最终执行（1）。

我不是数据结构方面的专家，所以我开始查看最常见的数据结构，现在我觉得它应该是某种树，但我不确定是哪一种。我最没有根据的猜测是这样一种数据结构，其中每个节点都是价格中的一个数字，因此，例如，我们要快速找到价格为 900 美元的所有节点，items['9']['0']然后查找叶节点。现在我的脑子里还是一团糟，所以请不要对我评价太苛刻。任何建议都会很棒。

Answer 1

听起来你想要一个简单的二叉搜索树（BST）：（嗯，一个自平衡的树）

二叉搜索树（BST）是一种基于节点的二叉树数据结构，具有以下属性：

• 节点的左子树仅包含键小于该节点键的节点。
• 节点的右子树仅包含键大于该节点键的节点。
• 左子树和右子树也必须是二叉搜索树。
• 不能有重复的节点（如果需要的话，这是一个很容易绕过的限制）。

BST 允许您高效地执行这两种操作 - 查找与某个值匹配的元素，或者查找该值最接近但更小的元素。

这两个操作的运行时间都是O(log n)，更具体地说，比较次数非常接近，大约是，这几乎没什么（并且需要一些工作来重新平衡树，但这应该是类似的工作量）。log2n12n = 5000