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

简介

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

实现

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

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. 搜索 在数据库中搜索出接近指定范围内的商户,如:搜索出1公里范围内的。 2. 过滤 搜索出来的结果可能会存在超过1公里的,需要再次过滤。如果对精度没有严格要求,可以跳过。 3. 排序 距离由近到远排序。如果不需要,可以跳过。 4. 分页 如果需要2、3步,才需要对分页特殊处理。如果不需要,可以在第1步直接SQL分页。

第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());// 纬度范围

计算出经纬度范围之后,SQL是这样:

SELECT id, name
FROM customer
WHERE (lon 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长度和距离的对照表:

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(?, '%');

这样会比区间查找快很多,并且得益于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>
// 移动设备经纬度
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());
}

最终我们的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次查询变成了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 (?, ?, ?, ?, ?, ?, ?, ?, ?);

这样将前缀匹配换成了直接匹配,速度会提升很多。

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

过滤代码就不写了,遍历一遍搜索结果即可。

step3 排序

同样,排序也需要在应用程序中处理。排序基于上面的过滤结果做就可以了Collections.sort(list, comparator)

step4 分页

如果需要2、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/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏牛肉圆粉不加葱

Spark SQL Limit 介绍及优化

全局限制,最多返回 limitExpr 对应条 records。总是通过 IntegerLiteral#unapply(limitExpr: Expressio...

992
来自专栏PPV课数据科学社区

【学习】七天搞定SAS(二):基本操作(判断、运算、基本函数)

? 今天开始注重变量操作。 SAS生成新变量 SAS支持基本的加减乘除,值得一提的是它的**代表指数,而不是^。* Modify homegarden dat...

2944
来自专栏开发 & 算法杂谈

Django-Database 之 Many-To-Many关系

这里对Many-To-Many即多对多的映射关系以详细事例来分析Django中Database操作多对多映射关系的一些基本用法和注意事项

752
来自专栏大数据架构

Spark SQL / Catalyst 内部原理 与 RBO

从上图可见,无论是直接使用 SQL 语句还是使用 DataFrame,都会经过如下步骤转换成 DAG 对 RDD 的操作

432
来自专栏C语言及其他语言

【每日一题】问题 1269: P1002

关注我们 题目描述 某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种,获取的条件各自不同: 1)院士奖学金,每人8000元,期...

27811
来自专栏大数据架构

Spark SQL 性能优化再进一步 CBO 基于代价的优化

上文Spark SQL 内部原理中介绍的 Optimizer 属于 RBO,实现简单有效。它属于 LogicalPlan 的优化,所有优化均基于 Logical...

533
来自专栏数据和云

用SQL解一道有趣的数学题:Gauss和Poincare

杨廷琨,网名 yangtingkun 云和恩墨技术总监,Oracle ACE Director,ACOUG 核心专家 用SQL为解析一道数学题 ---- Ora...

3515
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (下)

在前一部分的最后,我们给出了一个寻路的示例,在大多数情况下,运行还算良好,但是有一个小问题,如下图: ? 很明显,障碍物已经把路堵死了,但是小球仍然穿过对角线跑...

1859
来自专栏牛客网

【后台开发】百度,头条,腾讯面经

半年了,从七月的迷之自信,到十月的0offer,迷茫、反思、不甘,各位战友的鼓励激励着我前进... 终于拿到了offer,感谢牛客网长期以来的陪伴,在此献上面经...

3965
来自专栏转载gongluck的CSDN博客

FFmpeg菜鸡互啄#第6篇#音频帧格式转换(重采样)

关键步骤 struct SwrContext* swr_covert_ctx = swr_alloc_set_opts(NULL, av_get_def...

3895

扫码关注云+社区