Choosing an Order-Book Data Structure

The order book is the one data structure a matching engine touches on every single message. Its shape decides your p50, and — more importantly — your p99. This page is about choosing it: not by textbook Big-O, but by how each option behaves on the hot path, under a real order flow, on real hardware.

The headline up front: there is no universal winner. The right structure depends on the shape of your book — how wide the price band is, how densely levels are populated, and how many orders queue at each level. The canonical reference for fast books says exactly this: the best choice “depends mainly on the sparsity of the book.”¹ Liquidity is that sparsity, so we give it its own section below.

Every order book is the same three things

Before comparing structures, fix the anatomy. Whatever you pick, a limit-order book is three cooperating pieces:

A price-level index — maps a price to the level sitting at that price. This is the structure this page is about. Array, tree, skip list, linked list, hash, or radix tree — they are all just different ways to answer “where is the level at price P, and what is the best price right now?”
A FIFO queue per level — price-time priority means each level is a first-in-first-out queue of resting orders. This is almost always a doubly-linked list of order nodes, and it is the same regardless of which index you pick above.
An order-ID → order map — a hash table (or an intrusive pointer handed back to the client) that locates any resting order in O(1) without walking the book. This is what makes cancels and amends cheap, and it too is independent of the price-level index.

Pieces 2 and 3 are effectively fixed. The whole design decision is piece 1 — and the reason it’s subtle is piece 3’s workload, next.

The load-bearing constraint: cancels dominate

The single most important fact about real order flow is that it is overwhelmingly cancels, not trades. In US equity markets, 97% of orders are cancelled before they ever trade.² Add-then-cancel churn — from market-making and quoting algorithms constantly repricing — dwarfs executions by more than an order of magnitude.

That reshapes the priority order for the structure:

Cancel/amend must be O(1). This is why the order-ID map exists: you never search for the order you’re cancelling; you jump straight to its node and unlink it. Every structure below inherits this, so cancel cost is essentially a constant across all of them — the differentiator is insert and best-price cost.
Insert is the hot operation that actually varies. New resting orders arrive constantly and must find (or create) their price level. This is where the price-level index earns or loses its keep.
Best-bid / best-offer is read on nearly every message (to test for a cross). It must be O(1) — which for every structure below means caching the best price and maintaining it incrementally, never re-searching for it.

Keep this ranking in mind — cancel O(1) (given), insert cheap, best-price cached — while reading the comparison.

The six candidates

Structure	Core idea	Best / insert / cancel	Cost vs. book size	Liquidity fit
Direct-indexed array (price grid)	Pre-allocated array indexed by tick; each cell is a level’s FIFO queue	O(1) / O(1) / O(1)	Bounded by the configured price band — effectively constant	Narrow band, dense — liquid pairs on a fixed tick
Balanced BST (red–black / AVL)	One tree node per active price level	O(1)* / O(log L) / O(1)	Grows like log L in active levels	Wide band, sparse — general-purpose
Skip list / hybrid	Multi-level index: coarse search, then short linear scan	O(1)* / O(log L) / O(1)	Sub-linear; grows slowly as the book deepens	Very deep / sparse books
Linked levels + aux index	Doubly-linked list of levels + a map/array to find a level node	O(1) / ~O(1) near top, up to O(L) deep	Hot-path cost mostly independent of total depth	Any band, activity at the top
Hash map + heap/tree	Hash `price → level`; a separate heap/tree tracks the best price	O(1)* / O(log L) / O(1)	Depends on load factor + log L	Irregular / sparse grids
Adaptive radix tree (ART)	Radix tree over the fixed-width integer tick; node fan-out adapts (4/16/48/256) to occupancy	O(1)* / O(k) / O(1)	Bounded by key width k, independent of level count	Adaptive — dense regions turn array-like, sparse regions stay compact

*Best price is O(1) in all cases only because you cache and incrementally maintain the min/max. L = number of active price levels (which is << the number of orders); k = the price key’s fixed byte width (≤ 8 for a 64-bit tick), so O(k) is a hard constant bound, not a function of the book.

1. Direct-indexed array (price grid)

Pre-allocate a flat array covering a price band; index it by (price − floor) / tick. The cell at that index holds the level’s FIFO queue. Insert, cancel, and best-price all become O(1) array indexing.¹ There is no search, no rebalancing, no pointer-chasing — and because the array is contiguous, it is exquisitely cache-friendly (see mechanical sympathy below).

