S2 & H3

From One Machine to the Whole Planet

Look back at the three structures we've built. Geohash was a string — dead simple, and it shards across a thousand machines by prefix without a second thought. But it had two real flaws: its Z-order curve jumps (two points a stone's throw apart, on opposite sides of a seam, get codes with nothing in common), and its flat latitude/longitude grid stretches badly toward the poles, so a cell near the Arctic covers a wildly different area than one at the equator. Quadtrees and R-trees fixed the geometry — they adapt to the data — but they're trees of pointers that live on one machine; sharding them across a cluster is real work.

Planet-scale companies want both halves at once: a geohash's effortless distribution and geometry that doesn't fall apart. So Google and Uber each went back to the geohash's core idea — turn a location into a single number a B-tree can index — and rebuilt it properly. The recipe is the same for both: wrap the round Earth around a 3-D solid, lay a hierarchy of cells on its faces, and give every cell a 64-bit integer ID. A 64-bit ID is just a number — it drops into any database column, any key-value store, and shards as easily as a geohash — but now the cells sit on a sphere-aware grid with a locality-preserving order. Two flaws, fixed.

Where they part ways is the shape of the bet. Google's S2 tiles with squares and threads them with a smarter curve. Uber's H3 tiles with hexagons. Those two choices — a better curve versus a better shape — fall out of two different jobs, and between them they finish the spatial toolkit.

The two industrial global grid systems, S2 and H3, side by side as two different bets on the same idea. In the middle, the shared idea: wrap the round Earth in a hierarchy of cells and give every cell a 64-bit integer ID, so a location becomes a number any database can index and shard — distributable, like a geohash, but with far better geometry. On the left, S2 by Google: the sphere is projected onto the six faces of a cube, each face is a grid of squares, and a smooth Hilbert curve threads through the squares so that consecutive IDs are always neighbors. Its bet is squares plus a Hilbert curve, and its strength is indexing and covering regions. On the right, H3 by Uber: the sphere is wrapped as an icosahedron tiled with hexagons, where every neighbor of a cell sits at the same distance. Its bet is hexagons, and its strength is movement and flow analytics. The bottom line: same 64-bit distributable idea, two shapes, two jobs — and together they finish the spatial toolkit.

S2: A Hilbert Curve on a Cube

Google's S2 starts by fixing the geohash's projection problem. Instead of a flat lat/lng grid, it projects the sphere onto the six faces of a cube and grids each face. Unfolding a cube keeps cells far more uniform in size than a flat map that smears toward the poles — the first flaw, gone.

Each cube face is then a quadtree: divide it into four squares, each of those into four, and so on for 30 levels. Because it's a clean four-way split, the cells nest exactly — a level-18 cell sits perfectly inside its level-12 parent, which sits inside its face. The levels are your precision dial: a whole face at level 0, roughly 3 km at level 12, about 38 m at level 18, down to roughly 1 cm at level 30. Each cell gets a 64-bit ID: a 3-bit face number, then a pair of bits per level choosing which of the four children, then a marker bit — so the length of the meaningful prefix is the level, exactly like a geohash but as an integer.

Now the clever part, and the one that pays off Geohash's cliffhanger. To order the cells, S2 doesn't use the Z-order curve — it uses a Hilbert curve. Both are space-filling curves that thread a single line through the grid, but the Hilbert curve has a property the Z-order lacks: it never jumps. Every step from one ID to the next lands on a touching cell. Measure it and the difference is stark — and it grows with scale. Between consecutive codes the Hilbert curve moves at most 1 cell at any zoom level, while the Z-order curve's longest leap balloons with the grid: 7 cells on an 8×8, 63 on a 64×64, and unboundedly far on S2's real 2³⁰-per-side grid — nearby points flung to the far side of the map. That's the geohash seam, gone.

