演算法筆記系列 — QuadTree 與 GeoHash

created by AI

關於地圖相關的理論，不論是工作還是個人專案，過去一直沒有機會深入研究，前陣子剛好在了解什麼是 QuadTree 與 GeoHash，趁機會也把這些內容與核心邏輯記錄下來。

什麼時候會需要它們？

會討論到 QuadTree 與 GeoHash，主要是在開發 LBS (Location Based Service) 應用的時候，像是 Uber、Foodpanda，甚至是前陣子很熱門的 Pokémon GO，它們面臨的核心挑戰都是：「如何在 2D 平面上，從數百萬個點中快速找出附近的物體？」

想像一下，如果我們把資料都一筆一筆根據經緯度存放在資料庫中，然後用 SQL 的 WHERE lat BETWEEN ... AND lon BETWEEN ... 來根據範圍找到否些資料，當資料量很大的時候，這種範圍查詢的做法會導致資料庫全表掃描，絕對是行不通的，因此 QuadTree 與 GeoHash 正是為了將二維空間轉換成可快速檢索結構而生的技術

created by AI

QuadTree

QuadTree 的核心原理是「空間剪枝 (Spatial Pruning)」，它不只是把地圖切碎，而是建立了一套階層式的過濾機制。

核心機制：遞迴切割

想像你有一張正方形的地圖，當這張地圖裡的物件太多的時候（例如超過你設定的 Bucket Size = 10），我們就把它切成 4 個等大的小正方形：NW (西北)、NE (東北)、SW (西南)、SE (東南)。

如果切分後的小正方形內物件還是超過 10 個，就遞迴地再切成四份，直到符合條件為止。這對應到資料結構中，就是一顆根節點涵蓋全世界、只有葉子節點 (Leaf) 儲存實際資料點的四元樹。

created by AI

節點結構

每個 QuadTree 的節點都代表一個矩形範圍，一個節點通常包含：

• 邊界 (Boundary)：中心點 (x, y) 與半寬高。
• 容量 (Capacity)：該格子最多能塞幾個點。
• 資料 (Points)：目前儲存的物件清單。
• 子節點 (Children)：指向四個象限的指標。

特性：適應性

QuadTree 對空間利用極致優化，它不會浪費記憶體去切割空曠的地方。

• 在台北 101（人口密集），樹會切得非常深，格子變得很精細。
• 在太平洋中央（沒人），樹可能只切一層，格子超巨大。

為什麼搜尋快？

當你要找「某圓形範圍內的所有點」時，QuadTree 會執行以下邏輯：

1. 檢查相交：如果目前的「格子範圍」跟你的「搜尋圓形」完全沒交集，直接整顆樹砍掉，不進去搜。
2. 遞迴向下：如果有交集，就進去四個子節點重複步驟 1。
3. 收集結果：直到葉子節點，才把裡面的資料拿出來比對距離。

GeoHash

GeoHash 的核心原理是「空間填充曲線 (Space-filling Curve)」，它不是利用樹狀結構來層層分發，而是透過降維打擊 (2D to 1D) 將二維的 (Lat, Lon) 座標壓縮成一維的字串。

核心特性：前綴相似性

想像你把地球這張大地圖不斷地切格子，每一格都有一個專屬的名字。當你的座標落在某個格子時，就會被轉換成一串 Base32 編碼。

• 台灣 -> ws
• 台北 -> wsq
• 台北 101 -> wsqqpz

這種將空間轉為字串的做法，讓搜尋變成了極其簡單的「前綴比對」，它的特性是：字串的前綴 (Prefix) 越像，代表兩者在物理距離上越接近。

編碼原理

它是如何把經緯度變成字串的？主要分為三個步驟：

1. 二分法逼近 (Binary Partitioning)：將緯度 (-90, 90) 與經度 (-180, 180) 不斷二分，如果座標在右/上半部記為 1，反之記為 0。
2. 位元交叉 (Interleaving)：將得到的經、緯度二進位碼像編織一樣交叉組合（例如：經-緯-經-緯…），這樣做是為了確保編碼的每一位字元都能同時兼顧橫向與縱向的縮小。
3. Base32 編碼：將交叉後的二進位碼，每 5 個 bits 轉成一個字元（使用 0–9 與 b-z，去掉了容易混淆的 a, i, l, o）。

