Indexing the World with Morton Codes: How Our Quadtree Finds Overlaps in O(1)
· 6 min read
A new parcel arrives on-chain. Before the protocol writes it to the Index, it must answer one question: does this shape overlap anything already registered? A naive answer is to compare the newcomer against every existing parcel — but that's O(N), and N grows with every registration. On a blockchain, O(N) means gas that grows with the map's popularity. The more successful the protocol, the more expensive it becomes to use.