地理空間索引 (Geospatial Index)
為什麼一般索引不行
地理資料是 二維（經度 + 緯度）或多維，一般 B-Tree / Hash 索引只處理一維 key。
誤用一維 B-Tree 的兩個失敗路徑
以「找出 5 英里內的餐廳」為例：
CREATE INDEX idx_lat ON restaurants(latitude);
CREATE INDEX idx_lng ON restaurants(longitude);
| 方案 | 問題 |
|---|---|
| 只用緯度索引 | 找到一條「橫跨全球的長條帶」，再逐筆比對經度 → 經度索引幾乎沒用 |
| 兩個索引做交集（bitmap AND） | 形成一個 矩形 搜尋區域，比真正要的 圓形半徑 大得多；還要再過濾距離 |
根本問題：2D 空間搜尋不能只靠兩個獨立的 1D 索引。
四種主流技術
1. Geohash（最常用）
把地球表面切成網格，用 Base32 字串編碼位置，越長越精確。
"dr" → 整個舊金山
"dr5" → 縮小到任務區 (Mission District)
"dr5ru" → 某個街區
關鍵巧妙：相鄰的地點通常有相同字串前綴。
→ 把 2D 問題轉換成「字串前綴比對」→ 直接用既有 B-Tree 前綴索引。
CREATE INDEX idx_geohash ON restaurants(geohash);
-- 找 "dr5ru" 附近的餐廳：B-Tree 範圍掃描
SELECT * FROM restaurants
WHERE geohash BETWEEN 'dr5ru' AND 'dr5ru~';
| 優點 | 缺點 |
|---|---|
| 直接用現成 B-Tree，實作超簡單 | 邊界效應：相鄰點可能落在不同網格前綴不同 |
| 支援範圍查詢 | 矩形網格不貼合圓形搜尋範圍 |
應用：Redis GEOADD / GEORADIUS、MongoDB 2d 索引、Elasticsearch geo 查詢。
2. Quadtree（四分樹）
空間劃分：每個節點代表一矩形區域，資料太多就切成四個子象限（NE / NW / SE / SW），遞迴進行。
整個城市地圖
┌────┬────┐
│ NW │ NE │ ← 一層
├────┼────┤
│ SW │ SE │
└────┴────┘
│
資料太多 → 繼續切
│
┌─┬─┬──────┐
│ │ │ │ ← 二層（NE 細分為 4 個更小象限）
└─┴─┴──────┘
| 優點 | 缺點 |
|---|---|
| 動態精度（密集區切細、稀疏區保留大格） | 固定切 4 等份，不適應資料分佈 |
| 概念簡單直觀 | 需專門的樹結構，不能直接用 B-Tree |
| 對遊戲碰撞檢測友好 | 密集區域樹很深，遍歷慢 |
應用：電玩遊戲（碰撞檢測）、GIS 可視化、Google Maps 的 tile 管理。
（現代資料庫生產環境少見，多讓位給 R-Tree。）
3. R-Tree（Rectangle Tree，生產環境標準）
核心概念：不是固定切 4 等份，而是用 彈性、可重疊的矩形（MBR, Minimum Bounding Rectangle） 根據實際資料分佈來組織。
Quadtree：硬切 4 等份
┌──┬──┐
│ │ │
├──┼──┤
│ │ │
└──┴──┘
R-Tree：根據資料動態調整矩形，允許重疊
┌──────┐
│ ┌──┼──┐
│ │ │ │
└───┼──┘ │
│ │
└─────┘
| 優點 | 缺點 |
|---|---|
| 可同時索引 點、多邊形、道路網絡 | 矩形重疊時查詢要走多分支 |
| 按資料分佈調整，樹較淺 | 維護成本較高 |
支援範圍查詢 / 相交查詢（ST_Intersects） |
實作複雜 |
| 磁碟友好（針對 DB 存取優化） | 不如 Geohash 直觀 |
應用：PostGIS（PostgreSQL 擴展）、SQLite R*Tree module、Oracle Spatial、MySQL SPATIAL index。
4. Google S2 / Uber H3（進階）
兩者都是高階地理索引庫，用於超大規模地理系統。
| 系統 | 做法 | 適合 |
|---|---|---|
| S2 (Google) | 地球投影到 立方體，每面切 4 邊形 cell，每 cell 有唯一 ID | 地圖切片、範圍查詢（YouTube、Foursquare） |
| H3 (Uber) | 地球投影到 二十面體，切 6 邊形 cell | 鄰近搜尋、分佈聚合（Uber 叫車、外送） |
S2 找附近餐廳流程
- 餐廳經緯度 → S2 cell ID
- 使用者位置 → S2 cell ID
S2RegionCoverer計算覆蓋 5km 圓形範圍的 最少 cell 集合- 查詢落在這些 cell 的餐廳
- 用 Haversine 公式做精確距離過濾
H3 找附近餐廳流程
geo_to_h3(lat, lng, resolution)→ 餐廳與使用者的 H3 indexk_ring(cell, k)→ 以使用者 cell 為中心、半徑 k 的所有 6 邊形 cell- 查詢落在這些 cell 的餐廳
- 精確距離過濾
為什麼 H3 選 6 邊形
- 6 邊形到 所有鄰居的距離相等（4 邊形的對角線更遠）
- 更均勻地逼近圓形搜尋範圍
- 更適合鄰近搜尋和分佈式聚合
五種技術對比
| 技術 | 基本原理 | 優點 | 缺點 | 常見應用 |
|---|---|---|---|---|
| Geohash | 2D 座標轉 1D Base32 字串，用 B-Tree 前綴 | 可直接用 B-Tree；簡單；支援範圍查詢 | 邊界效應；矩形不貼圓 | Redis GEO、MongoDB、Elasticsearch |
| Quadtree | 遞迴切 4 等份 | 結構簡單；密集區自動細分 | 固定切法；密集區樹深 | 遊戲碰撞、GIS 可視化 |
| R-Tree | MBR 矩形包覆資料，可重疊 | 同時處理點 / 多邊形；磁碟友好 | 矩形重疊致多路搜尋 | PostGIS、SQLite、空間資料庫標準 |
| S2 | 地球投影到立方體，切 4 邊形 cell | 精度可調；層次化；適合地圖切片 | cell 形狀靠極區變形；實作複雜 | Google Maps、Foursquare、YouTube |
| H3 | 地球投影到二十面體，切 6 邊形 cell | 分佈均勻；適合鄰近搜尋與聚合 | 需要特殊函式庫；邊界仍需處理 | Uber 叫車 / 外送、熱力圖 |
Simplification-with-exceptions
邊界情況
- Geohash 邊界效應可緩解 — 搜尋時查詢中心 cell + 8 個鄰居 cell 即可涵蓋邊界點。
- 並非所有地理查詢都要索引 — 資料量小（幾百個點）線性掃描反而更快。
- R-Tree 是 SQL 世界的主流，但 NoSQL 更常用 Geohash / S2 / H3，因為後者
更容易做分散式 sharding。 - 高維度會打破一切 — 上述方法都針對 2D（有時 3D）；更高維度（如 ML embedding
的幾百維 vector）要用 Vector DB / ANN 索引，不是 geospatial。
決策流程
需要空間索引？
├─ 用 PostgreSQL / SQLite → PostGIS R-Tree
├─ 用 Redis / MongoDB → Geohash 內建
├─ 極大規模地理服務 → S2（地圖切片）or H3（鄰近搜尋）
└─ 資料量很小 → 不建索引直接算也可以