高效的多維空間點索引演算法 — Geohash 和 Google S2

引子

每天我們晚上加班回家，可能都會用到滴滴或者共享腳踏車。打開 app 會看到如下的界面：

app 界面上會顯示出自己附近一個範圍內可用的計程車或者共享腳踏車。假設地圖上會顯示以自己為圓心，5公里為半徑，這個範圍內的車。如何實現呢？最直觀的想法就是去資料庫裡面查表，計算並查詢車距離用戶小於等於5公里的，篩選出來，把數據返回給客戶端。

這種做法比較笨，一般也不會這麼做。為什麼呢？因為這種做法需要對整個表裡面的每一項都計算一次相對距離。太耗時了。既然數據量太大，我們就需要分而治之。那麼就會想到把地圖分塊。這樣即使每一塊裡面的每條數據都計算一次相對距離，也比之前全表都計算一次要快很多。

我們也都知道，現在用的比較多的資料庫 MySQL、PostgreSQL 都原生支持 B+ 樹。這種數據結構能高效的查詢。地圖分塊的過程其實就是一種添加索引的過程，如果能想到一個辦法，把地圖上的點添加一個合適的索引，並且能夠排序，那麼就可以利用類似二分查找的方法進行快速查詢。

問題就來了，地圖上的點是二維的，有經度和緯度，這如何索引呢？如果只針對其中的一個維度，經度或者緯度進行搜索，那搜出來一遍以後還要進行二次搜索。那要是更高維度呢？三維。可能有人會說可以設置維度的優先順序，比如拼接一個聯合鍵，那在三維空間中，x，y，z 誰的優先順序高呢？設置優先順序好像並不是很合理。

本篇文章就來介紹2種比較通用的空間點索引演算法。

一. GeoHash 演算法

1. Genhash 演算法簡介

Genhash 是一種地理編碼，由 Gustavo Niemeyer 發明的。它是一種分級的數據結構，把空間劃分為網格。Genhash 屬於空間填充曲線中的 Z 階曲線（Z-order curve）的實際應用。

何為 Z 階曲線？

上圖就是 Z 階曲線。這個曲線比較簡單，生成它也比較容易，只需要把每個 Z 首尾相連即可。

Z 階曲線同樣可以擴展到三維空間。只要 Z 形狀足夠小並且足夠密，也能填滿整個三維空間。

說到這裡可能讀者依舊一頭霧水，不知道 Geohash 和 Z 曲線究竟有啥關係？其實 Geohash演算法 的理論基礎就是基於 Z 曲線的生成原理。繼續說回 Geohash。

Geohash 能夠提供任意精度的分段級別。一般分級從 1-12 級。

字元串長度 cell 寬度 cell 高度

還記得引語裡面提到的問題么？這裡我們就可以用 Geohash 來解決這個問題。

我們可以利用 Geohash 的字元串長短來決定要劃分區域的大小。這個對應關係可以參考上面表格裡面 cell 的寬和高。一旦選定 cell 的寬和高，那麼 Geohash 字元串的長度就確定下來了。這樣我們就把地圖分成了一個個的矩形區域了。

地圖上雖然把區域劃分好了，但是還有一個問題沒有解決，那就是如何快速的查找一個點附近鄰近的點和區域呢？

Geohash 有一個和 Z 階曲線相關的性質，那就是一個點附近的地方(但不絕對) hash 字元串總是有公共前綴，並且公共前綴的長度越長，這兩個點距離越近。

由於這個特性，Geohash 就常常被用來作為唯一標識符。用在資料庫裡面可用 Geohash 來表示一個點。Geohash 這個公共前綴的特性就可以用來快速的進行鄰近點的搜索。越接近的點通常和目標點的 Geohash 字元串公共前綴越長（但是這不一定，也有特殊情況，下面舉例會說明）

Geohash 也有幾種編碼形式，常見的有2種，base 32 和 base 36。