1、GEOHash——如何“搖一搖”
1-1、為什么需要GEOHash
現(xiàn)在很多APP都有“搖一搖”、“附近的人”、網(wǎng)約車離我有多遠等類似的功能。
那就不可避免需要進行一系列的地理坐標轉換為距離的計算。
獲取地理坐標不難，只需要用戶授權就能輕松獲取到很精確的經(jīng)緯度；
計算距離也不難：兩點之間坐標差的平方相加，再開方即可（簡書的markdown太差了，公式也不支持）。
問題在于，用戶數(shù)量劇增以后（百萬、千萬、億……），每次進行全量距離計算本身就變成了一個巨大的負擔，大量乘方、開方這樣的浮點運算，不管多么強壯的算力都會被壓垮。
1-2、什么是GEOHash
GEOHash是解決這一問題的一種算法。
GEOHash的核心思想是將二維的經(jīng)緯度轉換成一維的字符串，這樣無論使用何種方式存儲用戶的位置數(shù)據(jù)，都可以很方便地建立索引，大大簡化計算。
GEOHash有三個主要特點：
字符串越長，表示的范圍越精確。編碼長度為8時，精度在19米左右，而當編碼長度為9時，精度在2米左右。
字符串相似的表示距離相近，利用字符串的前綴匹配，可以查詢附近的地理位置。
GEOHash編碼后的字符串，可以反向解碼出原來的經(jīng)緯度。
1-3、GEOHash編碼的簡易原理
GEOHash的編碼過程并不復雜，首先使用分形的思想對經(jīng)緯度做處理（二維空間轉換為分形維），轉為二進制字符串；然后偶數(shù)位放經(jīng)度，奇數(shù)位放緯度，得到一個新的二進制字符串；最后對該二進制字符串做Base32編碼處理即可（或者使用Base64）。
但是“為什么”要這樣編碼，就涉及到計算機圖形學的一些思想（GEOHash應用了Peano曲線），本篇側重應用，原理的具體說明此處略去。
1-4、GEOHash的邊緣問題
GEOHash編碼時，實際上就是把所有區(qū)域分割成大小相同的矩形塊（分得越細，字符串就越長，精度越精確）。
但是不管分割得怎么細，都是一個矩形區(qū)域，會出現(xiàn)區(qū)域內(nèi)靠近邊緣的某個點，與另一片區(qū)域中靠近邊緣的點離得更近，但是被誤判的情況。
畢竟同一片區(qū)域內(nèi)的hash碼是相同的，不管離得多遠，都會被判定為離得最近。
解決方法是在查詢時，除了使用定位點的GeoHash碼進行匹配外，還要使用周圍8個區(qū)域的GeoHash編碼一并匹配。
2、Redis中GEOHash的應用
Redis 從3.2版本開始，追加了GEO數(shù)據(jù)類型用于存儲用戶信息，并且提供了各種用于地理計算的方法。
（BTW，對Redis GEO貢獻最大的是其實是國內(nèi)的開發(fā)者。也是因為我們對這個功能的需求最大）
下面是相關的全部命令列表：
GEOADD：增加地理位置的坐標（支持批量操作）
時間復雜度O(log(N))
GEOADD key longitude latitude member [longitude latitude member ...]
- key標識一個地理位置的集合。
- longitude是經(jīng)度，latitude是緯度。
- member是該地理位置的名稱（自定義）。
應用舉例：
geoadd cities 121.47 31.23 shanghai
geoadd cities 116.40 39.90 beijing 118.78 32.07 nanjing
GEOPOS：獲取地理位置的坐標（支持批量操作）
時間復雜度O(log(N))
GEOPOS key member [member ...]
GEODIST：獲取兩個地理位置的距離
時間復雜度O(log(N))
GEODIST key member1 member2 [m|km|ft|mi]
單位可以指定為以下四種類型：
- m：米，距離單位默認為米，不傳遞該參數(shù)則單位為米
- km：公里
- mi：英里
- ft：英尺
應用舉例：
geodist cities beijing shanghai
GEORADIUS：根據(jù)給定地理位置坐標獲取指定范圍內(nèi)的地理位置集合
時間復雜度O(N+log(M))，N為指定半徑范圍內(nèi)的元素個數(shù)，M為要返回的個數(shù)
GEORADIUS key longitude latitude radius [m|km|ft|mi] [WITHCOORD] [WITHDIST] [ASC|DESC] [WITHHASH] [COUNT count]
- longitude是經(jīng)度，latitude是緯度。
- radius表示范圍距離。
- 距離單位可以為m|km|ft|mi
- WITHCOORD：傳入WITHCOORD參數(shù)，則返回結果會帶上匹配位置的經(jīng)緯度。
- WITHDIST：傳入WITHDIST參數(shù)，則返回結果會帶上匹配位置與給定地理位置的距離。
- ASC|DESC：默認結果是未排序的，傳入ASC為從近到遠排序，傳入DESC為從遠到近排序。
- WITHHASH：傳入WITHHASH參數(shù)，則返回結果會帶上匹配位置的hash值。
- COUNT count：傳入COUNT參數(shù)，可以返回指定數(shù)量的結果。
GEORADIUSBYMEMBER：根據(jù)給定地理位置獲取指定范圍內(nèi)的地理位置集合
時間復雜度O(N+log(M))，N為指定半徑范圍內(nèi)的元素個數(shù)，M為要返回的個數(shù)
GEORADIUSBYMEMBER key member radius [m|km|ft|mi] [WITHCOORD] [WITHDIST] [ASC|DESC] [WITHHASH] [COUNT count]
GEORADIUS 命令的參數(shù)是坐標，而本命令的參數(shù)是地理位置名稱，其他無區(qū)別。
應用舉例：
georadiusbymember cities shanghai 50 km
GEOHASH：獲取地理位置的GEOHash值（支持批量操作）
時間復雜度O(log(N))
GEOHASH key member [member ...]
3、關于Redis中GEO的一些說明
redis使用的GEOHash編碼長度為26位，可以精確到0.59m的精度。
Redis中的GEO核心主要是兩點：
- 使用GEOHash保存地理位置的坐標
- 使用有序集合（ZSET）保存地理位置的集合
內(nèi)部的實際存儲使用的是ZSET，進一步說明如下：
GEO命令中的key就是ZSET的名字
Redis沒有提供地理位置的刪除命令?？梢岳肸SET的ZREM命令進行刪除： zrem cities shanghai
執(zhí)行GEOADD命令時，會先按照標準的GEOHash計算方法計算hash值，然后將地理位置名稱（member）作為集合的member，將GEOHash值作為score，執(zhí)行ZADD命令插入到ZSET中
GEORADIUS和GEORADIUSBYMEMBER。內(nèi)部實現(xiàn)實際上就是先執(zhí)行ZRANGE命令，然后判斷結果是否符合命令中指定的距離即可。另外就是這兩個命令已經(jīng)自行解決了GEOHash的“邊緣問題”，會自動關聯(lián)周圍的八片區(qū)域，無需額外處理。
4、Redis以外的GEOHash實現(xiàn)
4-1、MySQL
MySQL從 5.7.4 labs 版本開始增加了對于空間索引的支持，通過R樹實現(xiàn)。
如果不具備升級MySQL的條件，就需要增加類似 geo_hash 的字段，追加地理位置時手動計算hash碼，搜索附近的人時手動解決GEOHash的邊緣問題，從算力和復雜度上來說都不能令人滿意。
4-2、MongoDB + 2d索引
MongoDB主要是通過它的兩種地理空間索引 2dsphere 和 2d來實現(xiàn)地理位置的操作。
兩種索引的底層依然是基于Geohash，但與通用的Geohash還有一些不同。
2dsphere 索引僅支持球形表面的幾何形狀查詢。
2d 索引支持平面幾何形狀和一些球形查詢。雖然2d 索引支持某些球形查詢，但 2d 索引對這些球形查詢時，可能會出錯。所以球形查詢盡量選擇 2dsphere索引。
盡管兩種索引的方式不同，但只要坐標跨度不太大，計算出的距離誤差幾乎可以忽略不計。
對經(jīng)緯度數(shù)據(jù)創(chuàng)建2d索引（db.coll.createIndex）以后，只要使用geoNear命令就可以實現(xiàn)附近的人的功能了。
