Order Book Data Structure

An order book is the exchange's running record of every resting buy and sell order for an instrument. The mechanics page covers what it means; this page is about how you build one in code so that the four hot operations — add an order, cancel an order, match an incoming order, and read the best bid/ask — are all fast. It's a favorite interview at market-making and HFT firms precisely because a naive design is easy and a good one requires you to combine three data structures on purpose.

What the book must do quickly

• Add a new limit order at some price.
• Cancel a specific resting order by its id.
• Match an incoming aggressive order against the best opposing prices.
• Query the best bid and best ask (the top of book).

The rule the exchange enforces is price-time priority: better prices trade first, and among orders at the same price, the one that arrived earliest trades first. Your data structure has to encode exactly that ordering.

The three-part design

• Price levels, sorted. Keep bids and asks each in a structure ordered by price — a balanced BST / sorted map, or two heaps, or (when the tick grid is bounded) a plain array indexed by price. This gives you the best price at the top.
• A FIFO queue at each level. Every price level holds a queue of orders in arrival order, so time priority is automatic — new orders join the back, fills come off the front.
• An id → order map. A hash map from order id to the order's node, so a cancel is $O(1)$: jump straight to the order and unlink it, no scanning.

Worked example: a market buy hits the book

Using the book above, a market buy for 6 shares arrives. It sweeps the ask side from the best price outward, respecting price-time priority:

1. Take 3 @ 100 (all of the best ask, front-of-queue first). 3 shares filled, 3 remain to buy.
2. Move up a level to 101; take 3 @ 101 from the front of that level's queue. 6 shares filled — done.

The 101 level, which held 8, now rests with 5 remaining, and 100 is empty so the best ask becomes 101. Average fill price is $(3\times 100 + 3\times 101)/6 = 100.5$ — the buyer paid the spread and a little slippage for immediacy. That walk-up-the-levels loop is the matching engine in miniature.

from collections import deque

class Book:
    def __init__(self):
        self.asks = {}       # price -> deque of resting orders (FIFO)
        self.orders = {}     # order_id -> (side, price)  for O(1) cancel

    def add_ask(self, oid, price, qty):
        self.asks.setdefault(price, deque()).append((oid, qty))
        self.orders[oid] = ("ask", price)

    def cancel(self, oid):
        side, price = self.orders.pop(oid)          # O(1) lookup
        q = self.asks[price]
        q.remove(next(o for o in q if o[0] == oid))  # unlink from its level

    def match_buy(self, qty):
        for price in sorted(self.asks):             # best (lowest) ask first
            q = self.asks[price]
            while q and qty > 0:
                oid, resting = q[0]
                take = min(resting, qty)
                qty -= take
                if take == resting: q.popleft()      # fully filled -> pop
                else: q[0] = (oid, resting - take)    # partial fill
            if qty == 0: break

(In production the sorted(self.asks) scan is replaced by a sorted container or heap so the best price is $O(1)$ or $O(\log P)$, not $O(P\log P)$ each match — the sketch above just makes the priority explicit.)

Complexity and the array trick

With a balanced tree / sorted map: add is $O(\log P)$, best-price read is $O(1)$ (cached top), match is $O(1)$ per level touched, cancel is $O(1)$ via the id map, where $P$ is the number of distinct price levels. When ticks are bounded — say a stock quoted in whole cents over a known range — you can index price levels directly in a plain array, making every operation $O(1)$. That is why real matching engines love bounded tick grids.

If you can name the three structures, explain how each enforces one half of price-time priority, and handle partial fills and fast cancels, you've answered the question the way a desk wants to hear it. It draws on the same map-plus-ordered-structure instinct as an LRU Cache Design and leans directly on Heaps and Priority Queues and Queue Position and Priority.