Match buy and sell stock orders
Match buy and sell stock orders
Stocks go up and down. Do you know what data structure is used to efficiently match buy and sell orders?
Stock exchanges use order books. An order book is an electronic list of buy and sell orders, organized by price levels. It has a buy book and a sell book, where each side of the book contains a bunch of price levels, and each price level contains a list of orders (first in first out).
The diagram below is an example of price levels and the queued quantity at each price level.
So what happens when you place a market order to buy 2700 shares in the diagram?
- The buy order is matched with all the sell orders at price 100.10, and the first order at price 100.11 (illustrated in light red).
- Now because of the big buy order which “eats up” the first price level on the sell book, the best ask price goes up from 100.10 to 100.11.
- So when the market is bullish, people tend to buy stocks aggressively, and the price goes up and up.
An efficient data structure for an order book must satisfy:
- Constant lookup time. Operations include: get volume at a price level or between price levels, query best bid/ask.
- Fast add/cancel/execute/update operations, preferably O(1) time complexity. Operations include: place a new order, cancel an order, and match an order.
First filter out, invalid requests such as requests placed outside stock exchange working hours, requests from clients without sufficient funds, etc. Next, we can first separate the buy and sell orders into separate heap (or priority queue) data structure, with the highest buying price at the top of the buy queue and the lowest selling price at the top of the sell queue. Then, we can iterate through both queues and match orders based on price until one of the queues is empty.
Low level design of a stock exchange very well explained.