The cost is memory and boundedness: you pay for the whole band whether or not levels are populated, and prices outside the band need a fallback. The canonical fast-book article notes the pure-array variant “will give O(1) always for add operations, but at the cost of making deletion/execution of the last order at the inside limit O(M)” unless you also track the best level incrementally — which you do, via the cached best-price pointer.¹ For a liquid instrument on a known, fixed tick — a typical spot crypto pair — this is often the fastest structure that exists.³

2. Balanced binary search tree (red-black / AVL)

One node per active price level, kept sorted. Inserting or removing a level is O(log L); best price is O(1) if you cache the min (asks) / max (bids) node and refresh it on removal. This is the textbook design and the most general — it handles arbitrarily sparse, unbounded prices with no band configuration. In C++, std::map is a red-black tree with logarithmic search/insert/erase,⁴ and it’s the default first implementation in countless engines.

Its weakness is mechanical, not asymptotic: tree nodes are heap-scattered, so every insert pointer-chases from root to leaf across cache lines, and rebalancing writes touch even more. Under micro-bursts this produces tail-latency spikes — one analysis of the standard “linked lists chained through a balanced tree” design attributes the spikes to exactly two costs: “pointer-chased traversal to reach the insertion point, and a root-to-leaf search to locate the target price level.”⁵ Clean theory, but it can hurt p99 for deep books.

3. Skip list / hybrid binary–linear

A skip list gives probabilistically O(log L) search via stacked express lanes, then a short local scan. Some engines use a hybrid: a coarse index to a price band, then a linear scan over the handful of levels in that band. The appeal is sub-linear cost that degrades gracefully as a book gets very deep, with simpler concurrency than a balanced tree.

In practice it shares the tree’s Achilles’ heel — the express lanes are still pointers, so it still chases cache lines — and dedicated, benchmarked skip-list order books are surprisingly scarce in the literature. Treat it as a sound O(log L) option for very deep/sparse books, but don’t expect it to beat a tuned array on hot-path latency.³

4. Linked levels + auxiliary index

Keep the price levels as a doubly-linked list (each level knows its neighbor levels), plus an auxiliary map or array to jump to a level node directly. Operations near the best price are ~O(1) — you’re already at the front of the list — but reaching a level deep in the book without the index is an O(L) walk. Since order activity clusters near the inside, the hot path is mostly independent of total depth. This is essentially the structure the canonical fast-book design describes: a sorted list of levels, each a FIFO queue, with a price → level map as the index that avoids the deep walk.¹ It leans hard on free-lists and careful pointer/node-pool management to stay allocation-free.

5. Hash map by price + heap/tree

Hash price → level for expected-O(1) level lookup, and keep a separate heap (or tree) that tracks the best price at O(log L) per update. Cancels stay O(1) via the ID map. It’s flexible for irregular or very sparse grids where an array would waste memory and a tree’s ordering isn’t needed.

The reason it’s rarely seen in the strictest hot path is overhead you can’t schedule: hashing has variable latency and cache-miss behavior, and a heap gives you only the single best price — not the ordered neighborhood you need to sweep through levels when a marketable order walks the book. That’s engineering judgment, not a cited law, but it’s why hot-path designs tend to shed hash/heap indirection in favor of arrays or intrusive linked levels.

6. Adaptive radix tree (ART)

A radix (prefix) tree over the price’s fixed-width integer representation, with the twist that makes it practical: each inner node adapts its size to how many children it actually holds (Node4 → Node16 → Node48 → Node256), and path compression plus lazy expansion remove the long single-child chains a plain trie would waste on sparse keys.⁶ Because the price tick is a fixed-width key, every operation costs O(k) in the key’s byte length — at most 8 byte-hops for a 64-bit tick, regardless of how many levels exist — and keys stay in bitwise lexicographic order, so min/max, range scans, and “walk the ordered neighborhood of the best price” all work natively — exactly the ordered operations the hash+heap combination struggles to provide.⁶

What earns ART a seat here is that it adapts across the liquidity regimes below instead of picking one end:

In a dense region of the book, the hot nodes grow into Node256 — literally a 256-slot array indexed by the next key byte — so lookups degenerate toward the direct-indexed array’s single-lookup behavior.⁶
In a sparse region, the small node types plus path compression keep memory proportional to the active levels (the paper proves a worst-case bound of 52 bytes per key), where a price-grid array would pay for the whole empty band.⁶

The flagship implementation is exchange-core, an open-source Java matching engine whose OrderBookDirectImpl indexes both sides’ price buckets and the order-ID map with a custom LongAdaptiveRadixTreeMap; its README reports ~5M ops/s with p50 ≈ 0.5 µs / p99 ≈ 4 µs at 1M ops/s — self-reported numbers, but the implementation is open and readable.⁷ The honest caveat: ART order books are rare in practice — one prominent engine and its forks, not an industry default — and ART still chases pointers between nodes, so on a small, dense, known band the flat array it partially imitates remains the structure to beat.

