Order book engineering: data structures and the operations they serve

The limit order book is the canonical systems design question at a trading firm, and it is a good one because the right answer comes entirely from the operation mix. Cancels dominate, the best prices are read constantly, and the price grid is dense and bounded — and those three facts determine the structure.

Operation	Frequency	Required
Cancel by order id	Highest — most orders are cancelled	$O(1)$
Read best bid and offer	Every decision	$O(1)$
Add at a price	High	$O(1)$
Match against the book	Lower	$O(1)$ amortised per level
Walk several levels of depth	Occasional	$O(\text{levels})$

Table 6.1 · The operations, by frequency. Cancels outnumber trades by one or two orders of magnitude on most venues, so a design that makes cancellation cheap at the expense of anything else is usually right.

Proposition 6.2

The standard design

An array of price levels indexed by tick, each holding an intrusive doubly linked list of orders in time priority, plus a hash map from order id to the node. The array gives $O(1)$ price access, the list gives FIFO with $O(1)$ removal given the node, and the map turns a cancel into a lookup and an unlink.

Holds when

Tick grids are dense and bounded around the touch, so an array beats a tree comfortably.
Intrusive lists put the pointers inside the order object, so unlinking needs no search and no allocation.
Cache the best bid and offer indices and update them on change rather than scanning.

Figure 6.3 · One price-level update, ten thousand levels. The book is updated far more often than it is walked, so the structure should be chosen for the update. Indexing an array by tick makes it a single write — the cost is memory proportional to the price range, which is why the trick works for equities and not for a sparse options chain.

Why an array beats a tree here. The textbook answer is a balanced tree keyed on price, and it is the right answer for a sparse, unbounded key space. A tick grid is neither: prices move by single ticks, the active range is a few hundred levels wide, and the mapping from price to index is arithmetic. So the tree’s $O(\log n)$ with a cache miss per level loses to an array’s $O(1)$ with one contiguous access — and the array is simpler. The general lesson is that asymptotic reasoning chooses the tree and the actual key distribution chooses the array.

Proposition 6.4

When the array does not work

Some instruments have very wide or unbounded price ranges — long-dated options, crypto, anything without a tick size. A flat array would be enormous and mostly empty, so the usual answer is a circular buffer covering a window around the touch, shifted as the market moves, with a fallback structure for the tails.

Holds when

The window must be wide enough that a fast move does not fall out of it.
Shifting costs a bounded amount of work, done off the critical path where possible.
A flat hash map plus a separately maintained best-price cache is the simple alternative.

Order book engineering: data structures and the operations they serve

After this lesson you should be able to

The standard design

When the array does not work

The rest of this lesson is in Premium