為什麼要用Geohash
將二維座標映射成一串字串,表示一個特定的長方形網格範圍
台北101的座標(“25.03463”, “121.56441”),在精度8的情況下會轉換成"wsqqqm2t"
字串越長、範圍越小、精度越高
優點
- 資料庫索引可從經緯度簡化成一列geohash
- geohash表示範圍,容許誤差,保護用戶隱私
- 字串順序表示範圍層級,方便查詢附近地點
缺點
轉換回經緯度會有誤差,不適用高精準度的查詢
Geohash 算法
將經緯度範圍切成一半,如果在上半部得到數字 1,在下半部得到數字 0,依此類推得到所需的二進制精度。
計算步驟:
第一步:從經度-180度到180度劃分成兩個區塊,(180,0)為上半部代表數字 1,(0,-180)為下半部代表數字 0,台北101經度的121.56441度會得到數字 1。
第二步:由第一步確認台北101屬於(180,0)區間,接著從經度180度到0度劃分成兩個區塊,(180,90)為上半部代表數字 1,(90,-0)為下半部代表數字 0,台北101經度的121.56441度會得到數字 1。
之後步驟:由此類推……
經緯度轉換二進制
台北101經度 121.56441
經度範圍 | 劃分區間1 | 劃分區間0 | 精度 | Binary數字 |
---|---|---|---|---|
-180 ~ 180 | 180 ~ 0 | 0 ~ 180 | 121 | 1 |
180 ~ 0 | 180 ~ 90 | 90 ~ 0 | 121 | 1 |
180 ~ 90 | 180 ~ 135 | 135 ~ 90 | 121 | 0 |
135 ~ 90 | 135 ~ 112.5 | 112.5 ~ 90 | 121 | 1 |
135 ~ 112.5 | 135 ~ 123.75 | 123.75 ~ 112.5 | 121 | 0 |
123.75 ~ 112.5 | 123.75 ~ 118.125 | 118.125 ~ 112.5 | 121 | 1 |
123.75 ~ 118.125 | 123.75 ~ 120.9375 | 120.9375 ~ 118.125 | 121 | 1 |
123.75 ~ 120.9375 | 123.75 ~ 122.34375 | 122.34375 ~ 120.9375 | 121 | 0 |
122.34375 ~ 120.9375 | 122.34375 ~ 121.640625 | 121.640625 ~ 120.9375 | 121.5 | 0 |
121.640625 ~ 120.9375 | 121.640625 ~ 121.2890625 | 121.2890625 ~ 120.9375 | 121.5 | 1 |
台北101緯度 25.03463
經度範圍 | 劃分區間1 | 劃分區間0 | 精度 | Binary數字 |
---|---|---|---|---|
-90 ~ 90 | 90 ~ 0 | 0 ~ -90 | 25 | 1 |
90 ~ 0 | 90 ~ 45 | 45 ~ 0 | 25 | 0 |
45 ~ 0 | 45 ~ 22.5 | 22.5 ~ 0 | 25 | 1 |
45 ~ 22.5 | 45 ~ 33.75 | 33.75 ~ 22.5 | 25 | 0 |
33.75 ~ 22.5 | 33.75 ~ 28.125 | 28.125 ~ 22.5 | 25 | 0 |
28.125 ~ 22.5 | 28.125 ~ 25.3125 | 25.3125 ~ 22.5 | 25 | 0 |
25.3125 ~ 22.5 | 25.3125 ~ 23.90625 | 23.90625 ~ 22.5 | 25 | 1 |
25.3125 ~ 23.90625 | 25.3125 ~ 24.609375 | 24.609375 ~ 23.90625 | 25 | 1 |
25.3125 ~ 24.609375 | 25.3125 ~ 24.9609375 | 24.9609375 ~ 24.609375 | 25 | 1 |
25.3125 ~ 24.9609375 | 25.3125 ~ 25.13671875 | 25.13671875 ~ 24.609375 | 25 | 0 |
二進制數字合併
經過上方圖表的計算轉換得到:
經度二進制: 11010 11001
緯度二進制: 10100 01110
將經度交錯放置偶數位、緯度放奇數位
經緯度的二進制數字合併成 11100 11000 10110 10110
經度 | 緯度 | 合併值 |
---|---|---|
1 | - | 1 |
- | 1 | 11 |
1 | - | 111 |
- | 0 | 1110 |
0 | - | 11100 |
- | 1 | 11100 1 |
1 | - | 11100 11 |
- | 0 | 11100 110 |
0 | - | 11100 1100 |
- | 0 | 11100 11000 |
轉成十進制查詢base32字串
將二進制轉成十進制,依照base32表查詢字串
(因容易和數字搞混,base32 去掉 a, i, l, o)
二進制 | 十進制 | base32 | 二進制經度數量 | 二進制緯度數量 |
---|---|---|---|---|
11100 | 28 | w | 3 | 2 |
11000 | 24 | s | 5 | 5 |
10110 | 22 | q | 8 | 7 |
10110 | 22 | q | 10 | 10 |
得出台北101 geohash字串長方型網格範圍"wsqq"
Geohash長度對應面積表
geohash長度 | 面積 | km誤差 |
---|---|---|
1 | 5,009.4km x 4,992.6km | +- 2500km |
2 | 1,252.3km x 624.1km | +- 630km |
3 | 156.5km x 156km | +- 78km |
4 | 39.1km x 19.5km | +- 20km |
5 | 4.9km x 4.9km | +- 2.4km |
6 | 1.2km x 609.4m | +- 610m |
7 | 152.9m x 152.4m | +- 76m |
8 | 38.2m x 19m | +- 19m |
通常用到geohash 5~8長度即可 |
工作上實際應用
目前我們在全球各地擁有超過一萬個停車點
隨著運營規模擴大、車輛數的增加
上/下班尖峰時刻、演唱會等特殊情況
高併發的API Request會使資料庫SQL無法即時算出資料,造成資料擁塞。
原本的解法
在PostgreSQL用車輛經緯度計算,距離所有停車點橢圓球體5公里內的最近停車點
(比對數萬個停車點)
|
|
導入Geohash後
取得車輛方圓5公里內最近的停車點
因此面積是 5km x 5km x pi = 78平方公里
選用層級五即可
分析步驟:
- 如果層級五有找到停車點(紅色區域,5km x 5km = 25平方公里),找到停車點->query
- 如果層級五沒有找到停車點,找同層級的其他八個區域(綠色區域),總面積達到225平方公里(25km2 x 9 = 225km2),找到停車點->query
- 如果層級五的九宮格都沒有找到,則沒有滿足條件的停車點
結論:
1. 減少查詢SQL次數
首先可以判斷是否座標周圍有涵蓋目標座標(使用者周圍是否有停車點)
2. 提升SQL查詢效率
第二是可以依照網格層級決定篩選多少量級的資料 藉由判斷是否在自身geohash網格、周圍八個geohash網格,將篩選出的資料範圍縮小
補充:Node Geohash套件
npm - ngeohash: https://www.npmjs.com/package/ngeohash
|
|
其他用法:
|
|
周圍四個角落的經緯度
周圍的八個Geohash網格
參考資料
影片:
** 1. 如何搜索附近的商家? Geohash (上)**
https://www.youtube.com/watch?v=NCvYkJWenb8&t=745s&ab_channel=HuaHua
** 2. 如何搜索附近的商家? Geohash (下)**
https://www.youtube.com/watch?v=_UAkuUVzwcY&ab_channel=HuaHua
Demo工具:
1. GeoHash Demo
https://phrozen.github.io/geohash/
2. ngeohash(Node.js)
https://www.npmjs.com/package/ngeohash
文章:
1. 空间索引之GeoHash
https://www.biaodianfu.com/geohash.html