白菜君の技术库

基于geohash算法-搜索附近的人

前言

目前空间索引的实现有 R 树和其变种 GIST 树、四叉树、网格索引等。 网格索引不再多提，使用普通的 hash 表存储地点和风格之间的映射来实现。今天要介绍的 GeoHash 算法实现的空间索引，虽然是以 B 树实现，但我认为它也借用网格索引的一部分思想。

php-geohash

GeoHash

  1. 从横向上将整个方形纸分为左右两份，左侧部分为标记为 0， 右侧部分标记为 1；
  2. 再将红点所在的部分划分为左右两块，再对红点位置做同样的标识，最后得出红点在横向上的标识为 10;
  3. 在纵向上对方形纸做同样的划分，左侧标识为0，右侧标识为 1，得出红点位置在纵向上的标识为 01;
  4. 将横向标识和纵向标识合并，规则为 纵向在奇数位，横向在偶数位 (也可纵横相反，但要在整个系统内保持一致)，得出红点在方形纸上的标识为 1001;

只标记一个方格显得看不出什么规律，如果我们把这些都空格都标识后会发现 被划分在角落里的四个方格会有同样的前缀.

同样的前缀意味着可以使用 B 树 索引查找有相同前缀的点作为附近的点，GeoHash 算法便是这些同样的前缀上面做文章。

  • 墨卡托投影

墨卡托投影，是正轴等角圆柱投影。由荷兰地图学家墨卡托(G.Mercator)于 1569 年创立。假想一个与地轴方向一致的圆柱切或割于地球，按等角条件，将经纬网投影到圆柱面上，将圆柱面展为平面后，即得本投影。墨卡托投影在切圆柱投影与割圆柱投影中，最早也是最常用的是切圆柱投影。

墨卡托投影简单地说，就是可以 把整个地球平面作为一个正方形来处理，当然地球平面不是严格的正方形，此投影在两极附近的点会有误差，本文专注于原理，纠偏就不多提了。

实现

按照墨卡托投影的平面，我们可以按照上面划分方格纸的方式来将整个地球表面划分为各个小方格。

如(116.276349, 40.040875)这个点的经度划分：

  1. 经度在 [-180,0) 范围内的标识为 0，经度范围在 [0, 180) 度的标识为 1;
  2. 继续划分，经度范围在 [0,90) 的标识为 0，经度范围在 [90,180) 的标识为 1;
  3. 这样，我们划分 20 次，方格的精度（见文末对照表）已达到 2m，得到经度的标识二进制串为11010010101011110111;
  4. 对纬度同样划分，得到纬度的标识二进制串为10111000111100100111;
  5. 我们对它组合，得到 40 位的二进制串11011 01110 00010 01110 11100 10111 01001 11111;
  6. 我们将这个二进制串使用 base32 编码（原理同 base64，可以见我的另一篇文章：WEB 开发中的字符集和编码，位编码映射表见下），得到 GeoHash 编码为 3OCO4XJ7;

那么 GeoHash 编码前缀为 3OCO4XJ7的地理点就是离 (116.276349, 40.040875)两米内的点。如果我们把地理位置点和其 GeoHash 编码存入数据库的话，我们要查找 附近两米点的点，只需要限定条件 geo_code like '3OCO4XJ7%'就行了;

边界值问题

边界点问题

可是最简版的 GeoHash 还有一个弱点，如下图：

如果每个方格的精度为 2km，那么我们直接按照前缀查询红点附近 2km 的点是查找不到离它很近的黑点的。

要解决这个问题，我们就需要所其周边八个方格也考虑上，将自身方格和周边八个方格内的点都遍历一次，再返回符合要求的点。那么如何知道周边方格的前缀呢？

仔细观察相邻方格，我们会发现两个小方格会在 经度或纬度的二进制码上相差1；我们通过 GeoHash 码反向解析出二进制码后，将其经度或纬度（或两者）的二进制码加一，再次组合为 GeoHash 码。

