什么是一些很好的数据结构来存储大订单？

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

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

有两个关键的操作：

迅速找到完全一样的价格的买卖盘（在更新的情况下取消）
快速找到与价格最接近的订单到提供的一个，但低于它

在更新的情况下，我们可能并不知道它是一个更新，所以我们可能会明星（2）并最终做（1）。我不是数据结构方面的专家，所以我开始浏览最常见的数据结构，现在我有一种感觉，它应该是某种树，但我不知道是哪一种。我最没有受过教育的猜测是一个数据结构，其中每个节点都是价格中的数字，因此，例如，为了快速找到价格为900美元的所有节点，我们执行items['9']['0']然后查找叶节点。现在头脑还是一团糟，所以请不要对我过分苛刻。任何建议都会很棒。

来源

2014-01-19 snitko

多大？成千上万的参赛作品？百万？十亿？ – phs

成千上万，典型的订单目前是4-5k条目。但请记住，我们在此讨论浏览器JavaScript性能，因为这正是我正在编写的内容。 – snitko

这听起来像你想要一个简单的binary search tree（BST）：（当然，一个self-balancing一个）

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

节点的左侧子树只包含密钥小于节点密钥的节点。

节点的右侧子树只包含密钥大于节点密钥的节点。

左右子树也必须是二叉搜索树。

必须没有重复的节点（如果需要，一个容易的约束来解决）。

一个BST，可以有效地做双方的业务 - 查找匹配一定的价值，或者一个当值最接近，但较小的元素。

这两项操作都O(log n)的运行时间，并且，更具体，比较的数量是相当接近log₂n，这大约是12为n = 5000，这是几乎没有（这里面的一些工作重新平衡树，但这应该是一个类似的工作量）。

来源

2014-01-19 23:29:32 Dukeling

适合内存不是问题。插入和搜索时间是。 – snitko

什么是一些很好的数据结构来存储大订单？

回答

相关问题