# What is an efficient data structure to model order book?

What is an efficient data structure to model order book of prices and quantities to ensure:

1. constant look up
2. iteration in order of prices
3. retrieving best bid and ask in constant time
-

Since Quant Cup 1's objective was an efficient price/time matching engine, the data structure of the winning implementation might partly be what you are looking for.

Else the setup of LOBSTER is supposed to be quick.

-
Nice. I was thinking of a simple array based implementation. The best implementation in Quant Cup does something similar. – Sam Hayen Jul 10 '12 at 20:23
However, note that it will be less optimal when price levels are sparse and we care about every price level. – Sam Hayen Jul 10 '12 at 20:39

I do not know in which context you want to implement a matching engine (ME). But according to me the two nice challenges in this context are:

• implement one in an FPGA
• for simulation / fast replay purpose, design the most efficient in/out bus to put synthetic traders in front of the ME.

The last point is about simulating one day in few seconds.

To answer more directly your question, the reference is Josh Levine's code of Island in foxpro. Levin's has been one of the pioneer in the raise of electronic trading. It is not only an executable spec, but a piece of history.

-

If you assume that most updates will happen near the top of the book (a fair assumption) a linked-list ordered by price levels will be very efficient.

You can check CoralMD for an example of a very fast, garbage-free market data book implementation that provides not just the global view of the market (all exchanges) but also a per-exchange book view. It also provides the infra-structure to write exchange feeds and to distribute market data internally.

Disclaimer: I am one of the developers of CoralMD

-

Why not just implement it with two price-amount maps, as shown here?

-
That level book uses std::map which is not cache efficient. Good tutorial though. – Maxim Egorushkin Mar 21 at 17:58