Implementation

Implementation

Historical record; annotated 2026-08-14. This describes the original pure-Python design: a red-black tree of OrderList objects per side, each a doubly linked list of Orders. That implementation was replaced by PR #7 in 2023, and the SQL-backed engine that replaced it was itself retired in 2026 (ADR-0003). Neither the tree nor the classes named below are in the code today. The current engine keeps, per side, a dict of price to price level and two heaps of prices for the two ends of the book, with each level's queue an insertion-ordered dict; matching lives in src/PyLOB/engine.py.

What survives is the reasoning. The motivation in the first three paragraphs — why a limit order book has to be fast, which operations dominate, and why price-time priority suggests a list-of-lists — is still exactly why the current engine is shaped as it is, and the operation costs below are still the costs it targets. The engine's own cost table, which is the accurate one, is in the src/PyLOB/engine.py module docstring.

The text below is left as it was written; only this note is new. For how the library works now, see the Usage walkthrough and the README.

Given the nature of fast paced, low-touch nature of the majority of trading activity these days it is imperative that limit order books operate efficiently. To give an idea of the kind of volume to expect, the Nasdaq TotalView ITCH feed (shows every instrument traded in Nasdaq) can have data rates of 3 Mb/second or more. Given that one message is around 20 bytes each, this means handling 100,000-200,000 messages/second.

In a simulated environment we may not need to be quite this fast, but certain LOB operations will always be hammered, even in simulation, so speed is something to keep in mind. The majority of activity in real world LOBs is made up of add and cancel operations as high-frequency market makers jostle for position, with executions a distant third. The goal is to implement these operations in O(1) time while allowing the model to be probed with questions like "what are the best prices?" or "how much volume is there at price X?".

Given that we want to use the price-time-priority model use by most modern exchanges, the simplest way to imagine a LOB is as a pair of list of lists, as shown below:

In the visualisation above, the bids and asks can be seen as separate lists of limit prices that each contain a list of all of the orders at that price. At each price, the list of orders is sorted according to its time of arrival. In the figure above, the orders labeled "1" arrived first. An add operation places an order at the end of one of a list of orders to be executed at a particular limit price and a cancel operation removes an order from anywhere in the book. An execution removes an order from the inside of the book, that is the oldest buy order at the highest price and the oldest sell order at the lowest price.

In order to keep things fast, I chose to use a red-black binary tree of OrderList objects sorted by Price, each of which is itself a doubly linked list of Order objects. Each side of the book is represented with a separate tree so that the inside of the book corresponds to the end and beginning of the buy Limit tree and sell Limit tree, respectively. Each order is also an entry in a map keyed off idNum, and each OrderList is also an entry in a map keyed off Price.

This structure allows the key operations to operate with the following performance:

• Add - O(log M) for the first order at a price, O(1) for all others
• Cancel - O(1)
• Execute - O(1)
• GetVolumeAtLimit - O(1)
• GetBestBid/Offer - O(1)

where M is the number of OrderLists (prices).