Why does that matter in practice? Because a region — "everything in this neighborhood" — becomes a set of contiguous ID ranges (an S2 covering), and each range is one fast B-tree scan. The smoother the curve, the fewer ranges you need: covering a small box took about 3.9 ranges with the Hilbert curve versus 6.3 with Z-order — fewer scans for the same area. And because the exact nesting makes every descendant of a cell fall in a contiguous run of IDs, the question "is this point inside that region?" collapses to an integer range check — no geometry math for the coarse pass, just low ≤ id ≤ high. That efficiency is why S2 is the choice when the job is indexing and geometry: Google Maps runs on it, MongoDB's 2dsphere and CockroachDB use it, and Foursquare rebuilt its entire venue database on S2 in 2018, replacing geohashing for large gains in query speed and reliability.

How Google's S2 turns the globe into 64-bit cell IDs, and why its curve beats the geohash. First, the sphere is projected onto the six faces of a cube, which keeps cells far more uniform in size than the geohash's flat map that stretches badly toward the poles. Each face is recursively divided into four squares, thirty levels deep, so cells nest exactly, from a whole cube face down to about one centimeter at level 30, with level 12 near three kilometers and level 18 near thirty-eight meters. A Hilbert curve then threads through the squares to number them, and the picture contrasts it with the geohash's Z-order curve: the Hilbert curve moves only to a touching neighbor at every step, while the Z-order curve periodically leaps clear across the map. The measured gap grows with the grid: the Hilbert curve's longest jump is always one cell at any zoom, but the Z-order curve's longest jump is seven cells on an eight-by-eight grid and sixty-three on a sixty-four-by-sixty-four grid. Because of that smoothness, covering a region takes fewer contiguous ID ranges, measured at about 3.9 ranges for Hilbert against 6.3 for Z-order. The bottom line: a cube for even cells, a Hilbert curve for true locality — a better geohash, in 64 bits.

H3: Hexagons All the Way Down

Uber's H3 makes a different bet, and it's all about one deceptively simple question: when you step from a cell to a neighbor, how far did you go?

On a square grid, there's no single answer. Your four edge-neighbors are one step away, but your four corner-neighbors are about 1.41 steps away — 41% farther. Two different distances. A triangle grid is worse: three. But a hexagon has exactly six neighbors, and all six are the same distance away. One distance, always. That sounds like a small thing and it's enormous: it means "grow the search outward by one ring," "measure how demand flows from this cell to the next," and "smooth a heatmap across cells" are all uniform and deterministic — no awkward corners that are secretly farther. For a company whose whole business is modeling movement — riders, drivers, supply, demand, surge — that uniformity is exactly what you want. So H3 tiles the Earth with hexagons, and its cell IDs (64-bit again) are the sharding key Uber's surge-pricing system uses to bucket supply and demand, city by city.

Hexagons come with a bill, though, and H3 pays it honestly. You cannot tile a sphere with hexagons alone — it's a geometric impossibility. H3 wraps the Earth as an icosahedron (a 20-sided solid) and is forced to place exactly 12 pentagons at its corners, surrounded by hexagons — 122 cells at the coarsest resolution (12 pentagons + 110 hexagons), tucked over the oceans where they cause the least trouble. And unlike S2's exact squares, H3's levels only nest approximately: each parent hexagon splits into 7 children that rotate about 19° and don't line up perfectly with the parent's edges. So a child isn't cleanly "inside" one parent the way an S2 cell is. Sixteen resolutions span the range — a base cell over 1,000 km across at resolution 0, down to about 0.5 m at resolution 15.

The trade, in a sentence: hexagons buy uniform neighbors — perfect for flow — at the price of 12 pentagons and approximate nesting.

Why Uber's H3 is built from hexagons, and what that buys and costs. The centerpiece compares three tilings by how many different distances separate a cell from its neighbors. A square cell has two: its four edge neighbors sit at distance one, but its four corner neighbors sit at about 1.41, forty-one percent farther. A triangle has three different distances. A hexagon has just one — all six of its neighbors are exactly equidistant — which makes growing a search ring outward, or modeling flow and movement between cells, clean and uniform. That is why Uber chose hexagons for measuring supply and demand. The cost is drawn alongside: you cannot tile a sphere with hexagons alone, so H3 wraps the Earth as an icosahedron and is forced to include exactly twelve pentagon cells at its vertices, and its levels only nest approximately — each parent splits into seven children that rotate slightly and do not fit perfectly, unlike S2's exact squares. The bottom line: hexagons give uniform neighbors for flow, paid for with twelve pentagons and approximate nesting.

