數據
限價訂單簿的紅黑樹
為什麼人們建議在限價訂單簿中使用紅黑樹/平衡二叉樹作為級別？
為什麼它們在算法上是理想的？
為什麼人們建議在限價訂單簿中使用紅黑樹/平衡二叉樹作為級別？
因為人們不是原創的，並且一直引用同一篇部落格文章。
為什麼它們在算法上是理想的？
它們不一定是理想的。事實上，它們很少用於具有低延遲要求的生產交易系統。但是，您的消息來源可能有以下考慮：
- 他們被賦予了更多的工程目標而不是交易目標。如果沒有您應該優化的業務約束或查詢，合理的先驗是針對插入和刪除的最壞情況執行時進行優化，因為插入和刪除通常支配執行。
- 他們根據來自價格稀疏的資產類別（如股票）的樣本數據設計了這個訂單簿結構。
由於 (1) 和 (2)，他們需要考慮以下市場屬性：
- 新的價格經常被插入到書的外部，因為 (i) 內部水平往往是密集的，並且 (ii) 向內部的插入可能會被另一本書匹配和截斷。
- 形成一個新的水平給予了顯著的隊列優先級，並且向外的訂單具有更多的時間價值，因此價格水平不太可能因向外取消訂單而被移除，而更有可能因向賬簿內側取消或執行而被移除.
(3) 和 (4) 將促進不平衡且高的 BST，其攤銷執行時間比其理想化形式差得多。有多種方法可以緩解這種情況。自平衡只是一種幼稚的解決方案，因為紅黑樹在容器庫中得到了非常廣泛的實現，並且是一種簡單的保證方法 $ \mathbb{O}\left(\log n\right) $ 插入和刪除價格水平。
在評估最佳資料結構時，我會牢記以下三個主要主題。
1. 從業務案例開始
如：
- 您的應用程序需要優化哪些查詢？
- 本書的稀疏性。
- 圖書事件的統計分佈。
例如：
- 在期權工具中，訂單事件可能很少，因此將所有內容儲存在數組中并線性遍歷它們可能會更便宜。
- 在流動性期貨合約中，大多數事件只影響幾百個價格水平，價格帶可能會給你一個你真正關心的水平的界限，所以可以預先分配一個數組中的水平，並將指數價格表示為一個偏移量刻度數的一些初始狀態。
- 一些交易策略需要非常迅速地對本書頂部的更改採取行動，並且可以將 BBO 之外的級別插入或刪除推遲到以後，因此針對級別插入或刪除進行優化並不重要。
2. 了解消息傳遞協議和數據饋送
例如：
- 一些數據饋送是突發性的，因此您可以將應用程序設計為在執行業務操作的關鍵路徑（例如下訂單、模型更新）之前刷新所有數據事件。如果事件是批處理的，則最佳訂單簿結構可能會有所不同。
- 數據饋送中的連續事件可能有一些價格排序。
3. 硬體協同設計
在實踐中，當您在記憶體或記憶體訪問時間尺度上操作或處理與記憶體大小相關的少量事件時，漸近時間複雜度通常會超出視窗，查看實際實現和真實基準更為重要，並針對其執行的架構對您的訂單簿進行程式碼設計。
在這種情況下，具有線性訪問模式的簡單數組或向量通常會勝過任何具有更好漸近執行時間的複雜資料結構，因為簡單的數組可以更容易地利用更重要的硬體優化：
- 地方性
- 預取
- 指令流水線
- 將所有相關/合格數據放入更少的“頁面”中，這些“頁面”必須向上移動記憶體層次結構，例如，不跨越記憶體的非連續區域追逐指針。
- SIMD 內在函式。
這如何轉化為訂單簿設計？例如：
- 與具有少量訂單的儀器的訂單 ID 查找相比， C++ STL 實現的
unordered_map性能通常更差。map- 可以用一個侵入式雙向鍊錶來表示每個價格水平，它具有 $ \mathbb{O}\left(1\right) $ 查找相鄰節點，因此您可以取消連結已刪除的訂單 $ \mathbb{O}\left(1\right) $ . 但是，通過創建預分配數組的鍊錶並通過用墓碑標誌標記它們來刪除訂單，您通常會獲得更好的性能。
在我上面描述的許多情況下，數組的鍊錶或數組的數組將優於具有侵入性雙向鍊錶的紅黑樹的通用設計。