System Design Interview Vol. 2 · 第 1 章Triton 覆蓋度:🟢 高(窄)Triton 線

Proximity Service
附近有什麼好吃的?

原書把五種空間索引講得很漂亮:二維搜尋、均勻網格、geohash、quadtree、Google S2。Triton 只談了這章的一小塊,但那一句很重:先算 N 和 m。1 萬個點,兩層 for-loop 不到一秒;真的大了,也是用 PostGIS、Elasticsearch 現成的 index,不要自己寫 quadtree。

給文組

全程只用「找 500 公尺內的珍奶店」,一階一階爬 10 個概念。頁首標 延伸基礎 的頁是補基礎,懂的人可以跳過。

給工程師

原書 21 張圖、12 個表全部重繪;最後一頁列出所有出處(materials/core)與頁碼對照。

標籤怎麼看

📖 原書 🗣️ Triton 本人說 🔭 依 Triton 原則推論 📅 2026 補充

先用生活理解為什麼需要「分格」

在台北找 500 公尺內的珍奶店

笨方法:把全台灣每一家店跟你的距離都量一次。聰明一點的方法:先看你在哪一區,只翻你這一格和隔壁 8 格的店。

這就像地址從大寫到小:台北市 → 大安區 → 某某里 → 某條路。同一個里的人一定住得近。等一下的 geohash 就是把「地址從大寫到小」變成一串字,例如 9q8yym:字頭一樣得越多,通常越近。

試試看:點地圖換你的位置,切換兩種找法。兩種找到的店一樣多,但要量距離的店差很多。

600要量距離的店0500 公尺內找到—省下的力氣

學習地圖本章的概念階梯

今天爬 10 階。每一階只用前面講過的東西。

  1. 1經緯度地球上的座標
  2. 2index照一種順序排的目錄
  3. 3read replica多印幾本給人查
  4. 42D search兩個條件取交集
  5. 5grid把地圖切成棋盤
  6. 6geohash地圖對折再對折
  7. 7鄰格住在格線旁的鄰居
  8. 8quadtree太擠就加隔板
  9. 9Hilbert curve一筆畫的蛇
  10. 10N 和 m先數有幾家

第 1–3 階 · 位置和電話簿

要回答:「附近」要怎麼用數字講?資料庫怎麼找得快?

第 4–7 階 · 把地圖切格子

要回答:兩個方向的條件,怎麼變成一個能查的字串?

第 8–9 階 · 會長大的格子

要回答:店擠在市中心,格子能不能跟著變細?

第 10 階 · Triton 的問題

要回答:你的店真的有 2 億家嗎?

全程只用一件事:你在台北,要找 500 公尺內的珍奶店

你站的位置 = 經緯度店家名冊 = database名冊的目錄 = index對折地圖的答案 = geohash收納盒的隔板 = quadtree

每爬 2–4 階,有一頁「到這裡你已經會了」。資料庫、cache、sharding 這些前面章節講過的,只用一句話帶過並附連結。

延伸基礎第 1 階 · 經緯度懂的人可以跳過

  1. 經緯度
  2. index
  3. read replica
  4. 2D search
  5. grid
  6. geohash
  7. 鄰格
  8. quadtree
  9. Hilbert curve
  10. N 和 m

兩個數字,就能說出你站在地球的哪裡

① 先想像

跟朋友約見面:「我在車站往北 2 條街、往東 3 條街。」兩個數字,就把位置講清楚了。

你猜猜看:台北 101 大約在「緯度 25.03、經度 121.56」。你往正北走一段路,哪個數字會變大?

③ 這叫做 latitude、longitude

latitude(緯度):南北,赤道是 0、北極是 90。longitude(經度):東西,英國格林威治是 0,往東、往西各到 180。

④ 跟這章的關係

App 送給後端的就是這兩個數字(原書 Table 1)。「附近」就是兩個數字都差不多。

② 動手玩:點地圖,放下你自己

25.040緯度(南北)121.540經度(東西)—到珍奶店(心算)

原書開場Figure 1

Proximity service:找附近的餐廳、加油站

這一步要解決的問題這個服務到底要做什麼?先看一個大家都用過的畫面。

📖 原書 Proximity service(鄰近服務)用來發現附近的地點:餐廳、旅館、劇院、博物館。它是 Yelp「找附近最好的餐廳」、Google Maps「找最近的 k 個加油站」背後的核心元件。

原書 Figure 1 是 Yelp 的搜尋畫面:上方搜尋列(tacos, cheap dinner, Max's、地點 1355 Market St, San Francisco, CA),左邊距離篩選(Bird's-eye View、Driving 5 mi、Biking 2 mi、Walking 1 mi、Within 4 blocks),中間三家店,右邊是標了編號的地圖。

原書註明:本章的地圖圖磚來自 Stamen Design,資料來自 OpenStreetMap。

原圖是產品截圖,這裡只重繪版面線框,不畫照片、商標與真實地圖。

📖 原書 Figure 1Yelp 上的附近搜尋(依原書內容重繪成線框示意)

原書 Step 1釐清需求

面試一開始:半徑多大、資料多久要生效?

這一步要解決的問題要找多遠?店家資料改了,多久要看到?問清楚,後面才知道哪裡可以簡單做。

📖 原書 應徵者 × 面試官

應徵者問面試官答
使用者能指定搜尋半徑嗎?半徑內商家不夠,要自動擴大嗎?先只管指定半徑內的;有時間再談擴大搜尋
最大半徑多少?可以假設 20 km(12.5 英里)嗎?合理
使用者能在 UI 上改半徑嗎?可以:0.5 km、1 km、2 km、5 km、20 km
商家資訊怎麼新增、刪除、更新?要即時反映嗎?商家業主可以增刪改;事先有商業協議:隔天才生效
使用者邊走邊用,結果會變,要一直刷新嗎?假設移動很慢,不用一直刷新

📖 原書 功能需求(3 個)

  1. 依使用者位置(緯度、經度)和半徑,回傳所有商家
  2. 商家業主可以新增、刪除、更新商家,但不需即時反映
  3. 顧客可以看商家的詳細資訊

📖 原書 非功能需求

  • 低延遲:很快看到附近商家
  • 資料隱私:位置是敏感資料,做 LBS 要遵守 GDPR、CCPA 等法規
  • 高可用、可擴展:撐得住人口密集區尖峰時段的流量

白話:LBS(location-based service)=依你的位置提供的服務;GDPR、CCPA=歐盟、加州的個資法;低延遲=等待時間短。

原書 Step 1Back-of-the-envelope estimation

1 億日活、2 億商家:搜尋 QPS 是 5,000

這一步要解決的問題一天有多少次搜尋、總共有幾家店?這兩個數字後面會一直用到。

📖 原書 假設:100 million DAU、200 million businesses,每位使用者每天搜尋 5 次。

一天的秒數 = 24 × 60 × 60 = 86,400 ≈ 105
Search QPS = 100 million × 5 ÷ 105 = 5,000

原書說 105 在整本書都用來代表一天的秒數,方便心算。

白話:DAU=每天有幾個人用;QPS=每秒來幾個請求。估算那份有完整的延伸基礎:DAU(第 22 頁)、QPS(第 23 頁)。

文組翻譯

一天大約十萬秒。一億人每天搜五次,就是五億次,平均每秒五千次。這是「平均」,吃飯時間會更高,原書在非功能需求裡已經提醒尖峰。

動手算

5,000

QPS

另一個數字先記住:N = 200 million 家商家。到 Triton 那段(第 45 頁),N 和這個 QPS 會一起決定要不要用索引。

原書 Step 2API design · Table 1、2

兩組 API:搜尋附近、管理商家

這一步要解決的問題App 要怎麼跟後端說「我在這裡、找多遠」?

📖 原書 GET /v1/search/nearby:依搜尋條件回傳商家。實務上結果通常會分頁,原書說分頁不是本章重點,但面試值得提一下。

📖 原書 Table 1Request parameters
FieldDescriptionType
latitude指定位置的緯度decimal
longitude指定位置的經度decimal
radius選填,預設 5000 公尺(約 3 英里)int

白話:API=App 和後端約好的窗口;decimal=有小數點的數字;int=整數;分頁=結果太多時一次只回一頁。


    