Redis 的 GEO 函数

版本限制：

Redis 的 Geo 系列函数需要>3.2 版本才支持。

问题

我们常见的需求是查找 n米 范围内的点，那么 n 米 与 GeoHash 码位数之间的映射如何实现呢？由于 GeoHash 码是由5位二进制码组成，每少一位，精度就会损失 2e(5/2)。

方法当然有的，我们将二进制 GeoHash 码直接索引就可以，但很长的索引长度会导致 B 树 索引查询效率会迅速下降。

方案

于是我们接着寻找解决方案，既然使用 base32 转换为 32 进制码 会不好控制精度，保持二进制又导致索引长度过长，那么进制位数和索引长度有没有一个平衡呢？

另外 Redis 的 sorted set 支持 64 位 的 double 类型的 score，我们把二进制的 GeoHash 码转为十进制放入 Redis 的 sorted set 中，不是可以实现 log(n)的查询效率了么。

redis 的 geo 也有一个很致命的弱点，那就是单一的搜索附近的人，还不能带其他的连带条件，所以需要二次过滤才可以，增加了额外的开销。

API

geoadd

geoadd 用来增加地理位置的坐标，可以批量添加地理位置，命令格式为：

GEOADD key longitude latitude member [longitude latitude member ...]

key 标识一个地理位置的集合。longitude latitude member 标识了一个地理位置的坐标。longitude 是地理位置的经度，latitude 是地理位置的纬度。member 是该地理位置的名称。GEOADD 可以批量给集合添加一批地理位置。
geopos

geopos 可以获取地理位置的坐标，可以批量获取多个地理位置的坐标，命令格式为：

GEOPOS key member [member ...]

geodist

geodist 用来获取两个地理位置的距离，命令格式为：

GEODIST key member1 member2 [m|km|ft|mi]

单位可以指定为以下四种类型：

  • m：米，距离单位默认为米，不传递该参数则单位为米。
  • km：公里。
  • mi：英里。
  • ft：英尺。

georadius

georadius 可以根据给定地理位置坐标获取指定范围内的地理位置集合。命令格式为：

GEORADIUS key longitude latitude radius [m|km|ft|mi] [WITHCOORD] [WITHDIST] [ASC|DESC] [WITHHASH] [COUNT count]

longitude latitude 标识了地理位置的坐标，radius 表示范围距离，距离单位可以为 m|km|ft|mi，还有一些可选参数：

  • WITHCOORD：传入 WITHCOORD 参数，则返回结果会带上匹配位置的经纬度。
  • WITHDIST：传入 WITHDIST 参数，则返回结果会带上匹配位置与给定地理位置的距离。
  • ASC|DESC：默认结果是未排序的，传入 ASC 为从近到远排序，传入 DESC 为从远到近排序。
  • WITHHASH：传入 WITHHASH 参数，则返回结果会带上匹配位置的 hash 值。
  • COUNT count：传入 COUNT 参数，可以返回指定数量的结果。

georadiusbymember

georadiusbymember 可以根据给定地理位置获取指定范围内的地理位置集合。georadius 命令传递的是坐标，georadiusbymember 传递的是地理位置。georadius 更为灵活，可以获取任何坐标点范围内的地理位置。但是大多数时候，只是想获取某个地理位置附近的其他地理位置，使用 georadiusbymember 则更为方便。georadiusbymember 命令格式为（命令可选参数与 georadius 含义一样）：

GEORADIUSBYMEMBER key member radius [m|km|ft|mi] [WITHCOORD] [WITHDIST] [ASC|DESC] [WITHHASH] [COUNT count]

geohash

geohash 可以获取某个地理位置的 geohash 值。geohash 是将二维的经纬度转换成字符串 hash 值的算法，后面会具体介绍 geohash 原理。可以批量获取多个地理位置的 geohash 值。命令格式为：

GEOHASH key member [member ...]

参考文献：https://www.cnblogs.com/zhenbianshu/p/6863405.html

算法 算法Redis