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

Question

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

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

有两个关键操作:

快速找到价格完全相同的订单(如果是
更新或取消)

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

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

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

Answer 1

听起来您想要一个简单的 binary search tree (BST):(嗯，一个 self-balancing 一个)

A binary search tree (BST) is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• The left and right subtree each must also be a binary search tree.
• There must be no duplicate nodes (an easy constraint to get around though, if need be).

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

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