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.
Wrong Target: Parcel Object Trimming
We analyzed every field in the stored geometry: vertex coordinates, part counts, creation epoch, owner reference, the cell list. Removing every redundant field saved an estimated 88 bytes per parcel — roughly 669K MIST. That's 19% of object overhead. Object overhead is 22% of total insertion cost. 19% × 22% ≈ 4% total savings.
We'd optimized the wrong term.
The $2.7\text{M} \times K$ term didn't scale with the parcel's data complexity. It scaled with geographic size. Trimming the geometry object left K untouched.
The Obvious Fix: Bigger Cells
Double the cell size. Halve the cell count per dimension. Quarter K.
The 36-cell envelope drops to 4 cells. Cost: roughly 97M → 11M MIST. A 9× improvement on paper.
Two failure modes killed it.
First: dense urban areas. A coarse cell covering a city block holds hundreds of parcels. Every registration loads the full vector of IDs in that cell. At high density, deserialization cost exceeds the storage savings. The problem shifts from allocation count to vector size.
Second: massive parcels. A national park or continental claim can still span 36+ coarse cells. At 42 cells, the protocol aborts with ETooManyCells. We moved the threshold. We didn't eliminate it.
Cell size is a dial, not a fix. Dense areas want fine cells; sparse areas want coarse ones. No single setting serves both.
Dead Ends: Space-Filling Curves
We evaluated every standard spatial indexing scheme.
H3: Hexagonal cells, no gaps, optimal packing. Cell membership requires icosahedral gnomonic projection — trigonometry. Move has no native floats. H3 is impossible on-chain.
Google S2: Hilbert curves, stronger locality than Z-order. But S2 first projects coordinates onto a sphere — float math, blocked on-chain. The Hilbert curve itself is integer-implementable, but S2's real innovation is its multi-resolution cell hierarchy, not the curve geometry.
Morton codes at fixed resolution: Pure integer bit manipulation, fully implementable in Move. But at any fixed depth, Morton codes partition space into exactly as many cells as a uniform grid. Locality improves. Cell count stays identical. K doesn't change.
The curve wasn't the problem. The hierarchy was.
Almost There: Two-Level Index
Group B×B fine cells into one coarse bucket (B=3). A parcel covering 36 fine cells lands in at most 4 coarse buckets — a 9× reduction in dynamic field allocations. The $2.7\text{M} \times K$ term drops from 97.2M to ~10.8M MIST. An 88% reduction in the dominant cost component.
Two problems remained.
First: dense buckets. In a dense city, many small parcels land in the same coarse bucket. Loading that bucket forces deserializing every ID in the vector. Bigger buckets meant bigger vectors — the allocation problem repackaged as a deserialization problem.
Second: the bound isn't tight. A parcel slightly larger than the 36-cell max still hits ETooManyCells. The two-level index moved the wall. It didn't remove it.
We'd analyzed the right problem — dynamic field allocation count — but bounded it from the wrong direction. The two-level index proved reducing K worked. A fixed grouping factor B can't serve all parcel sizes and densities.
The Insight: Natural Depth
Every approach so far shared one assumption: cell count scales with geographic size. Bigger cells, coarse buckets — K always grew with bounding box area.
The quadtree breaks that assumption: place a parcel at the depth where its bounding box fits in a single cell, not in every cell it touches at a fixed depth.
A city block has a small bounding box — it fits in a fine cell deep in the quadtree. A continental territory has a large bounding box — it fits in a coarse cell near the root. Both use one cell. One dynamic field allocation. K = 1.
The testnet numbers from the grid era:
- 4-vertex square, K=4: 13.2M MIST
- 36-cell envelope, K=36: 78.8M MIST
Under the quadtree, both cost ~7.2M MIST (K=1). The dominant term — $2.7\text{M} \times K$ — drops by 97% for large parcels, 75% for small ones. Total net savings: ~45% for a parcel that was already small (K=4→1), ~91% for a large parcel (K=36→1).
One honest note: for parcels that only covered 1–4 grid cells to begin with, the savings are modest. The quadtree makes storage cost-invariant — the cost no longer grows with geographic size.
We covered the natural_depth algorithm and depth_prefix mechanics in the Dynamic Fields article. The Morton Codes article covers the broadphase query that makes K=1 storage work for overlap detection.
The Measurement, Revisited
Storage is still 94–96% of transaction cost. What changed is the coefficient.
The K in $2.7\text{M} \times K$ went from a variable — "up to 36, scaling with the parcel's geographic footprint" — to a constant: 1.
We didn't make storage cheaper. We made the storage we need constant.