Same Idea, Two Bets

Line S2 and H3 up and the family resemblance is obvious — and so is the split.

What they share: both wrap the Earth on a 3-D solid, both build a hierarchy of cells, both hand every cell a 64-bit integer ID that indexes and shards as easily as a geohash, and both fix geohash's two flaws (the jumpy curve and the pole distortion). If you need a global spatial index that distributes across a cluster, either one beats a geohash and neither one is a tree stuck on a single machine.

Where they differ — the bet:

S2 = squares + a Hilbert curve. Cells nest exactly, the curve preserves locality, and a region becomes a tidy set of ID ranges. That makes it superb for indexing, containment, and covering regions — "is this point inside that polygon," "index every venue," "range-scan this neighborhood." It's the database-and-geometry tool.
H3 = hexagons. Neighbors are uniform, so it shines at movement, flow, and analytics — bucketing rides into cells, measuring supply and demand, drawing gradients, expanding search rings evenly. It's the marketplace-analytics tool.

It's not even either/or at the company level: Uber uses both — H3 to bucket supply and demand for surge, and S2 for its RideCheck safety system that geofences pickups and drop-offs. Same firm, different jobs, different grid. The rule of thumb is simple: reach for S2 when you're indexing and asking about geometry; reach for H3 when you're analyzing movement and flow.

Both bets are worth feeling directly. Toggle the curve — Z-order versus Hilbert — and watch which one keeps neighbors close; toggle the tiling — square versus hexagon — and watch the hexagon's neighbors line up at a single distance while the square's corners hang back.

Two toggles, two geometric bets. Flip between the geohash's Z-order curve and S2's Hilbert curve and watch the line thread the grid: the Hilbert curve only ever steps to a touching cell, while the Z-order line leaps across the map — pick two neighbors and see how far apart their codes land. Then flip between a square grid and a hexagon grid and click a cell: the square lights up four close neighbors and four that are 41% farther, while the hexagon lights up six that are all exactly the same distance. It's the whole lesson in your hands — why S2 changed the curve, and why H3 changed the shape.

The Spatial Toolkit Is Complete

Step back: with S2 and H3, the spatial section is finished, and the four structures line up as a single clean answer to the question we posed in Geospatial Search: The Problem — how do you find what's near, at scale?

Geohash — a location becomes a string; near becomes shares a prefix. Dead simple, distributes anywhere, but a fixed grid with a jumpy curve. Reach for it when simplicity and distribution win.
Quadtree — an adaptive grid that splits space where points cluster. Great for points and range queries in memory.
R-tree — an adaptive tree of bounding boxes that groups the data. The one for shapes with extent, and what spatial databases ship (PostGIS's GiST).
S2 / H3 — global, hierarchical grids with 64-bit IDs that keep the geohash's distribution and add real geometry. S2 (squares + Hilbert) for indexing and covering; H3 (hexagons) for movement and flow.

Every one of them is the same core move from the very first lesson of this section — turn "near" into a cheap lookup by imposing an order or a partition on space — just with different bargains: a string, an adaptive tree, or a global grid. You now have the whole toolkit and, more importantly, the judgment to pick.

And that closes the first half of §8. Everything so far has kept its answers exact — a spatial index finds precisely the points in your region. The rest of this section makes a startling different trade. What if you'd accept an answer that's occasionally wrong — "probably in the set," "about a million distinct users," "roughly this frequent" — in exchange for a structure hundreds of times smaller that runs at memory speed? That's the world of probabilistic sketches, and it opens with the most beloved of them all: the Bloom filter.