📖 原書 Response body:business object 只放搜尋結果頁需要的東西;點進詳細頁時,再呼叫另一個 endpoint 拿圖片、評論、星等。

{
 "total": 10,
 "businesses":[{business object}]
}
📖 原書 Table 2APIs for a business
APIDetail
GET /v1/businesses/{:id}回傳某商家的詳細資訊
POST /v1/businesses新增一個商家
PUT /v1/businesses/{:id}更新商家的詳細資料
DELETE /v1/businesses/{:id}刪除一個商家

原書推薦參考真實世界的 Google Places API 和 Yelp Reservation API。

延伸基礎第 2 階 · index懂的人可以跳過

  1. 經緯度
  2. index
  3. read replica
  4. 2D search
  5. grid
  6. geohash
  7. 鄰格
  8. quadtree
  9. Hilbert curve
  10. N 和 m

電話簿照姓氏排:找「王」很快,找「住大安區」很慢

① 先想像

電話簿照姓氏排好。找姓王的,翻到中間、看要往前還是往後,幾下就到。可是要找「住大安區的人」呢?

你猜猜看:1,000 頁的電話簿照姓氏排好。每次翻一半、看要往前還是往後,大約翻幾次就找到?

③ 這叫做 index

index(索引):事先照某個欄位排好的目錄,找東西不用整本翻。一個 index 只照一種順序排。

④ 跟這章的關係

店的位置是兩個欄位:緯度、經度。一個 index 只能照其中一個排,這就是原書接下來要解的難題。

② 動手玩:16 張名片,照姓氏排好

0翻了幾張—找到

按上面兩個按鈕比較。

原書 Step 2Data model · Table 3

讀很多、寫很少:關聯式資料庫就很合適

這一步要解決的問題店家資料要存在哪種資料庫?要哪幾張表?

📖 原書 Read/write ratio

  • 讀很多:「搜尋附近」和「看商家詳情」這兩個功能非常常用
  • 寫很少:新增、刪除、編輯商家是不常發生的操作
  • 讀為主的系統,MySQL 這類關聯式資料庫很合適

📖 原書 兩張主要的表

business table:商家的詳細資訊,主鍵是 business_id(右圖)。

geospatial (geo) index table:用來有效率地處理空間查詢。要先懂 geohash,原書放到 deep dive 的「Scale the database」再講(第 35 頁)。

文組翻譯:這像一本電話簿。全台灣每天有很多人查,但一年只改版幾次。這種東西,最普通的資料庫就做得很好。

白話:關聯式資料庫(RDBMS)=一張張像 Excel 的表;PK(primary key)=每一列獨一無二的編號;index 見上一頁。資料庫是什麼:Vol.1 第 1 章第 8 頁。

business
business_idPK
address
city
state
country
latitude
longitude
📖 原書 Table 3Business table(原書以圖片呈現,依原書內容重繪成表格)

注意:latitude、longitude 是兩個欄位。下一頁會看到,光在這兩個欄位上各建一個 index,查「附近」還是不夠快。

延伸基礎第 3 階 · read replica懂的人可以跳過

  1. 經緯度
  2. index
  3. read replica
  4. 2D search
  5. grid
  6. geohash
  7. 鄰格
  8. quadtree
  9. Hilbert curve
  10. N 和 m

名冊一年改幾次,每天卻有上萬人來查:多印幾本

① 先想像

全台珍奶店名冊只有一本,櫃台前大排長龍。反正一年才改版幾次,那就多影印幾本,放在各個櫃台給人查。

你猜猜看:一本名冊每秒能應付 1,000 次查詢。每秒來 5,000 次,至少要幾本?

③ 這叫做 primary、read replica

primary:正本,只有它能改。read replica:影本,只給人查;從正本抄過去,會晚一點才跟上。

④ 跟這章的關係

原書:讀很多、寫很少,商家資料又是「隔天才生效」。影本晚一點跟上,完全沒關係。

② 動手玩:每秒來多少人查?

5需要幾本(每本每秒 1,000 次)

原書 Step 2High-level design · Figure 2

兩個服務:找附近(LBS)和管商家(Business service)

這一步要解決的問題搜尋和管理商家要分成幾個服務?讀和寫各走哪條路?

📖 原書 Figure 2High-level design(依原書內容重繪)

📖 原書 Load balancer:通常公司只給一個 DNS 入口,內部依 URL path 把 API 導到對的服務。

📖 原書 LBS(location-based service)是核心:給位置和半徑找附近商家。特性:只讀不寫;QPS 高,密集區尖峰更高;stateless,容易水平擴展。

📖 原書 Business service:業主增刪改(寫為主,QPS 不高)+顧客看詳情(尖峰 QPS 高)。

📖 原書 Database cluster:primary-secondary。primary 處理所有寫入,多個 replica 處理讀取。有 replication delay,所以 LBS 讀到的可能和剛寫進 primary 的不一樣,但商家資訊本來就不用即時,通常不是問題。

📖 原書 擴展:兩個服務都 stateless,用餐時間自動加機器、睡覺時間減機器;在雲端還能用多個 region 和 availability zone 提高可用性(第 39 頁)。

白話:DNS=網址的電話簿;load balancer=帶位員(Vol.1 第 1 章第 12 頁);stateless=機器不記客人的事,壞了換一台就好(第 24 頁);primary、replica 見第 11 頁。

到這裡你已經會了小結 1 / 4

  1. 經緯度
  2. index
  3. read replica
  4. 2D search
  5. grid
  6. geohash
  7. 鄰格
  8. quadtree
  9. Hilbert curve
  10. N 和 m

到這裡你已經會了:位置、目錄、多印幾本

下一階要解決的問題

「緯度差不多」而且「經度差不多」,兩個條件一起查,index 能幫多少?先看最直覺的做法。

延伸基礎第 4 階 · 2D search懂的人可以跳過

  1. 經緯度
  2. index
  3. read replica
  4. 2D search
  5. grid
  6. geohash
  7. 鄰格
  8. quadtree
  9. Hilbert curve
  10. N 和 m

「南北差不多」而且「東西差不多」:兩疊名單取交集

① 先想像

店要在你南北 500 公尺內,也要在你東西 500 公尺內。地圖上是一條橫帶和一條直帶,交叉的那一小塊才是答案。

你猜猜看:城裡 100 家店。南北符合的有 20 家,東西符合的有 20 家。兩個都符合的大概幾家?

③ 這叫做 2D search

2D search(二維搜尋):同時用兩個方向的條件找東西。index 只能先幫你撈出其中一疊。

④ 跟這章的關係

這就是原書 Option 1。城市一大,兩疊都很厚,交集卻很薄(下一頁)。

② 動手玩:100 家店,一條橫帶、一條直帶

0南北符合0東西符合0兩個都符合

原書 Step 2Algorithms · Option 1:Two-dimensional search · Figure 3、4

最直覺的做法:畫一個圓,找圓裡的店

這一步要解決的問題最直覺的「畫個圓找店」,資料庫做得快嗎?

📖 原書 現實中公司可能直接用現成的地理空間資料庫,例如 Redis 的 Geohash 或 Postgres + PostGIS。面試不用懂它們的內部,但解釋 geospatial index 怎麼運作,比只丟出資料庫名字更能展現能力。

SELECT business_id, latitude, longitude,
FROM business
WHERE (latitude BETWEEN {:my_lat} - radius AND {:my_lat} + radius) AND
 (longitude BETWEEN {:my_long} - radius AND {:my_long} + radius)

📖 原書 這個 query 要掃整張表。在經度、緯度上各建 index 呢?原書說「提升不多」:index 能很快拿到 dataset 1(緯度帶)和 dataset 2(經度帶),但要找半徑內的店得把兩個 dataset 取交集,而每個 dataset 都很大。

問題的根源:資料庫 index 一次只能加速一個維度。那能不能把二維資料映射成一維?原書:可以。

白話:query=問資料庫的一句話(這裡是 SQL);PostGIS=PostgreSQL 的地理套件;dataset=撈出來的一疊資料;維度=方向(南北是一個、東西是一個)。

📖 原書 Figure 3Two dimensional search(依原書內容重繪;原圖底圖是真實街道,這裡畫成示意街區)

延伸基礎第 5 階 · grid懂的人可以跳過

  1. 經緯度
  2. index
  3. read replica
  4. 2D search
  5. grid
  6. geohash
  7. 鄰格
  8. quadtree
  9. Hilbert curve
  10. N 和 m

