The Order Book Data Structure

How Perpl achieves O(1) insert and cancel on a fully on-chain CLOB — while every sorted-tree alternative scales in cost with the size of the book.

Building a central limit order book entirely on-chain is the hardest engineering problem in DeFi. Every comparison, traversal, and structural update costs gas. Most perpetual DEXes responded by moving order matching off-chain entirely, sacrificing the transparency that makes a DEX meaningful. The ones that stayed on-chain paid in user-facing gas costs that make market-making economically punishing.

Perpl's CLOB achieves a complete post-and-cancel cycle at 100k gas — cheaper than a Uniswap V2 AMM swap at 200k gas. This is possible because of a purpose-built data structure that replaces sorted-tree traversal with direct bitmap lookup. Insert and cancel are O(1) constant time, always, regardless of how deep the book is.

The Industry Default: Sorted Trees

An order book must efficiently answer two questions: what is the best available price? and what orders exist at that price? The textbook answer for maintaining sorted access with fast insertion and deletion is a balanced binary search tree — a red-black tree or B-tree.

These structures work well in memory. Each internal node stores a price level. Insertion places the new price in its sorted position. The tree self-balances via rotations and recoloring to maintain logarithmic height. Finding the best bid or ask is simply reaching the minimum or maximum leaf.

On the EVM, this design is a gas disaster. Balanced tree operations require reading and writing multiple storage slots per operation, and the number grows with the size of the book:

comparisons = O(log N) — traverse from root to insertion point
rebalancing = O(log N) — rotations and recolors propagate up toward root
total SSTOREs = O(log N) — each structural change writes a storage slot N = number of active price levels. At N = 10,000: ~13 storage operations minimum per insert.

Figure 1: Red-Black Tree — Insert Triggers a Rebalancing Cascade

A single insert into a red-black tree with N price levels requires O(log N) reads to find the insertion point, then O(log N) writes as rotations and recolors cascade upward. Deletion is equally expensive. Both operations grow with book depth — there is no constant-time path.

Rebalancing is the core problem. After inserting a new node, the tree's red-black invariants may be violated and must be restored by rotating subtrees and recoloring nodes — potentially propagating all the way to the root. Each rotation writes two nodes. Each recolor writes one. A delete triggers "double-black" fixup, which can be even more expensive.

The market maker tax: A market maker updates quotes as price moves — typically a cancel followed by a re-post at the new price. On a sorted-tree CLOB, that's two O(log N) write operations per requote. Every storage write on EVM costs gas. As the order book fills up, each requote gets more expensive — directly increasing the minimum spread a market maker can profitably quote.

Perpl's Bit-Index Tree: O(1) by Design

Perpl's key observation: prices are integers in a bounded range. They don't need to be maintained in a sorted tree — they can be indexed in a bitmap. If a price level has orders, its bit is set to 1. If empty, it's 0. Finding the best available price is finding the lowest or highest set bit — a single bitwise scan of a 256-bit word.

The bit-index tree scales this bitmap idea across three levels of hierarchy. Each level is a single 256-bit storage slot. A bit set at a higher level signals that at least one price in that sub-range is occupied. This structure covers over 16 million distinct price levels using exactly three slot reads to locate any price — and exactly three slot writes (at most) to insert or delete any order.

levels = 3 capacity = 256³ = 16,777,216 price levels
insert = set bit in leaf → propagate up if level was zero → O(1)
cancel = clear bit in leaf → propagate up if level is now zero → O(1) Each level is one 256-bit word. The maximum structural change is three bit-flips. Always.

Figure 2: Bit-Index Tree — Insert an Order at Price P

Inserting at a new price: flip the leaf bit. If the mid-level word for that range was previously zero, flip the mid bit too. If the root was zero, flip the root. At most 3 writes — always. Cancel works in reverse: clear the leaf bit, clear mid if the word is now zero, clear root if the mid word is now zero. The structure never rotates, never rebalances, never cascades unpredictably.

Complexity at a Glance

Figure 3: Operation Complexity — Sorted Tree vs Bit-Index Tree

Operation	Red-Black / B-Tree	Perpl Bit-Index Tree	Note
Insert (post order)	O(log N)	O(1)	N = active price levels
Delete (cancel order)	O(log N)	O(1)	Delete fixup can cascade to root
Find best bid / ask	O(log N)	O(1)	Bit-scan on 256-bit word
Find next price level	O(log N)	O(1)	At most 3 slot reads per jump
Match (fill orders)	O(M)	O(M)	M = orders filled. Identical — both must touch each filled order
Worst-case SSTOREs per insert	~log₂(N) × 2	3	At N=10,000: tree ≈ 26 writes, Perpl ≤ 3