How liquidity shapes the choice

Everything above collapses to one question: what does your liquidity look like? Liquidity isn’t a single number — it’s three independent levers, and each one pushes toward a different structure. Get these three right and the choice makes itself.

The three levers

Price-band width = (highest price − lowest price) / tick = the number of possible price slots. This is the array’s whole cost model: a narrow band (a liquid pair pinned near a stable price on a coarse tick) is a small, cheap grid; a wide band (a low-unit-price token quoted to eight decimals, or a long-dated instrument ranging widely) is a huge grid that’s mostly empty. The array’s memory is O(band width) regardless of how many levels are actually populated.
Level density / occupancy = active levels L vs. the possible slots in the band. A dense book fills most slots near the top; a sparse book scatters a few levels across a wide range. Trees and skip lists cost O(log L) — they don’t care about band width at all, only about how many levels actually exist. This is the exact axis the canonical reference means by “sparsity of the book.”¹
Orders per band (queue depth per level) = N / L, orders divided by active levels. When many orders stack at each price, L stays small even for a huge order count N — and since the price-level index cost is a function of L, deep queues make the index cheap for every structure (the work shifts into the per-level FIFO, whose ops are all O(1)). When each level holds only one or two orders, L balloons toward N, and the index structure’s per-level cost is what dominates. This is why the field’s rule of thumb is L << N (levels far fewer than orders):¹ the more it holds, the less your index choice matters.

The regime matrix

Liquidity regime	Band width	Levels (L)	Orders / level	Best fit	Why
Deep & tight — liquid crypto pair, fixed tick	Narrow	Small, dense	High	Direct-indexed array	Small dense grid → O(1) with zero pointer-chasing; queue depth keeps L tiny
Thin & wide — illiquid name, many decimals, long tail	Wide	Small but scattered	Low	Balanced tree / skip list	Array would be a huge, mostly-empty grid; `O(log L)` ignores band width
Bursty at the top — heavy make/cancel churn at the inside	Any	Deep tail, hot top	Mixed	Linked levels + aux index	Hot path lives at the best price → ~O(1); rarely-touched tail can be deep
Many shallow symbols — one cluster hosts hundreds of thin books	Varies	Small each	Low	Tree / hash, compact per book	Per-book memory dominates; a per-symbol array grid would waste RAM ×N books
Mixed / shifting — dense inside, sparse tail, or liquidity that migrates	Any	Varies over time	Mixed	Adaptive radix tree	Node sizes adapt per region: dense top ≈ array (Node256), sparse tail stays compact; O(k) bound regardless

Reading it as a decision

Narrow band + dense (a liquid spot crypto pair on a fixed tick): the array wins outright. “For certain markets (like crypto or a specific product where the price range is known), a simple array-based approach might be faster than a tree.”³ Real implementations that start on std::map for generality routinely migrate to a flat array once the range is known to be bounded.
Wide band + sparse (long-dated options, illiquid names quoted to many decimals): a tree or skip list earns its log factor. Their cost tracks active levels, not band width, so a book that spans a huge price range but only ever has a few dozen live levels stays cheap — where an array would allocate (and cache-miss across) an enormous, mostly-empty grid.
High orders-per-level regardless of band keeps L small, which flatters every structure and widens the array’s lead (tiny grid, deep O(1) queues). Low orders-per-level (many thin levels) is the case that punishes the array’s memory and rewards the log-time structures.
Activity concentrated at the top regardless of tail depth: linked levels + index keep the hot path near O(1) while tolerating a deep, rarely-touched tail.
Can’t commit to one regime — dense at the inside, sparse in the tail, or a book whose shape shifts with liquidity: the ART covers both ends from a single structure, at the cost of a few pointer hops the pure array never pays. It’s also a pragmatic answer to the caution below — a volatility gap can’t overflow it the way it overflows a fixed band.

Why arrays beat trees in practice

The recurring theme above — arrays and intrusive lists winning despite equal-or-worse Big-O — is mechanical sympathy: writing software that works with the hardware, a principle popularized by HFT engineer Martin Thompson (of LMAX Disruptor fame).⁸ The core facts:

CPUs move memory in cache lines (commonly 64 bytes), and the hardware prefetcher rewards predictable, sequential access.⁸ A contiguous array of levels streams into cache; a tree of heap-scattered nodes defeats the prefetcher, turning each hop into a potential cache miss.
Big-O counts operations, not cache misses. For the collection sizes a hot book actually holds, a linear scan over contiguous memory routinely beats a “faster” pointer-based structure — the crossover where log-time structures pull ahead can be surprisingly large, and it depends heavily on element size and access pattern.