把地圖畫成棋盤:每家店登記在它那一格

① 先想像

把台北地圖畫上棋盤格,每家店記下自己在第幾格。找附近的店,只翻你那一格的名單。

你猜猜看:64 家店,地圖切成 4 × 4 = 16 格。如果店平均分布,一格幾家?

③ 這叫做 grid

grid(網格):把地圖切成一樣大的方格。每家店只屬於一格,一格可以有很多家。

④ 跟這章的關係

原書 Option 2「evenly divided grid」。問題就是右邊看到的:市中心塞爆,郊區一格空著。

② 動手玩:64 家店擠在市中心

4平均一格—最擠的一格—空的格子

原書 Step 2索引分類 · Option 2:Evenly divided grid · Figure 5、6

兩大類索引;最簡單的一種:把世界切成一樣大的格子

這一步要解決的問題不畫圓,改成先把地圖切成格子呢?

📖 原書 Figure 5Different types of geospatial indexes(依原書內容重繪;標色的是原書詳細討論的,alt 說 Cartesian Tiers 也標色,這裡依內文只標四種)

📖 原書 Hash:even grid、geohash、cartesian tiers;Tree:quadtree、Google S2、R-tree。底層不同,高階概念一樣:把地圖切成小區域,建 index 加速搜尋。業界最常用的是 geohash、quadtree、S2。

📖 原書的 Reminder

真實面試通常不用解釋 index 的實作細節,但要懂:為什麼需要 geospatial index、高階怎麼運作、它的限制。

📖 原書 Figure 6Global map(依原書內容重繪;大陸輪廓為簡化示意)

📖 原書 一格可以有很多商家,每家商家屬於一格。問題:商家分布不均,紐約市中心一格塞爆,沙漠和海洋的格子一家都沒有。理想是密集處用細格、稀疏處用大格。另一個挑戰:找某一格的鄰格不容易。

延伸基礎 · 動手玩第 6 階 · geohash懂的人可以跳過

  1. 經緯度
  2. index
  3. read replica
  4. 2D search
  5. grid
  6. geohash
  7. 鄰格
  8. quadtree
  9. Hilbert curve
  10. N 和 m

把地圖對折再對折:每折一次,記下 0 或 1

① 先想像

拿一張地圖,左右對折:你在右半記 1、左半記 0。再上下對折:上半 1、下半 0。一直輪流折下去。

你猜猜看:左右、上下輪流,一共折 6 次。地圖被切成幾格?

③ 這叫做 geohash

geohash:把對折的 0/1 答案寫成一串字。每 5 個 0/1 換成一個字(base32),例如 9q8yym。

④ 跟這章的關係

兩個數字變成一串字。字頭一樣 = 同一格,一般的 index 就能照字頭查。原書接著照這規則切整個地球。

② 動手玩:對折找出你和珍奶店的位置碼

點地圖可以把「你」換個位置。

原書 Step 2Option 3:Geohash · Figure 7、8

Geohash:每多一個 bit,格子就切一半

這一步要解決的問題怎麼把「兩個數字」變成「一串字」,讓一般 index 能查?

📖 原書 Figure 7Geohash(依原書內容重繪;alt 對各象限大陸的描述和內文的 bit 規則對不上,這裡依內文:左上是西經北緯)

📖 原書 Geohash 把二維的經緯度壓成一維的字串(字母加數字),做法是遞迴地把世界切成越來越小的格子。

  1. 沿本初子午線和赤道切成四塊:緯度 [-90, 0] → 0、[0, 90] → 1;經度 [-180, 0] → 0、[0, 180] → 1
  2. 每格再切四格,經度 bit 和緯度 bit 交替
  3. 重複到格子夠小;通常用 base32 表示

📖 原書 兩個例子(長度 6)

Google 總部
1001 10110 01001 10000 11011 11010 → 9q9hvu

Facebook 總部
1001 10110 01001 10001 10000 10111 → 9q9jhr

兩家都在灣區,前 3 個字 9q9 一樣。原書第一組只寫 4 個 bit,是省略了開頭的 0(01001 = 9)。

白話:bit=一個 0 或 1(第 18 頁的「對折一次」);本初子午線=經度 0 那條線;赤道=緯度 0。

原書 Step 2Geohash 精度 · Table 4、5

長度選幾?選「剛好蓋得住你的圓」的最短長度

這一步要解決的問題geohash 要取幾個字,格子才剛好蓋住你要找的範圍?

📖 原書 Table 4Geohash length to grid size mapping
Geohash lengthGrid width × height
15,009.4km × 4,992.6km(the size of the planet)
21,252.3km × 624.1km
3156.5km × 156km
439.1km × 19.5km
54.9km × 4.9km
61.2km × 609.4m
7152.9m × 152.4m
838.2m × 19m
94.8m × 4.8m
101.2m × 59.5cm
1114.9cm × 14.9cm
123.7cm × 1.9cm

📖 原書 Geohash 有 12 個精度(level)。我們只在意長度 4 到 6:超過 6 格子太小,小於 4 格子太大。挑法是「蓋得住使用者半徑那個圓的最短長度」。點一列看圓和格子的比例:

📖 原書 Table 5Radius to geohash mapping
RadiusGeohash length
0.5 km (0.31 mile)6
1 km (0.62 mile)5
2 km (1.24 mile)5
5 km (3.1 mile)4
20 km (12.42 mile)4

延伸基礎第 7 階 · 鄰格懂的人可以跳過

  1. 經緯度
  2. index
  3. read replica
  4. 2D search
  5. grid
  6. geohash
  7. 鄰格
  8. quadtree
  9. Hilbert curve
  10. N 和 m

你住在格線旁邊:對面那家店在隔壁格

① 先想像

你家在大安區最邊邊,過一條馬路就是信義區。對面的珍奶店離你 50 公尺,可是「只查大安區」找不到它。

你猜猜看:一格寬 1 公里。你站在格子最右邊,要找 500 公尺內的店。只查自己這一格,會漏掉嗎?

③ 這叫做 neighbor、boundary issue

neighbor(鄰格):四周的 8 格。boundary issue(邊界問題):很近的兩點,剛好被格線分開。

④ 跟這章的關係

原書的解法:自己這格 + 8 個鄰格一起查。geohash 算出鄰格只要一瞬間。

② 動手玩:一格 1 公里,找 500 公尺內

0找到0500 公尺內卻漏掉

動手玩Geohash 地圖:放下你自己,看格子、鄰格和邊界問題

點地圖放下你的位置,看看會漏掉哪些店

這一步要解決的問題只查自己這一格夠不夠?親手放下自己試試。

0撈出的候選0半徑內找到0半徑內卻漏掉
半徑


      

原書 Step 2Boundary issues · Figure 9、10、11

前綴越長越近;但近的不一定前綴一樣

這一步要解決的問題字頭一樣就一定近;那近的店,字頭一定一樣嗎?

📖 原書 Figure 9Shared prefix:九格都以 9q8zn 開頭(依原書內容重繪;格子排列依 geohash 規則推定)

📖 原書 Geohash 保證:兩個 geohash 共享的前綴越長,距離越近(Figure 9 九格都以 9q8zn 開頭)。

📖 原書 Boundary issue 1:反過來不成立。赤道或本初子午線兩側的點屬於世界的不同「半邊」。法國的 La Roche-Chalais(u000)離 Pomerol(ezzz)只有 30 km,前綴卻完全不同。所以這個 query 會漏:

SELECT * FROM geohash_index WHERE geohash LIKE `9q8zn%`

📖 原書 Boundary issue 2:兩個點可能前綴很長,卻屬於不同 geohash(Figure 11)。

📖 原書 常見解法:不只撈自己這格,連鄰格一起撈。鄰格的 geohash 可以在常數時間算出來。上一頁的地圖可以親手試(第 22 頁)。

原書 Step 2Not enough businesses · Figure 12

加分題:附近的店不夠多,怎麼辦?

這一步要解決的問題附近的店太少,怎麼自動把範圍放大?

📖 原書 Option 1:只回傳半徑內的

好做,缺點很明顯:回傳的結果不夠,滿足不了使用者。

📖 原書 Option 2:擴大搜尋半徑

