什麼是一些很好的數據結構來存儲大訂單？

我正在寫一個從交易所獲取訂單的比特幣交易應用程序。一個典型的訂單看起來是這樣的：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

什麼是一些很好的數據結構來存儲大訂單？

回答

相關問題