This is the same argument the rest of this site makes for NUMA & cache locality and core isolation: on the hot path, removing variance matters more than shaving an asymptotic factor. A tree’s O(log L) is real, but its cache misses are what show up in your p99.

How this maps onto Aeron Cluster

On a clustered matching engine, the order book lives inside a single deterministic state machine — the actor per symbol. Two consequences follow directly from that model:

Single-writer means no concurrent structure needed. Because exactly one thread owns a book and processes the replicated log in order, you never need a lock-free or concurrent variant of any structure above. You get to pick the fastest single-threaded layout — which is precisely why the array’s mechanical-sympathy win is available to you. Aeron® Cluster’s single-writer discipline is the enabler, not a constraint.
The snapshot serializes the whole book. Cluster snapshots walk every resting order in every resident book, so your structure’s size and traversal cost become a snapshot-time and recovery-time cost too — another reason a compact, contiguous layout pays off, and another reason a wide, sparse array grid hurts. See Cluster Standby & HA design for how async snapshots keep this off the hot path.

For the internals of how Aeron lays out its own log and term buffers for cache locality, we defer to The Aeron Files rather than duplicate them here.

Anti-patterns

Re-searching for the best price on every message. Best-bid/offer must be a cached, incrementally maintained pointer — never an O(log L) or O(L) lookup on the hot path.
Cancelling by searching the book. Cancels dominate flow;² without the order-ID map you turn the single most common operation into a walk. Always O(1) via the index.
Sizing an array’s band for the calm case. A volatility gap that exceeds the configured band overflows the grid; size for stress and keep a tree fallback for the tails.
Allocating on the hot path. New levels/orders must come from a pre-sized free-list or node pool, or GC/malloc jitter will own your p99. (On the JVM, this compounds with GC pauses and JIT warmup — see tuning methodology.)
Specializing to an array before measuring. A wide or sparse book will overflow or waste a price-grid array; confirm the band is narrow and densely populated on your data first.

Sources

WK Selph, “How to Build a Fast Limit Order Book” (archived) — the de facto practitioner reference: a price-level structure of FIFO queues plus a price → limit map and an id → order map; the array-vs-tree cost trade-off “depends mainly on the sparsity of the book,” and M (price levels) is “generally << N (orders).” ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶
Marta Khomyn & Tālis J. Putniņš (2021), “Algos gone wild: What drives the extreme order cancellation rates in modern markets?”, Journal of Banking & Finance 129 — “97% of orders in US stock markets are cancelled before they trade.” Peer-reviewed. (Open-access PDF.) ↩ ↩²
A. Kishlaly, “Building a sub-100µs matching engine” — engineering blog: “for certain markets (like crypto or a specific product where the price range is known), a simple array-based approach might be faster than a tree.” Cited as practitioner opinion. ↩ ↩² ↩³
cppreference — std::map — “Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.” ↩
Jake Yoon, “The World’s Fastest Matching Engine Algorithm”, arXiv preprint — attributes tail-latency spikes in the standard “linked lists chained through a balanced tree” design to pointer-chased traversal and root-to-leaf search. Cited for that qualitative argument only; its performance claims are an unreviewed preprint. ↩
Viktor Leis, Alfons Kemper, Thomas Neumann, “The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases”, ICDE 2013 (DOI) — adaptive node types Node4/16/48/256; lazy expansion and path compression; “all operations have O(k) complexity where k is the length of the key”; keys ordered bitwise lexicographically, supporting “range scan, prefix lookup, top-k, minimum, and maximum”; worst-case space “52 bytes for any adaptive radix tree”; “Dense keys… are the best case, and can be stored space efficiently.” ↩ ↩² ↩³ ↩⁴
exchange-core (Apache-2.0) — OrderBookDirectImpl declares LongAdaptiveRadixTreeMap<Bucket> askPriceBuckets / bidPriceBuckets and an ART-backed order-ID index; the ART classes (exchange-core/collections, ArtNode4/16/48/256) cite the Leis et al. paper directly. README performance figures (~5M ops/s; p50 0.5 µs / p99 4 µs at 1M ops/s) are the project’s own benchmarks — self-reported, matching+risk only, no network or journaling. ↩
Martin Fowler, “Mechanical Sympathy” principles — the term was popularized by HFT engineer Martin Thompson; memory moves in 64-byte cache lines and the prefetcher rewards predictable, sequential access. ↩ ↩²