把 geohash 的最後一個字拿掉,用新的(比較短的)geohash 撈附近商家。還不夠就再拿掉一個。格子逐步變大,直到結果比需要的數量多。

用原書的座標算一次

每拿掉一個字,格子面積大約變成 32 倍(base32 一個字 = 5 bit)。

📖 原書 Figure 12Expand the search process(依原書內容重繪)

這一招 Triton 的講義裡也有,而且一模一樣:「否則用 i-1 byte 的 geohash 從來~」(第 46 頁)。

到這裡你已經會了小結 2 / 4

  1. 經緯度
  2. index
  3. read replica
  4. 2D search
  5. grid
  6. geohash
  7. 鄰格
  8. quadtree
  9. Hilbert curve
  10. N 和 m

到這裡你已經會了:把地圖切成能查的格子

下一階要解決的問題

geohash 的格子大小是固定的。能不能讓市中心格子細、郊區格子大?

延伸基礎第 8 階 · quadtree懂的人可以跳過

  1. 經緯度
  2. index
  3. read replica
  4. 2D search
  5. grid
  6. geohash
  7. 鄰格
  8. quadtree
  9. Hilbert curve
  10. N 和 m

收納盒一格塞太滿,就加一個十字隔板

① 先想像

收納盒一格最多放 4 樣東西。放第 5 樣時,在那格加十字隔板變成 4 小格。東西多的地方隔得很細,空的地方還是一大格。

你猜猜看:一格最多 100 家,全世界 2 億家店。最小的格子大約有幾個?

③ 這叫做 quadtree、leaf

quadtree(四分樹):太擠就切四塊、一路往下切的目錄。leaf(葉子):最小、沒再切的那一格。

④ 跟這章的關係

原書 Option 4。格子大小跟著店的密度變;代價是要在記憶體裡先把這棵樹建好。

② 動手玩:一格最多 4 家

0店1最小格(leaf)0切了幾層

原書 Step 2Option 4:Quadtree · Figure 13、14

Quadtree:一格超過 100 家就切成四格

這一步要解決的問題格子能不能跟著店的多寡,自己變細?

📖 原書 Figure 13Quadtree(依原書內容重繪;m = million 家商家,不是公尺;右邊四格加總 30m,推定是 NE 再切)

📖 原書 Quadtree 把二維空間遞迴切成四個象限,直到格子內容符合某個條件,例如「一格不超過 100 家」。100 是任意的,依業務需求決定。

📖 原書 重點:quadtree 是記憶體裡的資料結構,不是資料庫。它跑在每一台 LBS 上,server 啟動時建好。根節點是整張世界地圖,假設世界上有 2 億家商家。

public void buildQuadtree(TreeNode node) {
 if (countNumberOfBusinessesInCurrentGrid(node) > 100) {
 node.subdivide();
 for (TreeNode child : node.getChildren()) {
 buildQuadtree(child);
 }
 }
}

下一頁可以自己加點、看它怎麼切。

白話:記憶體(memory)=電腦手邊的工作桌,快,但關機就清空;資料庫存在硬碟上。TreeNode=樹上的一格;subdivide=切成四格。

動手玩Quadtree 自己長出來

點一下加一家店:格子太擠就自動切四塊

這一步要解決的問題照原書 buildQuadtree 的規則,親手看樹怎麼長。

0商家1葉節點0內部節點0樹高

原書上限是 100,這裡用 4 才看得出來。市中心格子細、郊區格子大,這就是原書說的「依人口密度動態調整格子大小」。

注意「內部節點 = (葉節點 − 1) ÷ 3」永遠成立:每切一次,葉子少 1 多 4(淨 +3),內部節點 +1。所以原書說內部節點大約是葉節點的 1/3(下一頁)。

原書 Step 2Quadtree 的記憶體與建樹時間 · Table 6、7

2 億家店的 quadtree,只要大約 1.71 GB

這一步要解決的問題這棵樹要佔多少記憶體?一台機器放得下嗎?

📖 原書 Table 6Leaf node
NameSize
左上、右下座標(識別格子)32 bytes(8 bytes × 4)
格子內的 business ID 清單8 bytes per ID × 100(一格最多 100 家)
Total832 bytes
📖 原書 Table 7Internal node
NameSize
左上、右下座標(識別格子)32 bytes(8 bytes × 4)
指向 4 個子節點的指標32 bytes(8 bytes × 4)
Total64 bytes

📖 原書 建樹依格子內的商家數,但這個數字不用存在節點裡,可以從資料庫的紀錄推出來。

動手算(預設就是原書的數字)

📖 原書 面試不用算這麼細,重點是:quadtree index 不太佔記憶體,一台 server 就放得下。但不代表只用一台:依讀取量,一台的 CPU 或網路頻寬可能不夠,就要把讀取分到多台 quadtree server。

📖 原書 建樹時間:O((N/100) lg(N/100)),2 億家要幾分鐘。查詢:從 root 往下走到起點所在的葉節點;那格有 100 家就回傳,否則從鄰格補,補到夠為止。

原書 Step 2Operational considerations · Real-world example · Figure 15

Quadtree 上線之後的麻煩:啟動要幾分鐘、更新要上鎖

這一步要解決的問題樹放在每台 LBS 的記憶體裡,上線後會遇到什麼麻煩?

📖 原書 啟動時間

  • 2 億家的 quadtree 在 server 啟動時要建幾分鐘,建樹期間不能接流量
  • 新版本要一次只部署一小批 server,避免一大塊 cluster 同時下線造成 brownout(服務沒全掛,但變慢、部分失效)
  • 也可以用 blue/green deployment(新舊兩組機器並行、一次切過去),但整批新 server 同時從資料庫抓 2 億筆,會對系統造成很大壓力;做得到,但設計變複雜,面試要提

📖 原書 商家增減時怎麼更新

  • 最簡單:分批逐步重建整個 cluster 的 quadtree;部分 server 短時間回傳舊資料,依需求通常可接受
  • 再加上「隔天生效」的商業協議,可以用夜間 job 更新 cache;潛在問題是大量 key 同時失效,cache server 負載很重
  • 也可以即時更新,但多執行緒存取要上鎖,實作會大幅變複雜
📖 原書 Figure 15Real-world example of a quadtree:Yext 提供的丹佛附近 quadtree(依原書內容重繪;城市位置與格子為示意)

📖 原書 密集區要小而細的格子,稀疏區用大格子。丹佛、Aurora 一帶格子細,往東的 Watkins、Strasburg、Byers 格子很大。

延伸基礎第 9 階 · Hilbert curve懂的人可以跳過

  1. 經緯度
  2. index
  3. read replica
  4. 2D search
  5. grid
  6. geohash
  7. 鄰格
  8. quadtree
  9. Hilbert curve
  10. N 和 m

一條蛇一筆畫走完棋盤:編號近,位置就近

① 先想像

要把 4 × 4 的棋盤排成一列編號。最直覺是像讀書:一行讀完換下一行。另一種是讓一條蛇一筆畫走完 16 格,不跳格。

你猜猜看:像讀書一樣編號,第一行 0–3、第二行 4–7。3 號和 4 號在棋盤上挨在一起嗎?

③ 這叫做 Hilbert curve

space-filling curve:走遍每一格、一筆畫完的曲線。Hilbert curve 是其中一種:編號相近,位置通常也相近。

④ 跟這章的關係

Google S2 用它把地球上的格子排成一條線,再用一般的一維 index 查(原書 Option 5)。

② 動手玩:兩種編號法,點一格看鄰居

—編號差 1 的兩格,最遠隔幾步

點任一格:編號前後 2 號的格子會亮起來。

原書 Step 2Option 5:Google S2 · Figure 16、17

Google S2:用 Hilbert 曲線把球面攤成一條線

這一步要解決的問題能不能把整個球面,直接排成一條線來查?

📖 原書 Figure 16Hilbert curve:曲線上相近的點,在一維上也相近(依原書內容重繪)
點左邊任一格,看它落在一維的哪裡

📖 原書 S2 和 quadtree 一樣是記憶體內的方案。它依 Hilbert curve(一種 space-filling curve)把球面映射成一維 index。重要特性:曲線上相近的兩點,在一維空間也相近;一維搜尋比二維有效率得多。

