[00:01] between age 20 and 30 in milliseconds. But when you ask it to find every driver within 2 km of a rider for an Uber-like app, it falls over. Now, on the surface, these two queries look really similar, but they're actually very different. The
[00:14] age query is fast because a B-tree keeps sorted keys packed together on disk. 20 sits next to 21, sits next to 22. They're on the same page. So, everyone between 20 and 30 is one seek and a short read. Location doesn't work that
[00:28] way. You have two numbers, latitude and longitude. And what you care about is the straight-line distance between two points. Two B-trees don't save you here, you a horizontal strip of the earth. One on long gives you a vertical strip of
[00:42] the earth, and their intersection is still millions of rows that you have to check the distance between them and your point of interest by hand. Now, the real problem is that 1D sort order doesn't preserve 2D closeness. Take two cabs
[00:55] Manhattan. They're neighbors. But if your 1D index sorts on longitude alone, every other cab in the city at a longitude between them, from Bronx down to Staten Island, gets crammed into the index between these two neighbors.
[01:10] a millions of rows apart in your database. Any naive flattening of 2D into 1D rips apart the relationship we actually care about. Now, every modern production system, Postgres, Elasticsearch, Redis, Google Maps, Uber,
[01:24] approaches to solving this proximity search problem. Either build a custom tree like a B-tree, but specially tuned for location, or turn latitude and longitude into a single key that a plain B-tree can already sort. Why is B-tree
[01:38] the prize? Because it's the one data structure databases have spent 50 years tuning. It stays balanced as data changes, it packs sorted keys into disk pages, so range query is one seek and a sweep, and every database you'd ever
[01:51] squeeze your spatial problem into a B-tree shape, you inherit all of that complicated than it is. Both approaches end up at the same prize, a balanced tree of pages on disk that you can range scan. Let's walk through how we get
[02:06] there. The first serious attempt came in 1974 from Finkel and Bentley. They called it the quadtree, and it's an incredibly useful foundation to understanding proximity search. Take your whole map, split it into four
[02:18] quadrants. If any quadrant has too many points in it, split that one into four again. They can keep doing this recursively until every leaf has a manageable number of points. To find points near a location, you just descend
[02:30] node, you compare the query point's latitude and longitude against the cell's midpoint, north or south, east or west. That picks one of the four then repeat this until you end on a leaf. Then you check the neighboring
[02:45] happened to sit just on the boundary from your query point. What's really nice about this is that it adapts to density. Manhattan ends up as a deep tree because it's full of pins. A lake upstate stays a single coarse cell
[02:57] because nothing's there. We don't waste so much of space indexing the ocean. But this has a really bad downside on latency at scale. Because these splits always happen at the geometric midpoint of a cell, not where the data actually
[03:09] sits, a dense cluster like Manhattan just keeps getting sliced in half over and over and over again until those points finally separate. You burn 10s or more levels of depth in your tree before you actually reach a leaf node. Whereas
[03:22] just two. That means that your query latency depends on where in the world you're looking. You can't reason about worst-case performance very well, and the hot regions, the ones that you actually care about, like Manhattan, are
[03:35] problem. A quadtree is a pointer structure, which means every node in the tree lives at some arbitrary address in memory with pointers linking to its four children. That works beautifully when the whole tree fits in RAM because
[03:48] following pointers is a really cheap memory lookup. But databases can't make in memory. They read data from disk in fixed page sizes, and every pointer you at a page that you haven't loaded yet, which forces random disk reads every
[04:03] single time. A few hops in and you're spending most of your query time waiting work. Now, you still see quadtrees today. Google Maps uses them for map tile systems, game engines use them for collision detection, but for a scale
[04:16] database where the index has to live on disk and stay efficient when it doesn't fit in memory, we need something smart. Well, 1 year later in 1975, the same guy, he came back with a binary cousin he called the KD-tree. The idea is that
[04:29] instead of splitting all dimensions at once into four quadrants, alternate. At level zero, split on X. At level one, split on Y. And back to X, back to Y. You get the picture. One dimension per level, cycling through. This gives you a
[04:43] binary tree for multi-dimensional data that's balanced importantly if you split at the median. And it was the workhorse for nearest neighbor type searches for decades. But KD-trees, they have the same disk problem as quadtrees. There's
[04:56] mapping to pages. And so, great in memory, but painful off of it. The modern fix is what's called a BK-tree, short for block KD-tree. Instead of one
[05:08] point per node, points get packed into blocks sized to a disk page. And the whole tree is built once from a batch of data. Elasticsearch actually uses this for their geo fields today. So, when you run a geo query in Elasticsearch, you're
[05:21] hitting a 50-year-old algorithm with a disk-friendly wrapper, which is pretty cool. Next, in 1984, Antonin Guttman at Berkeley, he came up with the first spatial index designed specifically for a database. Guttman had two problems
[05:35] that quadtrees and KD-trees hadn't handled. The first was shapes. Every index before this one assumed your data was a point, like a driver, or a pin, or a user location. But real geographic data has lines and polygons. A highway
[05:48] is a line. A country is a polygon. A Starbucks might be a point, but the Starbucks delivery zone is a polygon. And so you can't meaningfully drop a country into a quadtree cell. The second was the disk issue. Guttman wanted the
[06:03] spatial analog of a B-tree. Balanced, fast to read off of disk, fast to update in-memory structures weren't going to cut it anymore. His answer was to use minimum bounding rectangles. Every
[06:16] single object gets wrapped in the smallest rectangle that contains it, with sides parallel to the latitude and longitude axes on the map. A point is a rectangle with zero width and height. A highway gets a long thin rectangle
[06:28] around it, and a country of course gets a big rectangle that bounds it. Then nearby rectangles can get grouped into larger enclosing rectangles. Those group into bigger ones, all the way up to the root. The clever part of this is that
[06:42] this tree stays balanced like a B-tree. Every leaf lives at the same depth. So every query touches the same predictable number of pages from the database. Every node fits into a disk page. Inserts and deletions rebalance by splitting and
[06:56] merging pages, just like a regular B-tree does. There's one trade-off to call out here. Unlike quadtree cells, R-tree rectangles can overlap. So if your query point lands inside two bounding rectangles at once, you have to
[07:08] descend both branches and check both subtrees. So a bad insertion strategy produces lots of overlap, which means a lot of branches to follow, which tanks performance. R-trees are the workhorse of production spatial indexes. PostGIS,
[07:21] SQLite, Oracle Spatial, they all use an R-tree variant under the hood. Six years after Guttman's paper, a team in Germany published the R*-tree, which uses a smarter insertion algorithm to minimize those overlaps we were just talking
[07:34] what almost all of the modern R-tree implementations are built on today. interviews, come join the hundreds of thousands of candidates who use hello interview.com every single month. We've got tons of free content across all
[07:47] interview types, like system design, coding, behavioral, and even AI coding. and an interactive guided practice that candidates love. Now, back to the video. second to zoom back out. Everything we've looked at so far, quad trees, KD
[08:02] trees, R trees, they're all custom tree structures. They work, but they're complicated. Your database needs special indexing codes, special query codes, skipped all of that? What if we could take latitude and longitude and turn
[08:15] integer, where numerically close integers meant geographically close locations? If we had an integer, then we could use a regular B-tree, that boring thing our database already has, and where range scans just work out of the
[08:29] box. This is that second camp, and it's the idea that took over most of the industry. In 2008, a developer named Gustavo Niemeyer took decades-old math actually compute in a few lines of code. He called it a geohash. The idea is that
[08:44] simple. Divide the world into a grid of 32 cells, and label each one with a of them, and that's your first character. Now, take that cell and divide it into 32 smaller cells. Your
[08:57] That's your second character. Keep recursing as deep as you want. Each additional character zooms in further to the map. A five-character geohash, for example, is about 5 km across. Nine characters gets you all the way down to
[09:11] 5 m. The final string, something like dr5ru, is your 2D location encoded as a 1D key. The payoff is that strings sharing a here's the part that's really worth pausing on. Each character picks one of
[09:28] 32 options, which is exactly five bits. So, a geohash isn't really a string, So, a geohash isn't really a string, it's a stack of bits. The string dr5ru is 25 of those bits grouped into five letters for human readability. Read the
[09:41] same 25 bits straight through as a number and you've got an integer. Same bits, same sort order. That's why Redis can store geohash of 52-bit integers and Postgres can store it as text and both indexes behave exactly the same way. The
[09:54] huge payoff here is that keys sharing a prefix are usually near each other, which means you can query proximity on any sorted index in a database. Where geohash like dr5 ru wildcard, that's just a regular B-tree prefix scan. It's
[10:09] totally efficient. This is how Redis geo commands work in production. When you call a geo add, Redis computes a 52-bit geohash integer and stores it in a sorted set, which is Redis's name for a B-tree like structure that keeps entries
[10:21] ordered by numerical score. A nearby query is just a ZRANGEBYSCORE against that sorted set. Basically, a range scan over the geohash integers. an existing data structure that you'll find in production. There is one catch
[10:35] worth noting though. Geohashes have edge cases at cell boundaries. Two points a meter apart can actually end up landing in completely different cells and prefixes if they straddle a boundary.
[10:48] Picture a rider standing right on the edge of a cell, dr5ru. The closest edge of a cell, dr5ru. The closest driver might be 10 m away in cell dr5rg. A naive prefix scan over dr5ru would miss them entirely. The standard fix is
[11:02] what's called the 3 by 3 trick. You compute the cell your query point then walk to the eight neighboring cells and query all nine as a unit. That way you distance of you, no matter how close to a boundary you are. You can then post
[11:16] filter the results by exact distance to drop the corners that are technically in your query window but actually too far away. And almost every encoded key index in production does some version of this trick at query time. All right. Now,
[11:28] out a city, but it starts to hurt when you look at a globe. The problem is that GeoHash treats latitude and longitude as if they lived on a flat rectangle, and the earth isn't flat. A degree of longitude is about 111 km at the
[11:43] equator, and nearly zero at the poles. So, a cell that's one GeoHash character wide is a fat square at the equator, and a tiny sliver near each of the poles. everywhere on earth, and you want a one-D ordering that preserves locality
[11:58] on a sphere object as a rectangle. So, around 2011, Google built S2 to fix this. The trick is to wrap the sphere in a cube, and project the earth onto its
[12:10] six flat surfaces. On each face, you can subdivide cleanly into cells that stay roughly the same size anywhere on the globe. Every location ends up with a 64-bit integer called an S2 cell ID. And like the GeoHash, the IDs are higher
[12:26] arctical. Truncate the ID, and you get a coarser parent cell. S2 is what powers MongoDB's 2D sphere index. When your geoquery correctly handles a polygon that crosses the anti-meridian, that's S2 under the hood. Flat earth indexes
[12:40] treat such a polygon as stretching all the way around the globe, but S2 knows better. Okay, last one now. In 2008, Uber open-sourced H3, which they use for dispatch and surge pricing. The twist with H3 is that it uses hexagons instead
[12:54] of squares. Why? Well, a square has two kinds of neighbors. Four sharing an edge, but four sharing only a corner. And the corner ones are further away. That asymmetry makes heat maps and everyone within N cells of me queries
[13:08] messy. So, a hexagon has exactly six neighbors, all at the exact same clean math for the kind of analytics that Uber runs every single day. H3 tiles the entire globe in hexagons, and each hexagon roughly subdivides into
[13:22] seven smaller hexagons. So, you can zoom in as far as you need, just like with S2 and Geo Hashes. You get 16 resolutions in total from continent-size cells down to about a square meter. Every cell gets a 64-bit integer ID, and again, like Geo
[13:37] Hash and S2, the IDs are hierarchical. Zero at the end of the ID and get a parent cell. Now, you might be wondering, how do you sort a hexagon in is that you don't sort the hexagons themselves. You sort their IDs. So, H3
[13:50] deterministic order, kind of like a space-filling curve. And it assigns each cell along that walk an integer that gets larger as you move along the path. property Geo Hash and S2 give you. Numerically close IDs are usually
[14:05] geographically close to each other. So, that a B-tree can scan over those IDs, giving you a clump of nearby hexagons. Now, the way that it works in production location, and the system converts that latitude and longitude into an H3 cell,
[14:19] say a 200-m cell. When a rider opens up their app, you get their latitude and longitude, find which cell they're in, expand to the six neighbors around them, look for any drivers. If you need a wider net, expand to the cells around
[14:32] those, and continue this until you find the closest driver. Okay, let's start to summarize what we learned. We threw a lot at you there. Every production types. The tradeoffs between them are pretty clear once you know what to look
[14:45] for. The first type is those custom spatial trees. The database ships a purpose-built tree tuned to behave like a B-tree on disk, where it's balanced, page size known, predictable depths, but it doesn't explicitly use a B-tree.
[14:58] Postgres uses an R-tree variant. Elastic Search uses that BKD tree. These really shine when you care about shapes and accuracy. An R-tree doesn't just index points. It indexes lines, polygons, and complex geometries, which means that you
[15:12] can ask things like, does this highway intersect this country? Or, which delivery zone contains this address? And you get an exact answer. The downside is that your database has to ship a real spatial extension. So, you can't do this
[15:24] in a generic setup and writes are expensive. R-tree inserts run a minimize that overlap we talked about earlier, and BKD trees are basically immutable segments. That makes them a bad fit for data that changes a lot like
[15:40] with Uber where you have many moving drivers. The second type is the encoded key. You basically turn latitude and longitude into a single sortable integer run-of-the-mill B-tree and then you're done. Redis uses GeoHash, MongoDB 2
[15:54] done. Redis uses GeoHash, MongoDB 2 sphere uses S2, and Uber uses H3. This approach wins out on simplicity and speed. It works in any database with a B-tree or a sorted structure. There's no spatial extension required. Writes are
[16:06] dirt cheap because a driver moving around is just a single integer update already been tuned for. And that's exactly why Uber can handle millions of live location pings per second. The cell IDs are also hierarchical, so you can
[16:19] zoom out by just truncating the ID. The trade-off is that you're mostly stuck artifacts where two locations a meter apart can land on very different keys, which means you usually have to query a ring of neighbor cells and post filter
[16:34] thumb is pretty simple. If you need shapes and exact geometry, reach for a custom tree, but understand the limitations on write throughput. If you have points at scale with heavy writes, reach for those encoded keys like
[16:47] GeoHashes, S2, or H3. Thanks everybody for watching. I really hope you enjoyed this video today. If you want to learn more about proximity search, database indexing, or anything system design, head over to hellointerview.com.