簡介

現在幾乎所有的O2O應用中都會存在“按范圍搜素、離我最近、顯示距離”等等類似的功能，那這樣的功能是怎么實現的呢？本文提供了基于MySQL的實現方式，同樣適用于其它數據庫。本文不分析，只講怎么實現，有關分析的文章可以看參考鏈接。

實現

為了方便下面說明，先給出一個初始表結構：

CREATE TABLE `customer` ( `id` INT(11) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT '自增主鍵', `name` VARCHAR(5) NOT NULL COMMENT '名稱' COLLATE 'latin1_swedish_ci', `lon` DOUBLE(9,6) NOT NULL COMMENT '經度', `lat` DOUBLE(8,6) NOT NULL COMMENT '緯度', PRIMARY KEY (`id`) ) COMMENT='商戶表' CHARSET=utf8mb4 ENGINE=InnoDB ;

實現過程主要分為四步：

1. 搜索
   在數據庫中搜索出接近指定范圍內的商戶，如：搜索出1公里范圍內的。
   
2. 過濾
   搜索出來的結果可能會存在超過1公里的，需要再次過濾。如果對精度沒有嚴格要求，可以跳過。
   
3. 排序
   距離由近到遠排序。如果不需要，可以跳過。
   

4. 分頁
   如果需要2、3步，才需要對分頁特殊處理。如果不需要，可以在第1步直接SQL分頁。</p>

   第1步數據庫完成，后3步應用程序完成。

   step1 搜索

   搜索可以用下面兩種方式來實現。

   區間查找

   customer表中使用兩個字段存儲了經度和緯度，如果提前計算出經緯度的范圍，然后在這兩個字段上加上索引，那搜索性能會很不錯。
   那怎么計算出經緯度的范圍呢？已知條件是移動設備所在的經緯度，還有滿足業務要求的半徑，這很像初中的一道平面幾何題：給定圓心坐標和半徑，求該圓外切正方形四個頂點的坐標。而我們面對的是一個球體，可以使用spatial4j來計算。

   <dependency>
   <groupId>com.spatial4j</groupId>
   <artifactId>spatial4j</artifactId>
   <version>0.5</version>
   </dependency>

   double lon = 116.312528, lat = 39.983733;// 移動設備經緯度
   int radius = 1;// 千米
   
   

SpatialContext geo = SpatialContext.GEO; Rectangle rectangle = geo.getDistCalc().calcBoxByDistFromPt( geo.makePoint(lon, lat), radius * DistanceUtils.KM_TO_DEG, geo, null); System.out.println(rectangle.getMinX() + "-" + rectangle.getMaxX());// 經度范圍 System.out.println(rectangle.getMinY() + "-" + rectangle.getMaxY());// 緯度范圍</pre>

計算出經緯度范圍之后，SQL是這樣：

SELECT id, name FROM customer WHERE (lng BETWEEN ? AND ?) AND (lat BETWEEN ? AND ?);

需要給lon、lat兩個字段建立聯合索引：

INDEX `idx_lon_lat` (`lon`, `lat`)

geohash

geohash的原理不講了，詳細可以看這篇文章，講的很詳細。geohash算法能把二維的經緯度編碼成一維的字符串，它的特點是越相近的經緯度編碼后越相似，所以可以通過前綴like的方式去匹配周圍的商戶。
customer表要增加一個字段，來存儲每個商戶的geohash編碼，并且建立索引。

CREATE TABLE `customer` ( `id` INT(11) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT '自增主鍵', `name` VARCHAR(5) NOT NULL COMMENT '名稱' COLLATE 'latin1_swedish_ci', `lon` DOUBLE(9,6) NOT NULL COMMENT '經度', `lat` DOUBLE(8,6) NOT NULL COMMENT '緯度', `geo_code` CHAR(12) NOT NULL COMMENT 'geohash編碼', PRIMARY KEY (`id`), INDEX `idx_geo_code` (`geo_code`) ) COMMENT='商戶表' CHARSET=utf8mb4 ENGINE=InnoDB ;

在新增或修改一個商戶的時候，維護好geo_code，那geo_code怎么計算呢？spatial4j也提供了一個工具類GeohashUtils.encodeLatLon(lat, lon)，默認精度是12位。
這個存儲做好后，就可以通過geo_code去搜索了。拿到移動設備的經緯度，計算geo_code，這時可以指定精度計算，那指定多長呢？我們需要一個geo_code長度和距離的對照表：

https://en.wikipedia.org/wiki/Geohash#Cell_Dimensions

假設我們的需求是1公里范圍內的商戶，geo_code的長度設置為5就可以了，GeohashUtils.encodeLatLon(lat, lon, 5)。計算出移動設備經緯度的geo_code之后，SQL是這樣：

SELECT id, name FROM customer WHERE geo_code LIKE CONCAT(?, '%');

這樣會比區間查找快很多，并且得益于geo_code的相似性，可以對熱點區域做緩存。

step2 過濾

上面兩種搜索方式，都不是精確搜索，只是盡量縮小搜索范圍，提升響應速度。所以需要在應用程序中做過濾，把距離大于1公里的商戶過濾掉。計算距離同樣使用spatial4j。

// 移動設備經緯度
double lon1 = 116.3125333347639, lat1 = 39.98355521792821;
// 商戶經緯度
double lon2 = 116.312528, lat2 = 39.983733;

SpatialContext geo = SpatialContext.GEO;
double distance = geo.calcDistance(geo.makePoint(lon1, lat1), geo.makePoint(lon2, lat2)) * DistanceUtils.DEG_TO_KM;
System.out.println(distance);// KM</pre> 
 
過濾代碼就不寫了，遍歷一遍搜索結果即可。

step3 排序
同樣，排序也需要在應用程序中處理。排序基于上面的過濾結果做就可以了Collections.sort(list, comparator)。
step4 分頁
如果需要2、3步，只能在內存中分頁，做法也很簡單，可以參考這篇文章。
總結
全文的重點都在于搜索如何實現，更好的利用數據庫的索引，兩種搜索方式以百萬數據量為分割線，第一種適用于百萬以下，第二種適用于百萬以上，未經過嚴格驗證。可能有人會有疑問，過濾和排序都在應用層做，內存占用會不會很嚴重？這是個潛在問題，但大多數情況下不會。看我們大部分的應用場景，都是單一種類POI(Person Of Interest)的搜索，如酒店、美食、KTV、電影院等等，這種數據密度是很小，1公里內的酒店，能有多少家，50家都算多的，所以最終要看具體業務數據密度。
 


參考資料
http://www.infoq.com/cn/articles/depth-study-of-Symfony2 

 http://tech.meituan.com/lucene-distance.html 

 http://blog.csdn.net/liminlu0314/article/details/8553926 

 http://janmatuschek.de/LatitudeLongitudeBoundingCoordinates 

 http://www.cnblogs.com/LBSer/p/3310455.html
</div>