📖 原書 S2 很複雜,面試不用解釋內部;但 Google、Tinder 都在用,所以介紹兩個優點:

  • Geofencing:能用不同層級的格子蓋住任意區域。維基百科:geofence 是真實地理區域的虛擬邊界,可以動態產生(某點周圍的半徑),也可以是預先定義的邊界(學區、社區)。可以對離開區域的使用者發通知,比單純回傳附近商家功能更豐富
  • Region Cover 演算法:不像 geohash 固定一個精度,S2 可以指定 min level、max level、max cells,格子大小有彈性,結果更細緻

原書 Step 2Recommendation · Table 8 · Geohash vs quadtree

誰用哪一種?面試建議 geohash 或 quadtree

這一步要解決的問題這麼多種 index,面試該選哪一個?

📖 原書 Table 8Different types of geo indexes
Geo IndexCompanies
GeohashBing map、Redis、MongoDB、Lyft
QuadtreeYext
Both Geohash and QuadtreeElasticsearch
S2Google Maps、Tinder

📖 原書 面試建議選 geohash 或 quadtree,因為 S2 很難在面試裡講清楚。

📅 2026 補充 Elasticsearch 新版的 geo_point 用 BKD tree 建索引,查詢用 geo_distance;Redis 的 GEO 指令(GEOADD、GEOSEARCH)底層是把 52-bit geohash 當 sorted set 的 score。原書沒提的 Uber H3 用六角形格子,也很常見。

📖 原書 Geohash

  • ✓ 好用好實作,不用建樹
  • ✓ 支援「指定半徑內」的查詢
  • ✗ 精度固定,格子大小就固定,不能依人口密度調整,要更複雜的邏輯
  • ✓ 更新 index 很簡單:刪掉那一列(geohash, business_id)就好(Figure 18)

📖 原書 Quadtree

  • ✗ 稍難實作,要建樹
  • ✓ 支援 k-nearest:車快沒油,只要最近的 k 個加油站,不管多遠;切格子依 k 走,會自動調整範圍到湊滿 k 個
  • ✓ 能依人口密度調整格子(Figure 15)
  • ✗ 更新比較複雜:從 root 走到 leaf,O(log n);多執行緒要上鎖;重新平衡也複雜(葉子滿了),可能的解法是 over-allocate ranges(Figure 19)

原書 Step 2更新 index · Figure 18、19

刪一家店:geohash 刪一列,quadtree 要從根走到葉

這一步要解決的問題商家新增、刪除時,兩種 index 各要做多少事?

📖 原書 Figure 18Remove a business(依原書內容重繪)
DELETE FROM geospatial_index
WHERE geohash = '9q8zn' AND business_id = 8;

SQL 是依原書文字寫的示意:「從對應 geohash 與 business_id 的列刪除即可」。

📖 原書 Figure 19Update quadtree:刪掉 ID = 2,要從 root 一路走到 leaf(依原書內容重繪)

白話:root=樹的最上層(整張地圖);O(log n)=資料變 2 倍,只多走一層;上鎖=改的時候不讓別人同時改(Vol.1 第 1 章第 44 頁)。

原書 Step 3Scale the database · Table 9、10、11

geo index 表怎麼存:一格一列,還是一店一列?

這一步要解決的問題資料變多時,兩張表各怎麼存、怎麼擴展?

📖 原書 Business table:資料可能放不進一台,適合 shard。最簡單是依 business ID shard:負載平均、維運簡單。

📖 原書 Geospatial index table:geohash 和 quadtree 都很常用,因為 geohash 簡單,以它為例。兩種存法:

白話:shard=把一個大資料庫依規則切成幾台(Vol.1 第 1 章第 34 頁);JSON array=一格裡塞一整串 ID;compound key=兩個欄位合起來當主鍵。

geospatial_index
geohash
list_of_business_ids
📖 原書 Table 9Option 1:list_of_business_ids 是 JSON array(原書以圖片呈現,依原書內容重繪)
geospatial_index
geohash
business_id
📖 原書 Table 10Option 2:business_id 是單一 ID(原書以圖片呈現,依原書內容重繪)
📖 原書 Table 11Sample rows of the geospatial index table(Option 2)
geohashbusiness_id
32feac343
32feac347
f3lcad112
f3lcad113

📖 原書 推薦 Option 2

  • Option 1 要更新一家店:先拿整個 array、掃過一遍找到它;新增時也要掃整個 array 確認沒重複;還要鎖住那一列防止同時更新,邊界情況很多
  • Option 2 用 (geohash, business_id) 當 compound key,新增和刪除都很簡單,什麼都不用鎖

原書 Table 11 的 f3lcad 含字母 l,嚴格說 geohash 的 base32 不用 a、i、l、o,這裡照原書保留。

原書 Step 3Scale the geospatial index

原書自己說:先別急著 shard,加 read replica 就好

這一步要解決的問題讀取量太大時,該多印幾本影本,還是把資料切開?

📖 原書 常見錯誤:沒看實際資料量就跳到 sharding。這裡 geo index 的完整資料不大(quadtree 只要 1.71 GB,geohash index 的儲存需求差不多),整個放得進一台現代資料庫的 working set。

📖 原書 但依讀取量,一台的 CPU 或網路頻寬可能不夠,就要分散讀取負載。兩種方法:加 read replica,或 shard。

📖 原書 很多工程師面試愛講 sharding,但 shard geohash 表很複雜,例如 sharding 邏輯要寫進應用層。有時 shard 是唯一選擇;但這裡全部放得進 working set,沒有強烈的技術理由 shard。所以推薦用 一系列 read replica,開發、維護都簡單得多。

這頁原書和 Triton 是同一國的。Triton 的版本更直接:「如果是小型系統,單純 scale up 便算了」(第 49 頁)。

原書 Step 3Caching · Cache key

要不要 cache?先問自己;要的話,key 用 geohash

這一步要解決的問題要不要加 cache?要的話,用什麼當 key?

📖 原書 先問:真的需要 cache 嗎?

  • 讀為主、資料集相對小,放得進任何一台現代資料庫的 working set,query 不是 I/O bound,應該跑得幾乎和記憶體 cache 一樣快
  • 讀取真的是瓶頸,可以加 read replica 提高讀取吞吐量
  • 跟面試官談 cache 要小心:要仔細做 benchmark 和成本分析;確認 cache 符合業務需求,才談 cache 策略

📖 原書 Cache key:經緯度不是好 key

  • 手機回報的座標不準,只是最佳估計;不動,每次拿到的也略有不同
  • 使用者會移動,座標跟著小幅變化,對多數 App 沒有意義
  • 理想:位置小幅變動仍對應同一個 key。geohash/quadtree 剛好做到:同一格的商家都對應同一個 geohash

動手試:手機一直回報不太一樣的座標

白話:cache=手邊的小抄,正本在資料庫(Vol.1 第 1 章第 18 頁);key=查小抄用的標籤;working set=常用的資料整個放得進記憶體;I/O bound=慢在讀硬碟;benchmark=實際量測。

回報的座標key = lat,lonkey = geohash6
0%經緯度當 key 的命中率0%geohash 當 key 的命中率

原書 Step 3Types of data to cache · Table 12

兩種 cache:「這格有哪些店」和「這家店長怎樣」

這一步要解決的問題cache 裡要放哪兩種東西?要多少記憶體?

📖 原書 Table 12Key-value pairs in cache
KeyValue
geohashList of business IDs in the grid
business_idBusiness object

📖 原書 商家資料相對穩定,預先算好每個 geohash 的 business ID 清單,放進 Redis 這類 key-value store。先用 SQL 拿清單,cache miss 才寫進 Redis:

SELECT business_id FROM geohash_index WHERE geohash LIKE `{:geohash}%`

public List<String> getNearbyBusinessIds(String geohash) {
 String cacheKey = hash(geohash);
 List<string> listOfBusinessIds = Redis.get(cacheKey);
 if (listOfBusinessIDs == null) {
 listOfBusinessIds = Run the select SQL query above;
 Cache.set(cacheKey, listOfBusinessIds, "1d");
 }
 return listOfBusinessIds;
}

📖 原書 商家新增、編輯、刪除時,更新資料庫並讓 cache 失效。這類操作量小,geohash 做法又不用上鎖,所以好處理。

📖 原書 使用者可選 500 m、1 km、2 km、5 km 四種半徑,原書寫「分別對應 geohash 長度 4、5、5、6」,所以在 Redis 快取三種精度:geohash_4、geohash_5、geohash_6。

