Order Book Data Structures and Constant-Time Lookups
Summary
The document examines complexity claims for limit order book implementations built from balanced trees. A conventional search in a balanced tree takes logarithmic time, but the answers explain that practical designs commonly combine separate price-level trees for bids and asks with a hash map keyed by order ID. Maintaining direct references to the best bid and ask can avoid searching the tree to retrieve the current top prices, while the hash map can locate an order directly for cancellation.
Price levels may hold linked lists of orders, so adding or removing an order at a known level can be constant time when the implementation retains the necessary references. The discussion distinguishes those operations from locating an arbitrary price level, which may still require a tree lookup unless another index or direct link is maintained. It also cautions that the cited implementation advice may be dated and suggests considering cache-friendly structures. The answers are brief and do not specify full complexity bounds for every update pattern or compare implementations empirically.
Key ideas
- A typical book uses separate sorted structures for bids and asks, alongside an order-ID hash map.
- Maintaining direct best-price references can make top-of-book retrieval constant time.
- A hash map can locate an order by ID without scanning price levels.
- Adding or removing within a known price-level list can be constant time when direct references are available.
- Finding an arbitrary price level may still require a tree search, and cache behavior can affect practical performance.
Tags
Full text
# Complexity of using balanced-tree to model order book
# Complexity of using balanced-tree to model order book
I have bene researching on the best data structure to implement a limit order book. Some of the most common implementations include arrays and balanced trees. This link has a good set of references.
Most of the proponents of balanced binary trees (such as Red-Black Tree) claim that the time complexity to add, cancel and execute orders to the limit order book is O(1).
"For a sparse book like US equities, you'll usually want to organize your price levels as 2 red-black trees (one for bid side, one for ask side), each price level as a doubly-linked list, and then hold a separate hash table for your orders. This lets you have O(1) access to BBO price and size, O(1) to cancel any order based on its order ID, and also O(1) to append to the top of the book."
Isn't the complexity to iterate through the tree to find the max (min) price to get the best bid (ask) O(log N)? In addition to append an order to the top of the book, we have to iterate the tree to the appropriate price level and from there, add to the head of the linked-list. Hence, isn't this complexity also O(log N)? Furthermore, to cancel an order, don't we have to iterate to the appropriate price level and remove the order from the linked-list?
Why do some people claim that the complexity to get best-bid and ask , append to top of the book and cancel Orders be O(1)?
Thank you.
## Answer by databento (score 4)
https://quant.stackexchange.com/a/74174
You won't usually implement a single tree. You'd usually implement a pair of trees (one for bid side, other for ask side) AND a hash map.
- Since each tree is sorted, you can get the max ask and min bid in $\mathbb{O}\left(1\right)$.
- Through the hash map, you can look up any order ID in $\mathbb{O}\left(1\right)$.
## Answer by experquisite (score 0)
https://quant.stackexchange.com/a/63143
“ and each Limit is also an entry in a map keyed off limitPrice.”
You don’t spend O(log N) in the tree to find a price, that is a hash at worst. Might want to keep direct BBO links into the tree. Also this info is a bit dated, you probably really want cache-friendlier structures. Intrusive linked lists, flat maps etc.Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.