Order Book Data Structure and Arbitrage Detection

Design and implement an order book data structure that supports the following operations: 1. **Add order** -- insert a new limit order (buy or sell) at a given price with a given quantity. 2. **Cancel order** -- remove an existing order by its ID. 3. **Match orders** -- when a new order arrives, match it against resting orders on the opposite side using price-time priority. 4. **Query best bid/ask** -- return the current top-of-book on each side. Your implementation should be optimized for low-latency trading. Discuss the time complexity of each operation and explain what data structures you would use. Then extend the design to handle **multi-venue arbitrage detection**. Suppose you maintain order books for the same instrument across $N$ exchanges. How do you efficiently detect when $\text{best\_ask}_i < \text{best\_bid}_j$ for some pair of venues $i \neq j$, and what data structures or caching strategies make this fast? Provide working code for the core single-venue order book, and describe the multi-venue extension in detail.