created by AI

而 GeoHash 的字串長度也直接決定了格子的精細程度。

為什麼搜尋快？

在實作 LBS 系統時，GeoHash 展現了極高的效能優勢：

1. 資料庫友善：你可以直接把 GeoHash 存成 String 並建立索引。搜尋附近 1 公里的目標，只需要下 WHERE hash LIKE 'wsqqpz%'。
2. 更新成本低：相對於 QuadTree 需要處理繁瑣的樹重組，GeoHash 只是字串的更新。對於每秒都在移動的物體（如司機），這能大幅減輕伺服器負擔。

兩者的限制與缺陷

在理解了 QuadTree 與 GeoHash後，其實他們在 LBS 的應用場景下各有不同適用的情況。

QuadTree 的 Re-balancing

這也是為什麼像 Uber 這種高頻動態場景不選 QuadTree 的主因。

• 痛點：當 10 萬個司機每 3 秒更新一次座標，司機從 A 格移到 B 格，會頻繁觸發 A 格的 Merge 與 B 格的 Split。
• 後果：結構不斷變動導致嚴重的 Lock Contention，為了保證執行緒安全，必須鎖住節點甚至父節點，導致伺服器 CPU 飆高。

以下這張圖，描述了當地圖上的點不斷移動，導致 Tree Lock Contention 的實際情況：

created by AI

GeoHash 的邊界斷層

GeoHash 存在一個數學上的天生缺陷：邊界斷層。

有時候兩個人明明只隔著 1 公尺，但剛好跨過了網格的邊界，這會導致兩人的 GeoHash 字串完全不同（例如你是 wx4g，他是 wx4h）。如果你只搜尋 wx4g 開頭的人，就會漏掉就在你旁邊的朋友。

解法：K-Ring (9-Neighbor Search) 為了不漏掉邊緣目標，我們搜尋時永遠不只搜尋自己這格，而是連同周圍的 8 個鄰居格子一起搜尋（總共搜 9 格），再透過距離公式篩選出精確的目標。

實際應用：Pokémon GO 系統設計題目

那我們來看看，實際應用在開發上的時候，我們該怎麼選擇這兩種模式。假設我們要設計 Pokémon GO 的後端，面對兩類資料：

1. 補給站 (PokéStops)：500 萬個，位置固定，分佈極不均勻（城市密、沙漠稀）。
2. 玩家 (Players)：100 萬人，每秒都在移動。

這兩類資料，根據我們理解 QuadTree 與 GeoHash 後，選擇的策略：

• 補給站使用 QuadTree：因為地點不變，且靜態資料不需擔心重組，且對疏密不均的空間節約效果極佳。
• 玩家使用 GeoHash：GeoHash 適用高頻更新，如果在這情況下選則使用 QuadTree，萬一 1 萬個玩家同時往某個地點集中，該節點會因不斷 Split 而觸發 Lock Contention，導致伺服器卡頓、遊戲崩潰。

總結一下，QuadTree 是一種 「空間索引」，它利用樹狀結構不斷分發請求，適合處理「不均勻」的資料分佈（如：哪裡有加油站）與複雜的範圍查詢。而 GeoHash 是一種 「空間編碼」，它將 2D 座標轉為 1D 索引，適合利用 Redis 或資料庫的 B-Tree 索引進行「高頻更新」的查詢（如：外送員在哪）。

最後有個小小的 demo site，把 QuadTree 與 GeoHash 視覺化的呈現出來，有興趣可以參考：

QuadTree ：

https://sean1093.github.io/AlgoVisuals/demo/quadtree

GeoHash：

https://sean1093.github.io/AlgoVisuals/demo/geohash

更多演算法與資料結構文章：

[embed]基礎演算法與資料結構學習筆記 基礎演算法與資料結構，常常是工作後沒在用就很容易忘記，但面試又很愛考，每次要準備面試前都要重新搜集資料複習，這次就趁有時間時候，一邊複習一邊紀錄一下這次基礎演算法與資料結構的學習筆記。medium.com

[embed]

如果你覺得這篇文章對你有幫助，歡迎買杯咖啡贊助 ☕️ 謝謝