⚠ 原書前後不一 依 Table 5,500 m → 6、5 km → 4,順序剛好反過來;這裡兩處都照原書列出,以 Table 5 為準。

📖 原書 記憶體

values:8 bytes × 200 million × 3 precisions ≈ 5 GB
keys:可忽略
總共 ≈ 5 GB

一台現代 Redis 就夠,但為了高可用、降低跨洲延遲,把 Redis cluster 部署到全球,每地放同一份 cache。最終架構裡叫它 “Geohash”。

白話:key-value store=用標籤直接拿值的倉庫;TTL=小抄多久過期,"1d" 是一天(Vol.1 第 8 章第 39 頁)。

📖 原書 第二種:key = business_id、value = 商家物件(名稱、地址、圖片 URL 等),很直接,叫 “Business info”。

原書 Step 3Region and availability zones · Figure 20 · Follow-up:篩選

把 LBS 放到離使用者近的地方

這一步要解決的問題全世界的使用者,怎麼讓每個人都連得快、又符合當地法規?

📖 原書 Figure 20Deploy LBS closer to the user(依原書內容重繪;大陸輪廓為簡化示意)

📖 原書 把 LBS 部署到多個 region 和 availability zone,好處:

  • 使用者在物理上更近:美西連美西的資料中心,歐洲連歐洲的
  • 依人口分散流量:日本、韓國人口密度高,可以獨立成 region,甚至在多個 AZ 部署 LBS 分散負載
  • 隱私法規:有些國家要求使用者資料在當地使用與儲存,就在那國設 region,用 DNS routing 把該國請求限制在那個 region

白話:region=一個地區的機房群;AZ(availability zone)=同一地區裡互相獨立的機房;DNS routing=依你在哪裡,把網址指到不同機房;hydrate=拿 ID 換回完整資料。多機房的基礎:Vol.1 第 1 章第 28 頁。

📖 原書 Follow-up:只要「現在有營業」或「只要餐廳」

應徵者:用 geohash 或 quadtree 把世界切成小格後,搜尋結果的商家數相對少。所以可以先拿 business ID,hydrate 成商家物件,再依營業時間或類型過濾。前提是營業時間和類型存在 business table 裡。

原書 Step 3Final design diagram · Figure 21

最終設計:找 500 公尺內的餐廳,一步一步走

這一步要解決的問題把前面全部串起來:一個搜尋從頭到尾怎麼走?

📖 原書 Figure 21Design diagram(依原書內容重繪;alt 把 LBS 寫成 Load Balancing Service,依內文是 location-based service;Business Service 先查 Business info cache 是依內文補畫的虛線)

📖 原書 Get nearby businesses

  1. 在 Yelp 找 500 m 內的餐廳。client 送位置(latitude = 37.776720、longitude = -122.416730)和半徑 500 m 給 load balancer
  2. Load balancer 把 request 轉給 LBS
  3. LBS 依位置和半徑找對應的 geohash 長度:查 Table 5,500 m → 長度 6
  4. LBS 算出鄰格加進清單:list_of_geohashes = [my_geohash, neighbor1_geohash, …, neighbor8_geohash]
  5. 對清單裡每個 geohash 呼叫 “Geohash” Redis 拿 business IDs,可以並行以降低延遲
  6. 用 ID 清單到 “Business info” Redis 拿完整商家資料,算距離、排序、回傳給 client

📖 原書 看、改、增、刪商家:這些 API 和 LBS 分開。看詳情時 business service 先查 “Business info” cache,有就回傳;沒有就從資料庫 cluster 拿,再存進 cache。因為「隔天生效」,cache 由夜間 job 更新。

原書 Step 4Wrap up · Chapter summary

原書的收尾:一個典型的 LBS,靠 geospatial index

這一步要解決的問題原書最後怎麼收尾?哪些是這章的骨架?

📖 原書 Chapter Summary本章心智圖(依原書內容重繪;alt 把 region、filter、final design 放在 Step 4,依內文它們屬於 Step 3 deep dive)

📖 原書 討論過的索引:二維搜尋、均勻網格、geohash、quadtree、Google S2。geohash、quadtree、S2 都被不同科技公司廣泛使用,原書選 geohash 當例子示範 geospatial index 怎麼運作。

📖 原書 Deep dive 談了:為什麼 cache 能降低延遲、該 cache 什麼、怎麼用 cache 快速拿附近商家;怎麼用 replication 和 sharding 擴展資料庫。

📖 原書 最後把 LBS 部署到不同 region 和 AZ:提高可用性、讓使用者物理上更近、更符合當地隱私法規。

原書最後一句:恭喜你看到這裡,給自己一個讚。

到這裡你已經會了小結 3 / 4

  1. 經緯度
  2. index
  3. read replica
  4. 2D search
  5. grid
  6. geohash
  7. 鄰格
  8. quadtree
  9. Hilbert curve
  10. N 和 m

到這裡你已經會了:原書的整套設計

下一階要解決的問題

原書一開始就假設有 2 億家店。如果你的系統只有 1 萬家呢?還需要這整套嗎?

延伸基礎第 10 階 · N 和 m懂的人可以跳過

  1. 經緯度
  2. index
  3. read replica
  4. 2D search
  5. grid
  6. geohash
  7. 鄰格
  8. quadtree
  9. Hilbert curve
  10. N 和 m

巷口只有 6 家飲料店,你會打開地圖 App 嗎?

① 先想像

巷口 6 家飲料店,走出去一家一家看就好。全台灣 2 萬家,才需要地圖 App。先數有幾家,再決定要不要買地圖。

你猜猜看:1 萬家店、每秒 50 人查詢,每人都把 1 萬家量一遍。每秒要量幾次距離?

③ 這叫做 N、m、brute force

N:有幾家店(資料多大)。m:每秒查幾次。brute force(暴力解):不用技巧,一家一家量。

④ 跟這章的關係

Triton:先算 N × m,再決定要不要建 geohash、quadtree。N 小,兩層 for-loop 就夠。

② 動手玩:三種規模,暴力解要量幾次?

50 萬每秒要量幾次(N × m)0.5%一顆 CPU 的負擔(示意)

Triton 怎麼看先知道 N

「Bruteforce algorithm(暴力解法)也是算法的一種啊!」

背景:有人在 Python 版發問「我有 10000 個點,我想找出每一個點的最近鄰居」,一堆人回答 R-tree、Quadtree……

「如果才 10000 個點,單純 2 層 for-loop,O(n^2) solution 吧。現實跑起來應該少於1秒。如果 n > 1M 則肯定不能暴力解」🗣️ Triton 本人說 064-introToAlgorithm.pdf.md · 「我的回應」

「Bruteforce algorithm(暴力解法)也是算法的一種啊!特別在 n 很小的時間。Engineering 是在有限資源(開發時間/server cost/效能)下找出最可行解法」🗣️ Triton 本人說 064 · 「我想說……」

「N 很小時,O(n^2)/O(n^3) 也好,1ms 和 0.1ms 對用戶感覺是沒差別的。越深的 algorithm,很多時其 implementation 就越複雜,這代表:更高的開發時間、更多可以犯錯的細節、更多的 source code,增加維護困難度」🗣️ Triton 本人說 064 · 「我繼續想說……」

你猜猜看:1 萬個點,要找每一點的最近鄰居。網友都推 R-tree、quadtree。如果只用兩層 for-loop 一個一個比,要跑多久?

🗣️ Triton 羅馬不是一天建成的:好的開發者應該

  1. 先正確地理解問題
  2. 了解 N(像是 QPS / user count / data size)
  3. 給 PM 說明不同解法的開發時間和其預測界限,找出平衡的方案
  4. 開發後,清楚寫下你用了那種解法
  5. 管理系統中的 tech debt,在 N 變大時換上更好解法

064 · 「羅馬不是一天建成的」(原文「平衝」應為「平衡」)

Triton 怎麼看 · 動手算暴力解 vs 索引:O(m·n) vs O(m·log n)

你的 N 和 m 是多少?算完再決定要不要建索引

你猜猜看:原書 2 億家店、每秒 5,000 次搜尋。如果每次搜尋都把 2 億家量一遍,每秒要量幾次?

