滴滴出现是一款非常好用的APP，解决了日常用户的出行需求，产品的背后需要非常精湛的技术支持，其中一项技术叫附近查找，附近查找的业务可能会基于多种业务规则，最常用的就是基于出行人的地理位置，查找附件的司机，从而将该出行需求信息推送给给附近的司机（以上是滴滴的业务，跟我们的业务并没有任何关系，只是为了描述业务场景）。我们的货车业务一样需要用到附近查找的技术，通过定位当前用户的位置，查询附近的货车，并在地图上展示。
地图后台如何根据自己所在位置查询来查询附近货车的呢？计算用户所在位置P与朝阳区所有货车距离，然后返回距离<=1000米的货车。问题来了，那么如果我们朝阳区有10万辆货车，这样计算不得了，是否可以考虑用索引？
一提到索引，大家脑子里马上浮现出B树索引，因为大量的数据库（如MySQL、oracle、PostgreSQL等）都在使用B树。B树索引本质上是对索引字段进行排序，然后通过类似二分查找的方法进行快速查找，即它要求索引的字段是可排序的，一般而言，可排序的是一维字段，比如时间、年龄、薪水等等。但是对于空间上的一个点（二维，包括经度和纬度），如何排序呢？又如何索引呢？解决的方法很多，下文介绍几种方法来解决这一问题。
- 支持二维索引的存储数据库：mongo
mongoDB支持二维空间索引,使用空间索引,mongoDB支持一种特殊查询,如某地图网站上可以查找离你最近的咖啡厅,银行等信息。这个使用mongoDB的空间索引结合特殊的查询方法很容易实现。 db.places.find( { location : { $near : [39.9994520000,116.4021310000], $maxDistance: 0.7 } } ).limit(20); 获取附近半径0.7附近的20条记录，经常简单实用。
优点:API直接支持，很方便
缺点：mongo2D查询不能建立联合索引，再基于其它条件排序的话，性能比较低，类似mysql的filesort，并发量大、数据量大的话性能是mongo会成为瓶颈。
- 升级Mysql至5.7，支持Geohash
MySQL 5.7.5 增加了对GeoHash的支持，提供了一系列geohash的函数，但是其实Mysql并没有提供类似mogodb类型near这样的函数，仅仅提供了一些经纬度转hash、hash取经纬度的一些函数。 参考：spatial-geohash-functions : http://dev.mysql.com/doc/refman/5.7/en/spatial-geohash-functions.html
优点:函数直接调用，生成目标hash、根据hash获取经纬度。
缺点：不支持范围查询函数，需要自行处理周边8点的问题，需要补充geo的算法
- Redis Commands: Geography Edition
GEO 特性在 Redis 3.2 版发布， 这个功能可以将用户给定的地理位置信息储存起来， 并对这些信息进行操作，GEO通过如下命令来完成GEO需求：详细参考： redis-geo:https://matt.sh/redis-geo Redis GEO 特性简介:http://blog.jobbole.com/89225/
命令 描述 example
geoadd添加一个或多个经纬度地理位置geoadd beijing 40.747533 -73.9454966 “tiananmen”
georadius获取指定范围内的对象，也可以增加参数withdistance直接算出距离，也可以增加参数descending/ascending 进行距离排序 georadius beijing 40.7598464 -73.9798091 3 km
georadiusbymember通过指定的对象，获取其周边对象georadiusbymember beijing “tiananmen” 7 km withdist asc
geoencode转换为geohash，52-bit，同时返回该区域最小角的geohash,最大角的geohash，及中心点geoencode 41.2358883 1.8063239geodecode同上逆操作geodecode 3471579339700058
优点:效率高，API丰富
缺点：3.2版本是否稳定？
- 基于Lucene-Spatial的地理位置查找
Lucene通过Spatial包提供了对基于地理位置的全文检索的支持，将坐标信息转化为笛卡尔层，建立索引
优点:天然支持，性能很优。
缺点：需要投入时间研究一下特性。
以上方案大部分都基于GEOHASH，思想通过某种方法将二维的点数据转换成一维的数据,我们已mysql为例，那样不就可以继续使用B树索引了嘛。
GeoHash将二维的经纬度转换成字符串，比如下图展示了北京9个区域的GeoHash字符串，分别是WX4ER，WX4G2、WX4G3等等，每一个字符串代表了某一矩形区域。也就是说，这个矩形区域内所有的点（经纬度坐标）都共享相同的GeoHash字符串，这样既可以保护隐私（只表示大概区域位置而不是具体的点），又比较容易做缓存，比如左上角这个区域内的用户不断发送位置信息请求餐馆数据，由于这些用户的GeoHash字符串都是WX4ER，所以可以把WX4ER当作key，把该区域的餐馆信息当作value来进行缓存，而如果不使用GeoHash的话，由于区域内的用户传来的经纬度是各不相同的，很难做缓存。
字符串越长，表示的范围越精确。如图所示，5位的编码能表示10平方千米范围的矩形区域，而6位编码能表示更精细的区域（约0.34平方千米）
通过上面的介绍我们知道了GeoHash就是一种将经纬度转换成字符串的方法，并且使得在大部分情况下，字符串前缀匹配越多的距离越近，回到我们的案例，根据所在位置查询来查询附近餐馆时，只需要将所在位置经纬度转换成GeoHash字符串，并与各个餐馆的GeoHash字符串进行前缀匹配，匹配越多的距离越近。
理论略过，网上一大堆，参考：
Geohash ：https://en.wikipedia.org/wiki/Geohash
简单讲一下Peano空间填充曲线
如图所示，我们将二进制编码的结果填写到空间中，当将空间划分为四块时候，编码的顺序分别是左下角00，左上角01，右下脚10，右上角11，也就是类似于Z的曲线，当我们递归的将各个块分解成更小的子块时，编码的顺序是自相似的（分形），每一个子快也形成Z曲线，这种类型的曲线被称为Peano空间填充曲线。
这种类型的空间填充曲线的优点是将二维空间转换成一维曲线（事实上是分形维），对大部分而言，编码相似的距离也相近， 但Peano空间填充曲线最大的缺点就是突变性，有些编码相邻但距离却相差很远，比如0111与1000，编码是相邻的，但距离相差很大。
除Peano空间填充曲线外，还有很多空间填充曲线，如图所示，其中效果公认较好是Hilbert空间填充曲线，相较于Peano曲线而言，Hilbert曲线没有较大的突变。为什么GeoHash不选择Hilbert空间填充曲线呢？可能是Peano曲线思路以及计算上比较简单吧，事实上，Peano曲线就是一种四叉树线性编码方式。
- 边界问题
由于GeoHash是将区域划分为一个个规则矩形，并对每个矩形进行编码，就导致了geohash算法会有突变性，这样在查询附近信息时会导致距离很近的2个位置，GeoHash编码缺不一样，（因为不在同一个GeoHash区域块上），而近的GeoHash编码与我们不一致。
在当前点位于矩形的边界位置或者靠近边界位置时，与其最近的点可能处于边界另一侧的矩形内，这种情形下就无法匹配到最近的点。针对这种情况最直观的想法是把当前点所在矩形的周围八个矩形也包括进来，这样能保证输入的点集一定包括潜在的最近点。我们查询时，除了使用定位点的GeoHash编码进行匹配外，还使用周围8个区域的GeoHash编码，，再使用这8个点去取数据，最后再做merge、sort，这样可以避免这个问题。 8个点的算法：这个问题之前很困惑，怎么找效率最高，按照顺时针，8个方向：北、东北、东、东南、南、西南、西、西北，分别将当前位置的精度、维度的二进制提取出来，针对北的计算，则将维度+1，东北的则经度+1，维度+1,以此类推，最后再做组合计算，得到点的geohash。
如果geohash的位数是9位数的时候，大概为附近2米
a）在纬度相等的情况下：
经度每隔0.00001度，距离相差约1米； 每隔0.0001度，距离相差约10米； 每隔0.001度，距离相差约100米； 每隔0.01度，距离相差约1000米； 每隔0.1度，距离相差约10000米。
b）在经度相等的情况下：
纬度每隔0.00001度，距离相差约1.1米； 每隔0.0001度，距离相差约11米； 每隔0.001度，距离相差约111米； 每隔0.01度，距离相差约1113米； 每隔0.1度，距离相差约11132米。
Geohash :https://en.wikipedia.org/wiki/Geohash
Movable Type Scripts : http://www.movable-type.co.uk/scripts/geohash.html
使用 Apache Lucene 和 Solr 进行位置感知搜索 :http://www.ibm.com/developerworks/cn/java/j-spatial/
现在几乎所有的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分页。
第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 (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;
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(?, '%');
这样会比区间查找快很多，并且得益于geo_code的相似性，可以对热点区域做缓存。
geohash边界和角的问题可以使用geohash-java来解决。
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(Person Of Interest)的搜索，如酒店、美食、KTV、电影院等等，这种数据密度是很小，1公里内的酒店，能有多少家，50家都算多的，所以最终要看具体业务数据密度。
参考： http://casestudy.iteye.com/blog/2298333
http://www.bubuko.com/infodetail-2390939.html
https://blog.csdn.net/qq_22929803/article/details/51286842
https://blog.csdn.net/hylexus/article/details/78734745