[转] 如何实现按距离排序、范围查找

简介

如今几乎全部的O2O应用中都会存在“按范围搜素、离我最近、显示距离”等等基于位置的交互,那这样的功能是怎么实现的呢?本文提供的实现方式,适用于全部数据库html

实现

为了方便下面说明,先给出一个初始表结构,我使用的是MySQLjava

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长度和距离的对照表:数据结构

geohash length width height
1 5,009.4km 4,992.6km
2 1,252.3km 624.1km
3 156.5km 156km
4 39.1km 19.5km
5 4.9km 4.9km
6 1.2km 609.4m
7 152.9m 152.4m
8 38.2m 19m
9 4.8m 4.8m
10 1.2m 59.5cm
11 14.9cm 14.9cm
12 3.7cm 1.9cm

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,转载请注明。

相关文章
相关标签/搜索