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

逃离我推掉我的手 2022-05-30 08:45 112阅读 0赞

# 简介 #

现在几乎所有的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的原理不讲了，详细可以看[这篇文章][Link 1]，讲的很详细。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长度和距离的对照表：

<table style="width:934px;background-color:rgb(255,255,255);border-spacing:0px;border:1px solid rgb(238,238,238);text-align:center;color:rgb(63,63,63);font-family:'-apple-system', 'SF UI Text', Arial, 'PingFang SC', 'Hiragino Sans GB', 'Microsoft YaHei', 'WenQuanYi Micro Hei', sans-serif, SimHei, SimSun;font-size:16px;"> 
 <thead> 
  <tr> 
   <th style="vertical-align:middle;">geohash length</th> 
   <th style="vertical-align:middle;">width</th> 
   <th style="vertical-align:middle;">height</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="vertical-align:middle;">1</td> 
   <td style="vertical-align:middle;">5,009.4km</td> 
   <td style="vertical-align:middle;">4,992.6km</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:middle;">2</td> 
   <td style="vertical-align:middle;">1,252.3km</td> 
   <td style="vertical-align:middle;">624.1km</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:middle;">3</td> 
   <td style="vertical-align:middle;">156.5km</td> 
   <td style="vertical-align:middle;">156km</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:middle;">4</td> 
   <td style="vertical-align:middle;">39.1km</td> 
   <td style="vertical-align:middle;">19.5km</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:middle;">5</td> 
   <td style="vertical-align:middle;">4.9km</td> 
   <td style="vertical-align:middle;">4.9km</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:middle;">6</td> 
   <td style="vertical-align:middle;">1.2km</td> 
   <td style="vertical-align:middle;">609.4m</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:middle;">7</td> 
   <td style="vertical-align:middle;">152.9m</td> 
   <td style="vertical-align:middle;">152.4m</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:middle;">8</td> 
   <td style="vertical-align:middle;">38.2m</td> 
   <td style="vertical-align:middle;">19m</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:middle;">9</td> 
   <td style="vertical-align:middle;">4.8m</td> 
   <td style="vertical-align:middle;">4.8m</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:middle;">10</td> 
   <td style="vertical-align:middle;">1.2m</td> 
   <td style="vertical-align:middle;">59.5cm</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:middle;">11</td> 
   <td style="vertical-align:middle;">14.9cm</td> 
   <td style="vertical-align:middle;">14.9cm</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:middle;">12</td> 
   <td style="vertical-align:middle;">3.7cm</td> 
   <td style="vertical-align:middle;">1.9cm</td> 
  </tr> 
 </tbody> 
</table>

> [https://en.wikipedia.org/wiki/Geohash\#Cell\_Dimensions][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值，当传入的坐标接近当前网格的边界时，用上面的搜索方式就会丢失它附近的数据。比如下图中，在绿点的位置搜索不到白家大院，绿点和白家大院在划分的时候就分到了两个格子中。   
![这里写图片描述][20160715101657127]   
解决这个问题思路也比较简单，我们查询时，除了使用绿点的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步，只能在内存中分页，做法也很简单，可以参考[这篇文章][Link 2]。

# 总结 #

全文的重点都在于搜索如何实现，更好的利用数据库的索引，两种搜索方式以百万数据量为分割线，第一种适用于百万以下，第二种适用于百万以上，`未经过严格验证`。可能有人会有疑问，过滤和排序都在应用层做，内存占用会不会很严重？这是个潜在问题，但大多数情况下不会。看我们大部分的应用场景，都是单一种类POI(Point Of Interest)的搜索，如酒店、美食、KTV、电影院等等，这种数据密度是很小，1公里内的酒店，能有多少家，50家都算多的，所以最终要看具体业务数据密度。本文没有分析原理，只讲了具体实现，有关分析的文章可以看参考链接。

[spatial4j]: https://github.com/locationtech/spatial4j
[Link 1]: http://www.cnblogs.com/LBSer/p/3310455.html
[https_en.wikipedia.org_wiki_Geohash_Cell_Dimensions]: https://en.wikipedia.org/wiki/Geohash#Cell_Dimensions
[20160715101657127]: /images/20220530/456bad2bee4b4cd48ab933ee047d18ed.png
[geohash-java]: https://github.com/kungfoo/geohash-java
[Link 2]: http://blog.csdn.net/ghsau/article/details/7243540