The Secret Number Hiding in Your Map Tiles

A Database That Only Understands a Line

Once, in the fast-query story, you met the tree of nested boxes that lets a database find shapes on a map in a flash. That is one answer to a hard problem. Here is a completely different answer to the same problem, one that is stranger, older, and quietly hiding inside the names of the very map tiles you push to your image network. The hard problem is this. A database is fundamentally good at one thing, sorting items along a single line, first to last, like words in a dictionary. But a map is two-dimensional. A place has both an east-west position and a north-south one. How do you put a flat, two-dimensional world into a filing system that only really understands a one-dimensional line. You cannot sort by east and by north at the same time. You have to choose. And choosing badly ruins everything.

Why Sorting by One Axis Fails

Say you just sort every location by its east-west position and ignore north entirely. Now two points that are right next to each other on the map, one just slightly north of the other, are fine, they have nearly the same east-west value, so they sit together in your sorted line. But two points that are far apart north-to-south yet happen to share an east-west position land right next to each other too, even though they might be hundreds of kilometers apart. Your sorted line thinks they are neighbors when they are strangers. Search the map for everything in a small area and your nice one-dimensional index keeps dragging in faraway points that merely share one coordinate. The line has lost the plot of the map.

What you actually want is a single number for each location such that places near each other on the map get numbers near each other on the line. A number that respects two dimensions of nearness at once. That sounds impossible, because a line is one-dimensional and a map is two, the same flattening problem in a new coat. But there is a beautiful trick that gets remarkably close, and it works by weaving the two coordinates together rather than picking one.

Weaving the Coordinates Together

Take the east-west position and the north-south position and write each as a string of binary digits, ones and zeros. Now, instead of putting one number after the other, you interleave them. First digit of east, first digit of north, second digit of east, second digit of north, alternating all the way down, braided into a single longer number. That braided number is the secret. Because the most significant digits, the ones that decide the broad region, come first and are interleaved, two places in the same broad quadrant of the map share the same leading digits and therefore land close together on the line. Zoom in and the next digits sort them within that quadrant, and the next within that, recursively, all the way down. Nearness on the map survives the journey onto the line, most of the time, because you braided the two dimensions instead of abandoning one.

If you trace the path this numbering takes across the map, in the order of the braided numbers, it draws a shape like the letter Z repeated at every scale, a Z made of Z's made of Z's. That is why one version is called the Z-order curve. It is a single winding thread that visits every cell of a two-dimensional grid while mostly keeping near things near. There are fancier cousins, one named after a mathematician, that wind more cleverly and never make a long jump, preserving nearness even better, but the Z-braid is the simplest and the most common because the interleaving is so cheap to compute.

It Is Already in Your Filenames

Here is where it stops being abstract. When you render map tiles into a pyramid, zoom level, then column, then row, and stack them on your image network, the addressing scheme for those tiles is this exact idea in disguise. Each deeper zoom level adds more braided digits, splitting every tile into four children, the world quartered and quartered and quartered again. The path through the tiles, the way a single coordinate can name a square at any zoom, is the same recursive braiding of two dimensions into one ordered sequence. You have been generating and naming things organized by this curve without needing to know it had a name. The reason a tile server can take one number and know exactly which square of the planet you mean, at exactly which zoom, is that the number is a braided address walking the Z-curve down into the map.

The Keeper

So you now hold two completely different answers to the same question, how to find things on a flat map using machinery that only sorts along a line. The first was the tree of nested boxes, opening only the boxes that overlap your search. This second one never builds a tree at all. It assigns every place a single braided number, made by interleaving the digits of its two coordinates, so that nearness on the map turns into nearness on the line, and then it just sorts, the way a database loves to. The path that numbering traces is a Z inside a Z inside a Z, and that same recursive quartering is silently naming every map tile you have ever rendered. Two dimensions, folded into one ordered thread, cheaply enough that it hides in plain sight inside your filenames.