# 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.

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)$$.
• How do you handle cancellations? Commented Dec 23, 2022 at 22:39
• @BobJansen For the design referenced by the OP, you'd look up the canceled order ID on the hash map in O(1); the design is intrusive so the order object has pointers to the left and right nodes, allowing you to unlink the canceled order in O(1). The last order at a price level is canceled in worst case O(log N) in number of price levels N, but amortized constant time. Commented Dec 25, 2022 at 5:23
• Do you know about a good open source implementation in C++ of a LOB from MBO? Commented Jun 25, 2023 at 21:52
• @EnricoDetoma Unfortunately I don't. It's a commonly requested feature we get at Databento where I work, so we'll probably open source one soon. Commented Jun 26, 2023 at 5:28
• There are many repos on GitHub that you might find useful for this: github.com/… Commented Jun 26, 2023 at 5:29

“ 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.