6
$\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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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)$.
Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ How do you handle cancellations? $\endgroup$
    – Bob Jansen ♦
    Commented Dec 23, 2022 at 22:39
  • 3
    $\begingroup$ @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. $\endgroup$
    – databento
    Commented Dec 25, 2022 at 5:23
  • $\begingroup$ Do you know about a good open source implementation in C++ of a LOB from MBO? $\endgroup$
    – Enrico Detoma
    Commented Jun 25, 2023 at 21:52
  • 1
    $\begingroup$ @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. $\endgroup$
    – databento
    Commented Jun 26, 2023 at 5:28
  • 1
    $\begingroup$ There are many repos on GitHub that you might find useful for this: github.com/… $\endgroup$
    – databento
    Commented Jun 26, 2023 at 5:29
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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