Order Book Mechanics in Matching Engines

What an order book is

An order book is a sorted list of buy orders (bids) and sell orders (asks) for a financial instrument. Bids are sorted highest-price-first. Asks are sorted lowest-price-first. The gap between the best bid and best ask is the spread.

Asks (sell orders):
  $101.50  x  200 shares
  $101.25  x  500 shares
  $101.00  x  150 shares  ← best ask
  ─────────────────────
  $100.75  x  300 shares  ← best bid
  $100.50  x  100 shares
  $100.25  x  450 shares
Bids (buy orders)

When a new order arrives, the matching engine checks if it can trade against existing orders on the other side. A buy order at $101.00 or higher would match against the best ask at$101.00. A buy order at $100.90 sits on the book as a new bid.

Price-time priority

Most exchanges use price-time priority (also called FIFO matching). Orders are ranked first by price (better prices first), then by arrival time (earlier orders first within the same price level).

struct Order {
    id: u64,
    side: Side,
    price: Price,
    quantity: u64,
    timestamp: u64,
}

struct PriceLevel {
    price: Price,
    orders: VecDeque<Order>,
    total_quantity: u64,
}

struct OrderBook {
    bids: BTreeMap<Price, PriceLevel>,
    asks: BTreeMap<Price, PriceLevel>,
}

When a marketable order arrives (a buy at or above the best ask), the engine walks the ask side starting from the best price. At each price level, it fills against orders in FIFO order until the incoming order is fully filled or the price level is exhausted.

impl OrderBook {
    fn match_buy(&mut self, mut order: Order) -> Vec<Fill> {
        let mut fills = Vec::new();

        while order.quantity > 0 {
            let Some((&ask_price, level)) = self.asks.first_key_value_mut() else {
                break;
            };

            if ask_price > order.price {
                break;
            }

            while order.quantity > 0 && !level.orders.is_empty() {
                let resting = level.orders.front_mut().unwrap();
                let fill_qty = order.quantity.min(resting.quantity);

                fills.push(Fill {
                    price: ask_price,
                    quantity: fill_qty,
                    maker: resting.id,
                    taker: order.id,
                });

                order.quantity -= fill_qty;
                resting.quantity -= fill_qty;

                if resting.quantity == 0 {
                    level.orders.pop_front();
                }
            }

            if level.orders.is_empty() {
                self.asks.pop_first();
            }
        }

        if order.quantity > 0 {
            self.bids.entry(order.price)
                .or_insert_with(|| PriceLevel::new(order.price))
                .orders.push_back(order);
        }

        fills
    }
}

Data structure choices

The hot path in a matching engine is:

1. Find the best price level (O(1) with a cached pointer)
2. Match against orders at that level (O(1) for the front of a queue)
3. If the level is exhausted, move to the next price level (O(log n) in a tree)

Production matching engines at exchanges like NASDAQ and LSE typically use array-based structures indexed by price tick. If the price can range from $0.01 to$999.99 in $0.01 increments, that is 100,000 slots. A flat array indexed by (price - min_price) / tick_size gives O(1) insert and cancel.

The best bid/ask pointers are maintained incrementally. When the best bid level empties, you scan backward to find the next non-empty level. In practice this is usually one or two steps because order books are densely populated near the top.

Queue position matters

In a FIFO matching engine, your position in the queue at a price level determines whether you get filled. If there are 10,000 shares ahead of you at $100.75, a market sell order of 5,000 shares won't reach you.

This is why high-frequency traders care about latency at the microsecond level. Being 1 microsecond faster can put your order earlier in the queue at the same price level. Over thousands of trades, better queue position translates directly to better fill rates.

Market impact and toxicity

Every order that trades against the book has market impact. A large buy order that sweeps through multiple price levels moves the price up. The "depth" of the book determines how much size can trade before the price moves significantly.

Before large buy:          After 5000-share buy:
Ask $101.50 x 200          Ask $101.50 x 200
Ask $101.25 x 500          Ask $101.25 x 500
Ask $101.00 x 150          Ask $101.00 x ← consumed
─────────────               ─────────────
Bid $100.75 x 300          Bid $101.25 x 4350 (remainder)

Smart order routing algorithms split large orders into smaller pieces to minimize this impact. They might send 500 shares every 30 seconds instead of 5,000 at once, or route to different venues to avoid depleting any single order book.

Building a simulated order book

If you are building a backtesting engine or a market simulator, a BTreeMap<Price, VecDeque<Order>> can handle millions of operations per second in Rust. That is enough for many simulations. Focus on matching semantics and FIFO correctness before optimizing the data structures.