Shadowing Practice: Proximity Search & Geospatial Indexes Explained - Learn English Speaking with Video
Creating lesson...
1
Your database can easily find every user between age 20 and 30 in milliseconds.
2
But when you ask it to find every driver within two kilometers of a rider for an Uber-like app, it falls over.
3
Now on the surface, these two queries look really similar, but they're actually very different.
4
The age query is fast because a B tree keeps sorted keys packed together on disk.
5
20 sits next to 21, sits next to 22, they're all on the same page.
6
So everyone between 20 and 30 is one seek and a short read.
7
Location doesn't work that way.
8
You have two numbers, latitude and longitude.
9
And what you care about is the straight line distance between two points.
10
Two B trees don't save you here either.
11
One on lat gives you a horizontal strip of the earth.
12
One on long gives you a vertical strip of the earth.
13
And their intersection is still millions of rows
14
that you have to check the distance between them and your point of interest by hand.
15
Now, the real problem is that 1D sort order doesn't preserve 2E closeness.
16
Take two cabs parked five blocks away in midtown Manhattan.
17
They're neighbors.
18
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,
19
gets crammed into the index between these two neighbors.
20
They're a block apart on the street and millions of rows apart in your database.
21
Any naive flattening of 2D into 1D rips apart the relationship we actually care about.
22
Now every modern production system, Postgres, Elasticsearch, Redis, Google Maps, Uber, they've all converged on one of two approaches to solving this proximity search problem.
23
Either build a custom tree like a B-tree but specially tuned for location, or turn latitude and magnitude into a single key that a plain B-tree can already sort.
24
Why is B-tree the prize?
25
Because it's the one data structure databases have spent 50 years tuning.
26
It stays balanced as data changes, it packs sorted keys into disk pages so a range query is one seek in a sweep, and every database you'd ever reach for our E-ships one.
27
If you can squeeze your spatial problem into a B-tree shape, you inherit all of that for free.
28
Now, this sounds more complicated than it is.
29
Both approaches end up at the same price, a balanced tree of pages on disk that you can range scan.
30
Let's walk through how we get there.
31
The first serious attempt came in 1974 from Finkel and Bentley.
32
They called it the quad tree, and it's an incredibly useful foundation to understanding proximity search.
33
Take your whole map, split it into four quadrants.
34
If any quadrant has too many points in it, Split that one into four again.
35
Now you can keep doing this recursively until every leaf has a manageable number of points.
36
To find points near a location, you just descend that tree one level at a time.
37
At each node, you compare the query points latitude and longitude against the cell's midpoint.
38
North or south, east or west.
39
That picks one of the four children and you recurse into it.
40
You then repeat this until you land on a leaf.
41
Then you check the neighboring leaves too to catch anything that happened to sit just on the boundary from your query point.
42
What's really nice about this is that it adapts to density.
43
Manhattan ends up as a deep tree because it's full of pins.
44
A lake upstate stays a single core cell because nothing there.
45
We don't waste a bunch of space indexing the ocean.
46
But this has a really bad downside on latency at scale.
47
Because these splits always happen at the geometric midpoint of a cell, not where the data actually sits,
48
a dense cluster like Manhattan just keeps getting sliced in half over and over and over again until those points finally separate.
49
You burn tens or more levels of depth in your tree before you actually reach a leaf node, whereas a query in Vermont might have a depth of just two.
50
That means that your query latency depends on where in the world you're looking.
51
You can't reason about worst-case performance very well, and the hot regions, the ones that you actually care about, like Manhattan, are the slowest.
52
There's also a disk problem.
53
A quad tree 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.
54
That works beautifully when the whole tree fits in RAM because following pointers is a really cheap memory lookup.
55
But databases can't make the assumption that the whole tree fits in memory.
56
They read data from disk and fix page sizes
57
and every pointer you follow has a good chance of pointing you at a page
58
that you haven't loaded yet which forces random disk reads every single time.
59
A few hops in and you're spending most of your query time waiting on the disk instead of doing useful work.
60
Now you still see quadtrees today.
61
Google Maps uses them for map tile systems, game engines use them for collision detection, But for a scale database where the index has to live on disk and stay efficient when it doesn't fit in memory,
62
we need something smart.
63
Well, one year later in 1975, the same guy, he came back with a binary cousin he called the KD tree.
64
The idea is that instead of splitting all dimensions at once into four quadrants, alternate.
65
At level zero, split on X.
66
At level one, split on Y.
67
Then back to X, back to why you get the picture.
68
One dimension per level cycling through.
69
This gives you a binary tree for multi-dimensional data that's balanced, importantly, if you split at the median.
70
And it was the workhorse for nearest neighbor type searches for decades.
71
But KD trees, they have the same disk problem as quad trees.
72
There's pointers everywhere.
73
There's no clean mapping to pages.
74
And so great in memory, but painful off of it.
75
The modern fix is what's called a BKD tree, short for block KD tree.
76
Instead of one point per node, points get packed into blocks sized to a disk page.
77
And the whole tree is built once from a batch of data.
78
Elasticsearch actually uses this for their geo fields today.
79
So when you run a geo query in Elasticsearch, you're hitting a 50 year old algorithm with a disk friendly wrapper, which is pretty cool.
80
Next, in 1984, Antonin Gutman at Berkeley, he came up with the first spatial index designed specifically for a database.
81
Guttman had two problems that Quadtrees and KDtrees hadn't handled.
82
The first was shapes.
83
Every index before this one assumed your data was a point, like a driver or a pin or a user location.
84
But real geographic data has lines and polygons.
85
A highway is a line.
86
A country is a polygon.
87
A Starbucks might be a point, but the Starbucks delivery zone is a polygon.
88
And so you can't meaningfully drop a country into a Quadtrees cell.
89
The second was the disk issue.
90
Guttman wanted the spatial analog of a B-tree.
91
Balanced, fast to read off of disk, fast to update when drivers move, the pointer-heavy in-memory structures weren't gonna cut it anymore.
92
His answer was to use minimum bounding rectangles.
93
Every single object gets wrapped in the smallest rectangle that contains it, with sides parallel to the latitude and longitude axes on the map.
94
A point is a rectangle with zero width and height.
95
A highway gets a long, thin rectangle around it, and a country, of course, gets a big rectangle that bounds it.
96
Then nearby rectangles can get grouped into larger enclosing rectangles.
97
Those group into bigger ones all the way up to the root.
98
The clever part of this is that this tree stays balanced like a bee tree.
99
Every leaf lives at the same depth so every query touches the same predictable number of pages from the database.
100
Every node fits into a disk page, inserts and deletions rebalance by splitting and merging pages just like a regular bee tree does.
101
There's one trade-off to call out here.
102
Unlike quadtree cells, archery rectangles can overlap.
103
So if your query point lands inside two bounding rectangles at once, you have to descend both branches and check both subtrees.
104
So a bad insertion strategy produces lots of overlap, which means a lot of branches to follow, which tanks performance.
105
Archeries are the workhorse of production spatial indexes.
106
PostGIS, SQLite, Oracle Spatial, they all use an archery variant under the hood.
107
Six years after Gutmann's paper, a team in Germany published the R-Star tree, which uses a smarter insertion algorithm to minimize those overlaps we were just talking about.
108
And that insertion heuristic is what almost all of the modern R-Tree implementations are built on today.
109
Really quick, if you're preparing for interviews, come join the hundreds of thousands of candidates who use hellointerview.com every single month.
110
We've got tons of free content across all interview types, like system design, coding, behavioral, and even AI coding.
111
We also have premium breakdowns, videos, and an interactive of guided practice that candidates love.
112
Now, back to the video.
113
Okay, still with me?
114
Let's take a quick second to zoom back out.
115
Everything we've looked at so far, quad trees, KD trees, R trees, they're all custom tree structures.
116
They work, but they're complicated.
117
Your database needs special indexing code, special query code, special tooling.
118
What if instead we skipped all of that?
119
What if we could take latitude and longitude and turn them into a single number, just one integer, where numerically close integers meant geographically close locations?
120
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 box.
121
This is that second camp, and it's the idea that took over most of the industry.
122
In 2008, a developer named Gustavo Niemeyer took decades-old math
123
and turned it into something you can actually compute in a few lines of code.
124
He called it a geohash.
125
The idea is dead simple.
126
Divide the world into a grid of 32 cells and label each one with a character.
127
Your location falls into one of them, and that's your first character.
128
Now, take that cell and divide it into 32 smaller cells.
129
Your location again falls into one of those.
130
That's your second character.
131
Keep recursing as deep as you want.
132
Each additional character zooms in further to the map.
133
A five character geohash, for example, is about five kilometers across.
134
Nine characters gets you all the way down to five meters.
135
The final string, something like dr5ru, is your 2D location encoded as a 1D key.
136
The payoff is that strings sharing a prefix are usually near each other.
137
And here's the part that's really worth pausing on.
138
Each character picks one of 32 options, which is exactly five bits.
139
So a geohash isn't really a string, it's a stack of bits.
140
The string dr5ru is 25 of those bits grouped into five letters for human readability.
141
Read the same 25 bits straight through as a number, and you've got an integer.
142
Same bits, same sort order.
143
That's why Redis can store a geohash of 52-bit integers and Postgres can store it as text.
144
And both indexes behave exactly the same way.
145
The 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.
146
Where geohash like dr5ru wildcard, that's just a regular B-tree prefix scan.
147
It's totally efficient.
148
This is how Redis Geo commands work in production.
149
When you call a geoadd, Redis computes a 52-bit GeoHash integer and stores it in a sorted set, which is Redis' name for a B-tree-like structure that keeps entries ordered by a numerical score.
150
A nearby query is just a Z range by score against that sorted set.
151
Basically, a range scan over the geohash integers.
152
This is one of the most elegant uses of an existing data structure that you'll find in production.
153
There is one catch worth noting, though.
154
Geohashes have edge cases at cell boundaries.
155
Two points a meter apart can actually end up landing in completely different cells, and therefore get completely different prefixes if they straddle the boundary.
156
Picture a writer standing right on the edge of a cell, dr5ru.
157
The closest driver might be 10 meters away in cell DR5RG.
158
A naive prefix scan over DR5RU would miss them entirely.
159
The standard fix is what's called the 3x3 trick.
160
You compute the cell your query point lands in, then walk to the eight neighboring cells and query all nine as a unit.
161
That way you can't miss anyone within one cell's distance of you, no matter how close to a boundary you are.
162
You can then post-filter the results by exact distance to drop the corners that are technically in your query window, but actually too far away.
163
And almost every encoded key index in production does some version of this trick at query time.
164
All right, now geohash works great when we're mapping out a city, but it starts to hurt when you look at a globe.
165
The problem is that geohash treats latitude and longitude as if they lived on a flat rectangle.
166
And the earth isn't flat.
167
A degree of longitude is about 111 kilometers at the equator and nearly zero at the pulse.
168
So a cell that's one geohash character wide is a fat square at the equator
169
and a tiny sliver near each of the poles.
170
You want cells of roughly equal area everywhere on Earth.
171
And you want a 1D ordering that preserves locality on a sphere, not just a rectangle.
172
So around 2011, Google built S2 to fix this.
173
The trick is to wrap the sphere in a cube and project the Earth onto its six flat surfaces.
174
On each face, you can subdivide cleanly into cells that stay roughly the same size anywhere on the globe.
175
Every location ends up with a 64-bit integer called an S2 cell ID.
176
And like the geohash, the IDs are hierarchical.
177
Truncate the ID and you get a coarser parent cell.
178
S2 is what powers MongoDB's 2D sphere index.
179
When your geoquery correctly handles a polygon that crosses the anti-meridian, that's S2 under the hood.
180
Flat Earth indexes treat such a polygon as stretching all the way around the globe.
181
But S2 knows better.
182
Okay, last one now.
183
In 2008, Uber open sourced H3, which they use for dispatch and surge pricing.
184
The twist with H3 is that it uses hexagons instead of squares.
185
Why?
186
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.
187
That asymmetry makes heat maps and everyone within NSTELS of me queries messy.
188
So a hexagon has exactly six neighbors, all at the exact same distance from each other.
189
And so it's clean math for the kind of analytics that Uber runs every single day.
190
H3 tiles the entire globe in hexagons, and each hexagon roughly subdivides into seven smaller hexagons.
191
So you can zoom in as far as you need, just like with S2 and Geohashes.
192
You get 16 resolutions in total, from continent-sized cells down to about a square meter.
193
Every cell gets a 64-bit integer ID.
194
And again, like Geohash and S2, the IDs are hierarchical.
195
Zero out the end of the ID and get a parent cell.
196
Now you might be wondering, how do you sort a hexagon in the first place?
197
And the honest answer is that you don't sort the hexagons themselves.
198
You sort their IDs.
199
So H3 walks the hexagon grid in a deterministic order, kind of like a space-filling curve,
200
and it assigns each cell along that walk an integer that gets larger as you move along the path.
201
Math aside, the result is the same property GeoHash and S2 give you.
202
Numerically closed IDs are usually geographically close to each other, so that a B-tree can scan over those IDs, giving you a clump of nearby hexagons.
203
Now Now, the way that it works in production is that every driver reports their location, and the system converts that latitude and longitude into an H3 cell, say a 200 meter cell.
204
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.
205
If you need a wider net, expand to the cells around those, and continue this until you find the closest driver.
206
Okay, let's start to summarize what we learned.
207
We threw a lot at you there.
208
Every production spatial index falls into one of two types.
209
The trade-offs between them are pretty clear once you know what to look for.
210
The first type is those custom spatial trees.
211
The database ships a purpose-built tree tuned to behave like a B-tree on disk, where it's balanced, page size nodes,
212
predictable depths, but it doesn't explicitly use a B-tree.
213
PostGist uses an R-tree variant.
214
Elasticsearch uses that BKD tree.
215
These really shine when you care about shapes and accuracy.
216
An R-tree doesn't just index points.
217
It indexes lines, polygons, and complex geometries, which means that you can ask things like, does this highway intersect this country?
218
Or which delivery zone contains this address?
219
And you get an exact answer.
220
The downside is that your database has to ship a real spatial extension.
221
So you can't do this in a generic setup, and writes are expensive.
222
R tree inserts run a rectangular packing heuristic to minimize that overlap we talked about earlier.
223
And BKD trees are basically write once since they're designed for immutable segments.
224
That makes them a bad fit for data that changes a lot, like with Uber, where you have many moving drivers.
225
The second type is the encoded key.
226
You basically turn latitude and longitude into a single sortable integer and drop it into a regular run-of-the-mill B-tree, and then you're done.
227
Redis uses GeoHash, MongoDB 2Sphere uses S2, and Uber uses H3.
228
This approach wins out on simplicity and speed.
229
It works in any database with a B-tree or a sorted structure.
230
There's no spatial extension required.
231
Writes are dirt cheap
232
because a driver moving around is just a single integer update on an index that the database has already been tuned for.
233
And that's exactly why Uber can handle millions of live location pings per second.
234
The cell IDs are also hierarchical, so you can zoom out by just truncating the ID.
235
The trade-off is that you're mostly stuffed with points, and you get boundary artifacts where two locations a meter apart can land on very different keys,
236
which means you usually have to query a ring of neighbor cells and post filter by exact location.
237
Now the rule of thumb is pretty simple.
238
If you need shapes and exact geometry, reach for a custom tree, but understand the limitations on write throughput.
239
If you have points at scale with heavy writes, reach for those encoded keys like geohashes, S2, or H3.
240
Thanks everybody for watching.
241
I really hope you enjoyed this video today.
242
If you want to learn more about proximity search, database indexing, or anything system design, head over to hellointerview.com.
243
Thank you.
📺 Same Channel
C16
Distributed Transactions Explained: 2 Phase Commit vs Saga Pattern
University StudentsBusiness English+1
C11
Why Shopify Moved Inventory Reservations from Redis to MySQL
University StudentsBusiness English+1
C12
Concurrency in Low-level Design Interviews w/ Staff Engineer
University StudentsBusiness English+2
C13
CAP Theorem in System Design Interviews
University StudentsBusiness English+2
C11
API Gateways in System Design Interviews w/ Ex-Meta Staff Engineer
University StudentsBusiness English+2
C1Message Queues in System Design Interviews w/ Meta Staff Engineer
University StudentsBusiness English+2
C1Elasticsearch Deep Dive w/ a Ex-Meta Senior Manager for System Design Interviews
University StudentsBusiness English+2
C1API Design in System Design Interviews w/ Meta Staff Engineer
University StudentsBusiness English+2
C1Redis Deep Dive w/ a Ex-Meta Senior Manager
University StudentsBusiness English+1
C1Recommendation System Infra Basics 1
University StudentsBusiness English+1
C1Consistent Hashing: Easy Explanation for System Design Interviews
University StudentsWorking Adults+1
✨ Recommend Video
C11
77 sentences
The Secret Sauce Behind NoSQL: LSM Tree
University StudentsBusiness English+1
C11
392 sentences
Uber Data Engineering Mock Interview - Ride-Sharing Data Warehouse Schema
University StudentsBusiness English+2
C11
54 sentences
Traceroute: You're Probably Reading the Results Wrong
University StudentsBusiness English+1
C1762 sentences
Building Anthropic | A conversation with our co-founders
University StudentsBusiness English+1
C11
218 sentences
Next.js 16.3 got good (if you care)
University StudentsBusiness English+1
C112
47 sentences
Essence of linear algebra preview
American Accent, en-USUniversity Students+2
C11
156 sentences
SELECT COUNT (*) can impact your Backend Application Performance, here is why
University StudentsBusiness English+1
C11
149 sentences
Inside a warehouse run by AI robots
University StudentsBusiness English+1
C11
137 sentences
JUST $1 For Billions of Tokens?! (DeepSeek v4 Pro)
University StudentsBusiness English+1
C13
24 sentences
Pokemon Go était lié à la CIA…
University StudentsBusiness English+2
C11
51 sentences
What's Under Your Feet in New York City?
University StudentsBusiness English+1
C1604 sentences
I Left a $100B Giant to Build dLocal | CEO Pedro Arnt
University StudentsBusiness English+1
About This Lesson
You're practicing English with "Proximity Search & Geospatial Indexes Explained" using the Shadowing technique — a method originally developed for professional interpreter training.
Focus on sounding like the speaker — not just repeating words. With 15–30 minutes of daily practice, you'll build real-world speaking confidence.
What is the Shadowing Technique?
Shadowing is a science-backed language learning technique originally developed for professional interpreter training and popularized by polyglot Dr. Alexander Arguelles. The method is simple but powerful: you listen to native English audio and immediately repeat it out loud — like a shadow following the speaker with just a 1–2 second delay. Unlike passive listening or grammar drills, shadowing forces your brain and mouth muscles to simultaneously process and reproduce real speech patterns. Research shows it significantly improves pronunciation accuracy, intonation, rhythm, connected speech, listening comprehension, and speaking fluency — making it one of the most effective methods for IELTS Speaking preparation and real-world English communication.