跟讀練習: Proximity Search & Geospatial Indexes Explained - 通過影片學習英語口語

選擇練習模式

每種模式都會開啟全屏練習室。

243 句

如果句子過短或過長，請點選 Edit 進行調整。

Your database can easily find every user between age 20 and 30 in milliseconds.

But when you ask it to find every driver within two kilometers 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 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 all on the same page.

So everyone between 20 and 30 is one seek and a short read.

Location doesn't work that 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 either.

One on lat gives you a horizontal strip of the earth.

One on long gives you a vertical strip of 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 2E closeness.

Take two cabs parked five blocks away in midtown 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.

They're a block apart on the street and 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, they've all converged on one of two 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 magnitude into a single key that a plain B-tree can already sort.

Why is B-tree 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 a range query is one seek in a sweep, and every database you'd ever reach for our E-ships one.

If you can squeeze your spatial problem into a B-tree shape, you inherit all of that for free.

Now, this sounds more complicated than it is.

Both approaches end up at the same price, a balanced tree of pages on disk that you can range scan.

Let's walk through how we get there.

The first serious attempt came in 1974 from Finkel and Bentley.

They called it the quad tree, and it's an incredibly useful foundation to understanding proximity search.

Take your whole map, split it into four quadrants.

If any quadrant has too many points in it, Split that one into four again.

Now you can keep doing this recursively until every leaf has a manageable number of points.

To find points near a location, you just descend that tree one level at a time.

At each node, you compare the query points latitude and longitude against the cell's midpoint.

North or south, east or west.

That picks one of the four children and you recurse into it.

You then repeat this until you land on a leaf.

Then you check the neighboring leaves too to catch anything that 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 core cell because nothing there.

We don't waste a bunch 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 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 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.

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 the slowest.

There's also a disk problem.

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.

That works beautifully when the whole tree fits in RAM because following pointers is a really cheap memory lookup.

But databases can't make the assumption that the whole tree fits in memory.

They read data from disk and fix page sizes

and every pointer you follow has a good chance of pointing you at a page

that you haven't loaded yet which forces random disk reads every single time.

A few hops in and you're spending most of your query time waiting on the disk instead of doing useful 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 database where the index has to live on disk and stay efficient when it doesn't fit in memory,

we need something smart.

Well, one year later in 1975, the same guy, he came back with a binary cousin he called the KD tree.

The idea is that instead of splitting all dimensions at once into four quadrants, alternate.

At level zero, split on X.

At level one, split on Y.

Then back to X, back to why you get the picture.

One dimension per level cycling through.

This gives you a 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 quad trees.

There's pointers everywhere.

There's no clean mapping to pages.

And so great in memory, but painful off of it.

The modern fix is what's called a BKD tree, short for block KD tree.

Instead of one 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 hitting a 50 year old algorithm with a disk friendly wrapper, which is pretty cool.

Next, in 1984, Antonin Gutman at Berkeley, he came up with the first spatial index designed specifically for a database.

Guttman had two problems that Quadtrees and KDtrees 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 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 Quadtrees cell.

The second was the disk issue.

Guttman wanted the spatial analog of a B-tree.

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.

His answer was to use minimum bounding rectangles.

Every 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 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 this tree stays balanced like a bee tree.

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.

下載應用

流利口語所需的一切

AI 發音評分逐句打分

音標練習掌握每個音

詞彙學習建立你的詞庫

詞彙遊戲邊玩邊學

掃碼

Download on theApp Store Get it onGoogle Play

同頻道

Elasticsearch Deep Dive w/ a Ex-Meta Senior Manager for System Design Interviews

Business EnglishInterview EnglishUniversity Students

API Design in System Design Interviews w/ Meta Staff Engineer

Business EnglishInterview EnglishUniversity Students

Redis Deep Dive w/ a Ex-Meta Senior Manager

Business EnglishUniversity StudentsWorking Adults

Recommendation System Infra Basics 1

Business EnglishUniversity StudentsWorking Adults

Consistent Hashing: Easy Explanation for System Design Interviews

Interview EnglishUniversity StudentsWorking Adults

FOR YOU

本課的詞彙與口語要點

這節 C1 級別的口語課以影片“Proximity Search & Geospatial Indexes Explained”為素材。影片中反覆出現的詞有：tree, cell, query, database, disk。這段影片共有 243 個句子、3302 個單詞可供跟讀。講話部分時長為 17:06。說話人語速較快，每分鐘約 193 個詞，會出現較多連讀和弱讀。只有 74% 的單詞屬於英語最常用的 3,000 詞，詞彙難度較高。

影片中的重點詞彙

影片中最難的 15 個單詞，附發音和釋義：

單詞	發音	釋義
query 名詞	/ˈkwɪɹ.i/	問題 /問題, 質問 /質問
disk 名詞	/dɪsk/	圓盤 /圓盤
integer 名詞	/ˈɪn.tɪ.d͡ʒə(ɹ)/	整數 /整數
longitude 名詞	/ˈlɑnd͡ʒəˌtud/	經度 /經度
rectangle 名詞	/ˈrɛktæŋɡl̩/	長方形 /長方形, 矩形
hexagon 名詞	/ˈhɛk.sə.ɡɑn/	六邊形 /六邊形, 六角形
latitude 名詞	/ˈlætɪtud/	緯度 /緯度
spatial 形容詞	/ˈspeɪ.ʃəl/	空間的 /空間的
polygon 名詞	/ˈpɑliˌɡɑn/	多邊形 /多邊形, 多角形
pointer 名詞	/ˈpɔɪn.təɹ/	教鞭
node 名詞	/noʊd/	結節 /結節
prefix 名詞	/ˈpɹiːfɪks/	字首 /字首, 詞頭 /詞頭
metre 名詞	/ˈmiːtəɹ/	米, 公尺
proximity 名詞	/pɹɒkˈsɪm.ɪ.ti/	接近
sphere 名詞	/sfɪɚ/	球體 /球體

