簡介

如今幾乎全部的O2O應用中都會存在「按範圍搜素、離我最近、顯示距離」等等基於位置的交互，那這樣的功能是怎麼實現的呢？本文提供的實現方式，適用於全部數據庫。html

實現

爲了方便下面說明，先給出一個初始表結構，我使用的是MySQL：java

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

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

實現過程主要分爲四步：
1. 搜索
在數據庫中搜索出接近指定範圍內的商戶，如：搜索出1千米範圍內的。
2. 過濾
搜索出來的結果可能會存在超過1千米的，須要再次過濾。若是對精度沒有嚴格要求，能夠跳過。
3. 排序
距離由近到遠排序。若是不須要，能夠跳過。
4. 分頁
若是須要二、3步，才須要對分頁特殊處理。若是不須要，能夠在第1步直接SQL分頁。mysql

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

step1 搜索

搜索能夠用下面兩種方式來實現。github

區間查找

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

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

• 1
• 2
• 3
• 4
• 5

• 1
• 2
• 3
• 4
• 5

// 移動設備經緯度
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());// 緯度範圍

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

計算出經緯度範圍以後，SQL是這樣：sql

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

• 1
• 2
• 3

• 1
• 2
• 3

須要給lon、lat兩個字段創建聯合索引：數據庫

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

• 1

• 1

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 ;

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13

在新增或修改一個商戶的時候，維護好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(?, '%');

• 1
• 2
• 3

• 1
• 2
• 3

這樣會比區間查找快不少，而且得益於geo_code的類似性，能夠對熱點區域作緩存。但這樣使用geohash還存在一個問題，geohash最終是在地圖上鋪上了一個網格，每個網格表明一個geohash值，當傳入的座標接近當前網格的邊界時，用上面的搜索方式就會丟失它附近的數據。好比下圖中，在綠點的位置搜索不到白家大院，綠點和白家大院在劃分的時候就分到了兩個格子中。

解決這個問題思路也比較簡單，咱們查詢時，除了使用綠點的geohash編碼進行匹配外，還使用周圍8個網格的geohash編碼，這樣能夠避免這個問題。那怎麼計算出周圍8個網格的geohash呢，可使用geohash-java來解決。

<dependency> <groupId>ch.hsr</groupId> <artifactId>geohash</artifactId> <version>1.3.0</version> </dependency>

• 1
• 2
• 3
• 4
• 5

• 1
• 2
• 3
• 4
• 5

// 移動設備經緯度
double lon = 116.312528, lat = 39.983733; GeoHash geoHash = GeoHash.withCharacterPrecision(lat, lon, 10); // 當前 System.out.println(geoHash.toBase32()); // N, NE, E, SE, S, SW, W, NW GeoHash[] adjacent = geoHash.getAdjacent(); for (GeoHash hash : adjacent) { System.out.println(hash.toBase32()); }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

最終咱們的sql變成了這樣：

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

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

原來的1次查詢變成了9次查詢，性能確定會降低，這裏能夠優化下。還用上面的需求場景，搜索1千米範圍內的商戶，從上面的表格知道，geo_code長度爲5時，網格寬高是4.9KM，用9個geo_code查詢時，範圍太大了，因此能夠將geo_code長度設置爲6，即縮小了查詢範圍，也知足了需求。還能夠繼續優化，在存儲geo_code時，只計算到6位，這樣就能夠將sql變成這樣：

SELECT id, name FROM customer WHERE geo_code IN (?, ?, ?, ?, ?, ?, ?, ?, ?);

• 1
• 2
• 3

• 1
• 2
• 3

這樣將前綴匹配換成了直接匹配，速度會提高不少。

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

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9

過濾代碼就不寫了，遍歷一遍搜索結果便可。

step3 排序

一樣，排序也須要在應用程序中處理。排序基於上面的過濾結果作就能夠了Collections.sort(list, comparator)。

step4 分頁

若是須要二、3步，只能在內存中分頁，作法也很簡單，能夠參考這篇文章。

總結

全文的重點都在於搜索如何實現，更好的利用數據庫的索引，兩種搜索方式以百萬數據量爲分割線，第一種適用於百萬如下，第二種適用於百萬以上，未通過嚴格驗證。可能有人會有疑問，過濾和排序都在應用層作，內存佔用會不會很嚴重？這是個潛在問題，但大多數狀況下不會。看咱們大部分的應用場景，都是單一種類POI(Point 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
http://cevin.net/geohash/

本文來自：高爽|Coder，原文地址：http://blog.csdn.net/ghsau/article/details/50591932，轉載請註明。