「反正你只用解一次,暴力解法跑完後把結果存起來就好」🗣️ 064 · 正確地理解問題

「對一個任意點 x,我想知道在 10000 個點中,誰跟 x 最接近。暴力解法:O(m*n),m=你 query 的次數;Quadtree 解法:O(m * log n)。因為 m 可以很大,所以暴力解法不一定能接受」🗣️ 064

🔭 計算假設 用 Triton 自己的數字反推:1 萬點 O(n²) = 1 億次距離計算「少於 1 秒」,所以這裡以一顆 core 每秒約 1 億次當示意。索引的成本只算 log₂ N,忽略常數,真實數字請壓測。判斷門檻用 Triton 說的「n > 1M 則肯定不能暴力解」。

Triton 怎麼看同意:geohash + 8 鄰格

✅ 同意原書 自己這格加 8 個鄰格,找不到就縮短一碼

你猜猜看:原書是「自己這格 + 8 個鄰格,店不夠就把 geohash 縮短一碼」。Triton 會怎麼評?

「你可以想像:每一個 geohash 都是一個長方形。在一個長方形內的點,其最近鄰居一定是……在同一長方形內,或在鄰近八個長方形內。對於一個 geohash,要找出鄰近8個長方形的所需時間是:O(1),真的是 O(1)」🗣️ Triton 本人說 064 · Geohash(續)

「簡單來說:這是把地球坐標轉成 string 的 encoding。4byte geohash 誤差是 20km、5byte geohash 誤差是 2.4km、6byte geohash 誤差是 610m」🗣️ Triton 本人說 064 · Geohash

Triton 的「誤差」大約是原書 Table 4 格子邊長的一半(39.1 × 19.5 km → 20 km;4.9 km → 2.4 km;1.2 km × 609 m → 610 m),兩邊數字一致。

🗣️ Triton 具體解法(簡化版)

  1. 「把每一個點,建立從 1byte 到 i byte 的 geohash 的 column,然後把這些資料放進 elastic search」
  2. 「先建立 i byte 的 geohash(還有其相鄰8格的 geohash)」
  3. 「把這 9 個 geohash 丟到 ES 搜尋」
  4. 「如果有結果返回,則一個一個對比,最近的點就是答案」
  5. 「否則用 i-1 byte 的 geohash 從來~」

064 · 具體解法

和原書對照

第 4 步是原書 Figure 2 之後的「算鄰格、逐格撈、算距離排序」(第 40 頁);第 5 步就是原書的「拿掉最後一碼擴大搜尋」(第 24 頁)。差別只在存哪裡:原書是自建 geo index 表 + Redis,Triton 是每個長度一個欄位,交給 ES 的 index。

Triton 怎麼看情境差異:面試講原理,工作用現成的

原書在 LBS 裡自己建 quadtree;Triton:「以上的都不用自己來寫」

你猜猜看:原書讓每台 LBS 開機時,自己在記憶體裡建一棵 2 億家店的 quadtree。真的上線,最可能遇到什麼麻煩?

📖 原書 自建、自己維運

原書自己也說現實中公司會用 Redis Geohash 或 PostGIS,但面試要你解釋原理。於是 quadtree 版本是:每台 LBS 啟動時花幾分鐘建樹、期間不能接流量;更新要上鎖、重新平衡複雜(第 30 頁);geohash 版本是自建 geo index 表,再加一組 Redis “Geohash”。

🗣️ Triton 本人說 用現成的 index

「這是 quadtree 變種,所以其時間是 O(m log n)。因為其 fanout factor 很高,所以 tree height 很低。Geohash 有現有 library,不用自己來寫。能善用 elastic search/一般 RDBMS 的 indexing,不用自己建立和管理 quadtree」064 · 解法優點

「如果你用 postgresql,使用 postGIS 套件,以上的都不用自己來寫,有人替你寫好了」064 · 附 postgis.net 的 KNN 教學連結

Triton 怎麼看情境差異(續):能不能先在資料庫裡做?

越少模組越好:geo index 能不能就放在原本的資料庫裡?

這一頁要回答不自己建 quadtree,那要用什麼?要不要另外架一套 Elasticsearch?

🗣️ Triton 越少模組越好

「越少模組,便代表你需要監控和管理的模組便越少,代表你的團隊需要掌握的語言/技術便越少」「例子:是否使用 ElasticSearch?你需要 Tokenization 嗎?能不能先在 RDBMS 做 searching?」073 · lesson3

🔭 依 Triton 原則推論 放回這一章

原書已經選了 MySQL/primary-replica。如果改成 Postgres + PostGIS,geo index 就是同一個資料庫裡的一個 index:不用另一張自建表、不用每台 LBS 啟動建樹;「營業中」「只要餐廳」也能寫在同一個 WHERE 裡。064 推 ES,073 又問「能不能先在 RDBMS」,兩句合起來,第一步是 PostGIS。

📅 2026 補充 PostGIS 長什麼樣

CREATE INDEX ON business USING GIST (geog);
SELECT business_id FROM business
WHERE ST_DWithin(geog, ST_MakePoint(-122.41673, 37.77672)::geography, 500)
ORDER BY geog <-> ST_MakePoint(-122.41673, 37.77672)::geography
LIMIT 20;

ST_DWithin 用 GiST index 做半徑查詢;<-> 是 index 支援的 KNN 排序。

Triton 怎麼看同意:RDBMS、先 scale up、別急著 shard

✅ 同意原書 1.71 GB 的 index,一台資料庫就放得下

你猜猜看:2 億家店的 geo index 約 1.71 GB。Triton 會建議一開始就 shard 成好幾台嗎?

📖 原書 自己就說了

  • 讀為主的系統,MySQL 這類關聯式資料庫很合適(第 10 頁)
  • geo index 只有約 1.71 GB,放得進 working set,沒有強烈的技術理由 shard,用 read replica(第 36 頁)
  • geo index 表一店一列,不要塞 JSON array(第 35 頁)

🔭 依 Triton 原則推論

唯一的差別:原書在 business table 那段說「可能放不進一台,適合 shard」;照 Triton 的順序,先問 2 億筆商家到底多少 GB,scale up 到 20 core、200 GB RAM 還放不下,才輪到 shard。

「不能不見的data,我一定存到RDBMS」「用children table來存你的array data,別為了小事輕易違反3NF」「如果是小型系統,單純scale up便算了」🗣️ Triton 本人說 106-喵 data.md

「正常沒亂來的系統,在20core + 200GB RAM的暴力機器下,絕大部份都沒需要玩clustering」「如果到了scale up盡頭又不想走Hbase那些noSQL……我還不如走傳統的sharding路線」🗣️ Triton 本人說 106

「資料量不夠大 (<100GB) 就乖乖回去用 RDBMS 就好啦」🗣️ Triton 本人說 054-data-analysis.pdf.md · 前言(原文談資料分析)

「Auto-scaling是用來省錢的。一般用在 App. Server層,別用在 DB層。流量上升是慢慢的,不是爆發性的」🗣️ Triton 本人說 051-concurrency.pdf.md · Auto-scaling(對照原書「用餐時間自動加 LBS」:同意,LBS 是 stateless 的 AS 層)

Triton 怎麼看Cache:TTL 對了,夜間 job 要小心

原書設了 1 天 TTL ✅;但「大量 key 同時失效」要先想好

你猜猜看:原書用夜間 job 更新 cache。如果做法是「先全部清掉,等有人查再補」,清掉的那一刻會怎樣?

✅ 同意 一定要設 TTL

原書的程式碼 Cache.set(cacheKey, listOfBusinessIds, "1d")。

「沒設定合理的 TTL:有笨蛋會設 cache TTL = 一年,不設 TTL後果更嚴重,唉~這種瘋狂的 TTL,最終會讓 redis存太多過期資料,觸發 cache eviction」🗣️ Triton 本人說 087-redis-2019.pdf.md · caching 常犯錯誤

「正常人使用 Redis……用作 caching,資料同時存放於主資料庫」087 原書正是這樣用:資料庫是本體,Redis 是 cache。

📖 原書自己點出的問題 夜間 job 讓大量 key 同時失效

原書:用夜間 job 更新 cache,「潛在問題是大量 key 同時失效,cache server 負載很重」,但沒給解法。

「如果資料X的 QPS是 1000……如果主資料庫需要 80ms回傳資料X,那麼便有 80個 request進了主資料庫」🗣️ 087 · 「一般」的 caching 問題