Matching is O(M) for both approaches — you must touch each filled order to settle it. The difference is entirely in insert and cancel, which happen with every post and every requote.

▶ Simulate it in the interactive

The Gas Reality

Abstract complexity becomes concrete gas cost on the EVM. Every storage write (SSTORE) costs gas — 20,000 gas for a cold slot (first write in a transaction), and 2,900 gas for a warm slot (already accessed). A sorted tree with 10,000 price levels requires at minimum 13 traversal reads and several rebalancing writes on each insert — and this cost grows as more orders accumulate.

Perpl's post-and-cancel cycle runs at 100k gas total, including full solvency checks, order storage, and all other computation. Uniswap V2 — the baseline for "a lightweight DeFi swap" — costs 200k gas. Perpl's CLOB insert+cancel is cheaper than an AMM swap.

Figure 4: Gas Cost vs Order Book Depth — Perpl Stays Flat, Sorted Trees Scale

Gas estimates for the sorted tree assume warm slots (SSTOREs at 2,900 gas) after initial traversal. Real-world costs are higher when tree nodes are cold, which is typical for orders at new price levels. Perpl's 100k gas figure is the actual measured cost from deployed contracts on Monad, including full solvency checks.

The gap compounds with frequency. A market maker running 200 requotes per hour faces 200 post+cancel cycles. On Perpl that's 20M gas per hour — a predictable, constant budget. On a sorted tree CLOB at N=10,000, the same 200 cycles consume 60M+ gas per hour, and the cost continues climbing as the book deepens. At scale, this difference determines whether tight-spread market making is economically viable.

Why This Defines Market Maker Quality

Market makers provide the liquidity that makes a CLOB useful. Their value is the spread: the gap between the best bid and best ask. Narrow spreads mean tighter prices for takers. But spreads are not set arbitrarily — they are bounded below by the cost of maintaining them.

A market maker's core loop is: post a quote → price moves → cancel → post new quote. The gas cost of that loop sets the minimum economically viable spread. Every requote must at minimum cover its gas cost through expected fee income. Higher gas per requote = wider minimum spread = worse prices for everyone.

Sorted tree CLOB

O(log N) per post + cancel

Every requote traverses the tree to find the insertion point, then rebalances. The cost scales with how many price levels are active. A deep book is a more expensive book to quote on.

Post cost (N=10,000)~150k gas

Cancel cost (N=10,000)~150k gas

Requote cycle~300k gas

Cost grows with?Book depth

Perpl bit-index tree

O(1) per post + cancel

Every requote flips bits at fixed tree levels. Cost is identical whether there are 10 price levels or 10 million. A liquid, deep book costs no more to quote on than an empty one.

Post cost (any N)~50k gas

Cancel cost (any N)~50k gas

Requote cycle100k gas

Cost grows with?Nothing

The Change order compounds this further. Because Perpl's order storage slots are not tied to any specific price level, a market maker can move an order to a new price in a single transaction rather than canceling and reposting. The Change operation shifts the order's slot from one price partition to another — no deallocation, no reallocation. This eliminates half the storage cost of a requote entirely.

Shared storage across price levels: The partition map list that holds orders at each price level uses the same pool of order slots regardless of which price they're at. Order o15 at price m-2 can be moved to price m-3 by updating its partition pointers — no new slot needed. This is what makes Change orders possible and is a direct consequence of the bit-index tree's clean separation between price indexing and order storage.

The Full Order Book Architecture

The bit-index tree handles price discovery. Orders at each price level are stored in a partition map list — a doubly-linked FIFO queue per price level, built on Solidity mappings. Orders at the same price execute in the order they were posted (price-time priority). The combined structure is two bit-index trees and one partition map list:

Figure 5: Order Book Architecture — Two Bit-Index Trees + Partition Map List

The price bit-index tree (left) indexes which price levels have active orders — covering ~16M price levels with 3 storage slots max. Each occupied price maps to a FIFO queue of orders (right). The order ID bit-index tree (lower left) tracks available order slots and serves as the ID counter. Orders move between price queues (via Change) without deallocating their storage slot.

The result is a CLOB that supports over 16 million price levels, up to 65,535 simultaneous open orders per contract, and price-time priority matching — all fully on-chain, fully transparent, and at gas costs that make market making economically viable for the first time on an EVM chain.

▶ Explore the interactive How the Change order works ← All Explainers