影片中出現的短語動詞

單詞	發音	釋義
end up 動詞		到達
come up with 動詞		想出, 提出
take over 動詞		接管, 接手
zoom out 動詞	/ˌzuːm ˈaʊt/	縮小 /縮小

值得反覆跟讀的句子

影片中簡短而完整的句子，可以直接用在日常對話裡：

Let's walk through how we get there.
Let's take a quick second to zoom back out.
What if instead we skipped all of that?

影片中的語法

說話人最常用的結構，並附上影片中的原話：

結構	影片中的用法
定語從句 who / which + 從句 — 補充說明人或事物	structure, which means · wrapper, which is · overlap, which means
現在完成時 have/has + 過去分詞 — 過去發生但與現在仍有關聯的事	have spent · haven't loaded · we've looked
被動語態 be + 過去分詞 — 強調發生了什麼，而不是誰做的	is built · are built · been tuned

需要注意的發音

說話人用了 40 次縮略和弱讀形式，例如 they're, you're, can't。請按聽到的簡短形式來說。

“th” 音: algorithm /ˈælɡəɹɪðm̩/, thumb /ˈθʌm/, width /ˈwɪtθ/
“sh” 和 “zh” 音: spatial /ˈspeɪ.ʃəl/, insertion /ɪnˈsɝʃən/, dimension /daɪˈmɛn.ʃən/, limitation /lɪmɪˈteɪʃən/, collision /kəˈlɪʒn̩/
長單詞——注意重音位置: proximity /pɹɒkˈsɪm.ɪ.ti/, hierarchical /ˌhaɪəˈɹɑːkɪkəl/, predictable /pɹəˈdɪktəbləl/, limitation /lɪmɪˈteɪʃən/, dimensional /daɪˈmɛn.ʃə.nəl/

中文母語者容易讀錯的音：

/v/ — 不要讀成 /w/，上齒輕觸下唇: overlap /ˌəʊvəˈlæp/, naive /naɪˈiv/, variant /ˈvæɹi.ənt/, behave /bɪˈheɪv/, interactive /ˌɪn.tɚˈæk.tɪv/
詞尾子音 — 要讀清楚，後面不要加母音: disk /dɪsk/, longitude /ˈlɑnd͡ʒəˌtud/, latitude /ˈlætɪtud/, node /noʊd/, encode /ɪnˈkoʊd/
/r/ 和 /l/ 的區別: rectangle /ˈrɛktæŋɡl̩/, hierarchical /ˌhaɪəˈɹɑːkɪkəl/, predictable /pɹəˈdɪktəbləl/, algorithm /ˈælɡəɹɪðm̩/, importantly /ɪmˈpɔɹ.tənt.li/

如何用這段影片練習

先完整聽一遍影片，不要開口，記下不認識的單詞。
先用 0.75 倍速逐句跟讀，熟練之後再回到正常速度。
錄下自己的聲音並與原聲對比，特別注意 query, disk, integer 這類單詞。

什麼是跟讀法？

跟讀法 (Shadowing) 是一種有科學依據的語言學習技巧，最初開發用於專業口譯員的培訓，並由多語言者Alexander Arguelles博士普及。這個方法簡單而強大：您在聽英語母語原聲的同時立即大聲重複——就像是一個延遲1-2秒緊跟說話者的影子。與被動聽力或語法練習不同，跟讀法強迫您的大腦和口腔肌肉同時處理並模模擬實的講話模式。研究表明它能顯著提高發音準確性，語調，節奏，連讀，聽力理解和口語流利度——使其成為雅思口語備考和真實英語交流最有效的方法之一。

影子跟讀法: 閱讀完整分步指南 →

跟讀練習: Proximity Search & Geospatial Indexes Explained - 通過影片學習英語口語

選擇練習模式

下載應用

同頻道

Distributed Transactions Explained: 2 Phase Commit vs Saga Pattern

Why Shopify Moved Inventory Reservations from Redis to MySQL

Concurrency in Low-level Design Interviews w/ Staff Engineer

CAP Theorem in System Design Interviews

API Gateways in System Design Interviews w/ Ex-Meta Staff Engineer

System Design Interview: Design Ticketmaster w/ a Ex-Meta Staff Engineer

Message Queues in System Design Interviews w/ Meta Staff Engineer

Elasticsearch Deep Dive w/ a Ex-Meta Senior Manager for System Design Interviews

API Design in System Design Interviews w/ Meta Staff Engineer

Redis Deep Dive w/ a Ex-Meta Senior Manager

Recommendation System Infra Basics 1

Consistent Hashing: Easy Explanation for System Design Interviews

推薦影片

What's new in Google Cloud in less than 1 minute

what is a database index?

Real-Time Digital Twins Using CFD, Sensors & AI - Haris Kokkinos | Podcast #165

MiniMax 2026 06 09 06 47 09 Captivating Female

Easy Migration from Postgres to Databricks Lakebase

Urban Designer Answers City Planning Questions From Twitter | Tech Support | WIRED

System Design: Why is Kafka fast?

Is Amazon Too Big?

Understand search engine optimization (SEO) | Google Digital Marketing & E-commerce Certificate

The Essential Main Ideas of Neural Networks

World Models explained in 10min..