3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.