🗣️ Triton 的進階做法 ① 從 Redis 拿 X,有就回傳 ② 拿到 X 的鎖 ③ 再從 Redis 拿一次,有就回傳 ④ 從主資料庫拿 ⑤ 放回 Redis ⑥ 回傳 087

🗣️ 預熱「土法煉鋼但是有效的做法:寫一個 crontab,在 cache miss前到主資料庫拿資料放到 redis」087

🔭 推論 放回這章:夜間 job 不要「先清空再等 miss」,而是直接把新清單寫過去(預熱),TTL 錯開;漏網的 miss 走「上鎖再檢查」。商家資料一天才變一次,也很適合放 LBS 本機的 local cache(051:snapshot 不會被改動,能放在 local cache)。

🗣️ Triton Redis cache 也要當 stateful 看

「如果單純用作caching的,那嚴格定義上算是stateless,不過,實務上當成stateful會比較安全(單純是cache-miss就超級可怕了)」017

Triton 補充Region、AZ 與 High Availability

多 region 是為了近和法規;HA 先用別人做好的

你猜猜看:原書把 Redis cache 部署到全球各地。如果某一區的 cache 突然全空,會怎樣?

「傳統上我們談High Availability,我們是指:1. 系統中沒有single point of failure 2. 如果single component掛掉,是不需要人類即時行動。」「有HA不代表系統完全零秒的Downtime, 有HA只代表有single component掛了後系統能自動短時間內回復。(一般來說「短時間」=數分鐘內)」🗣️ Triton 本人說 017-High Availability stateful component vs stateless component.md

「stateless component算是很簡單的,就單純有N個相同的node就好」「整個過程有數不清的地方可以出錯,請使用像AWS RDS multi-AZ這些別人建好的方案,而不要輕易自己」🗣️ Triton 本人說 017

🔭 依 Triton 原則推論 對照原書

  • 原書的 LBS、business service 都 stateless:多開幾台、heartbeat 判斷死活,就是 017 說的簡單那一半
  • 麻煩的是 stateful 的 primary DB 和 Redis。原書的圖只畫了 primary + replica,沒說 primary 掛了誰升級;照 017,交給 RDS multi-AZ 這類 managed 方案
  • 原書把 Redis cluster 部署到全球,是為了延遲和可用性;照 017,cache 也要當 stateful 看:一個 region 的 cache 全空,流量全打回資料庫
  • 原書第三個理由「隱私法規」是 Triton 材料沒談過的,照原書

017 這篇的背景是 Triton 批評 ByteByteGo 一篇談 HA 的貼文(「4 nines」、hot-hot),也就是本書作者那邊的內容;他批評的是那篇貼文,不是這一章。

到這裡你已經會了小結 4 / 4

  1. 經緯度
  2. index
  3. read replica
  4. 2D search
  5. grid
  6. geohash
  7. 鄰格
  8. quadtree
  9. Hilbert curve
  10. N 和 m

到這裡你已經會了:Triton 的那一個問題

10 階全部走完了

下一頁用一句話收尾;再下一頁是名詞小卡,給大家課後複習。

一句話記住

先數有幾家店、每秒查幾次;
小就暴力解,大就用 PostGIS,不要自己種樹。

原書對的地方

  • geohash + 8 鄰格解決邊界問題
  • 找不到就拿掉一碼擴大搜尋
  • geo index 一店一列、不用上鎖
  • 資料小,用 read replica 別 shard
  • 先問要不要 cache、TTL 設 1 天

情境差異

  • 原書假設 N = 2 億,所以一定要索引;你的 N 可能是 1 萬
  • 面試要講原理;上線用現成的 PostGIS / ES / Redis GEO
  • 自建 quadtree:啟動幾分鐘、更新要上鎖

Triton 的做法

  • 先寫下 N 和 m,算 O(m·n)
  • N < 1M、m 小:兩層 for-loop,寫進 tech debt
  • N 大:geohash 欄位放 ES 或 RDBMS index,或 PostGIS
  • 夜間更新 cache:預熱 + 上鎖再檢查

本章名詞小卡課後複習用 · 每個名詞一句白話

今天出現的名詞,一句話講完

latitude(緯度)南北方向的座標,赤道 0、北極 90
longitude(經度)東西方向的座標,格林威治 0、東西各到 180
proximity service、LBS給位置和半徑,找附近的店的服務
radius(半徑)以你為圓心,要找多遠;原書 0.5–20 km
DAU、QPS每天有幾個人用/每秒來幾個請求
APIApp 和後端約好的窗口,例如 GET /v1/search/nearby
index照某個欄位排好的目錄;只對那個欄位快
RDBMS關聯式資料庫(MySQL、PostgreSQL),一列一列的表
primary / read replica唯一能改的正本/只給人查的影本
replication delay影本比正本晚一點才跟上
load balancer帶位員,把請求分到不同的服務
stateless機器身上不記客人的事,壞了換一台就好

給工程師的重點出處與標籤

引述來源(materials/core)

Triton 本人的講義 / 文章

  • 064-introToAlgorithm.pdf.md — 本章主來源:1 萬點 O(n²) 少於 1 秒、n > 1M 不能暴力解、「Bruteforce algorithm 也是算法的一種」、了解 N、O(m*n) vs O(m log n)、geohash 長方形 + 8 鄰格 O(1)、1..i byte 欄位放 ES、i-1 重來、不用自建 quadtree、postGIS 套件
  • 073-lesson3.pdf.md — 越少模組越好;是否使用 ElasticSearch、能不能先在 RDBMS 做 searching
  • 106-喵 data.md — 不能不見的 data 存 RDBMS、children table 不違反 3NF、小型系統 scale up、20core + 200GB RAM、寧走傳統 sharding
  • 054-data-analysis.pdf.md — <100GB 用 RDBMS(原文談資料分析)
  • 051-concurrency.pdf.md — auto-scaling 用在 AS 層、別用在 DB 層;snapshot 可放 local cache
  • 087-redis-2019.pdf.md — 一定要設合理 TTL、cache stampede 上鎖再檢查、crontab 預熱、Redis 用作 cache 資料同時存主資料庫
  • 017-High Availability….md — HA = 無 SPOF + 自動數分鐘內恢復、stateless 簡單、用 RDS multi-AZ、Redis cache 當 stateful 看

沒有引用:061(Roy 的專案報告,用了 PostGIS 的 ST_DWithin,但標「僅供面試評估使用,請勿外傳」);187–195 的 AI 生成內容。

循序漸進(文組版)的頁面

學習地圖(第 3 頁);延伸基礎 10 階:經緯度(4)、index(9)、read replica(11)、2D search(14)、grid(16)、geohash(18)、鄰格(21)、quadtree(26)、Hilbert curve(31)、N 和 m(43);小結(13、25、42、52);名詞小卡(54)。Triton 段:44–51(PostGIS / 少模組在 48)。

原書對照

Alex Xu & Sahn Lam, System Design Interview Vol.2 Ch.1。開場與 Figure 1(第 5 頁)、Step 1 需求(6)、估算(7)、API 與 Table 1–2(8)、Data model 與 Table 3(10)、High-level design 與 Figure 2(12)、Option 1 與 Figure 3–4(15)、索引分類、Option 2 與 Figure 5–6(17)、Geohash 與 Figure 7–8(19)、Table 4–5(20)、互動地圖(22)、Boundary issues 與 Figure 9–11(23)、Not enough businesses 與 Figure 12(24)、Quadtree 與 Figure 13–14(27–28)、Table 6–7 與記憶體(29)、Operational 與 Figure 15(30)、S2 與 Figure 16–17(32)、Table 8 與比較(33)、Figure 18–19(34)、Scale the database 與 Table 9–11(35–36)、Caching 與 Table 12(37–38)、Region / AZ、Figure 20 與篩選(39)、Final design 與 Figure 21(40)、Wrap up 與心智圖(41)。21 張圖、Table 3/9/10 的圖片與心智圖都依原書圖說和 alt 重繪,不是原圖。

一個可以直接問自己的問題

你的系統有幾個點要搜?每秒搜幾次?兩個數字乘起來,是一億、還是一兆?

← → 翻頁 · S 講者備註 · D 深/淺色
1 / 1目錄