From Grid to Quadtree: How We Cut Storage Costs by 97%
Testnet, March 2026. We measured.
Storage was 94–96% of every transaction's cost. Grid cell dynamic fields consumed 68% of per-parcel insertion cost. As we derived in our Dynamic Fields article, the dominant cost term in the insertion formula is $2.7\text{M} \times K$, where K is the number of grid cells a parcel covers:
$$ \text{Cost} = 1\text{M} + 2.7\text{M} \times K + 3\text{M} + 0.5\text{M} \times m \quad (\text{MIST}) $$
A parcel spanning 36 cells paid 97.2M MIST in cell entries alone. That's 97% of the $2.7\text{M} \times K$ term — the dominant cost component, not 97% of total gas. The other terms (base overhead, geometry storage) were fixed. K was the variable. K scaled with geographic size.
This article is about the five approaches we analyzed to cut K. Four of them failed. The fifth — a hierarchical quadtree with depth-prefixed Morton keys — reduced K from up to 36 to exactly 1. This is the story of how we found it.