Redis GeoHash Data Structure

Posted on

Peano GeoHash(Geography Hash) 提供了一套存储、查询坐标元素的 API。可以高效的查询一定范围坐标内的元素。

Redis GeoHash 的底层是用 zset 实现的，其中 value 是 location 名，而 score 是 GEO 码，可以通过 GEO 码对经纬度快速索引。

  • 如何从纬度+经度转化为 GeoHash 中的 GEO 编码？

    1. 从三维到二维 将地球的球形表面抽象为一个二维球面。纬度的范围是[-90,90],经度的取值范围是[-180,180]。可以想象将整个地球外表的球面展开，成一个 180*360 的矩形
    2. 从二维到一维 利用Peano空间填充曲线算法将矩形平面编码。
      1. 将矩形空间平均切割成 4 部分
      2. 给四个区域分别编号：左下(00)、左上(01)、右下(10)、右上(11)
      3. 利用分形原理，将 00 继续分成四部分：左下(0000)、左上(0001)、右下(0010)、右上(0011)
      4. 重复 1、2、3 步骤继续分形下去，直到编码到所需精度。例如经过 10 次分形，生成 20 位的编号(如：11100111010010001111)来表示一个区域单元，其中包含了纬度和经度。
    3. 从一维到二进制存储 利用Base32编码方式，将上面生成的编号每 5 位对应一个 Base32 编码字符，生成一个 4 个字节的码。

  • 为什么要把坐标转为 GEO 码？——索引 我们对 int/string 类型比较时，可以根据元素比较、排序，快速的知道哪些元素是距离较近的，从而实现索引功能。空间索引也是一样的道理，如果能把空间转换为某种一维的快速比较的数据结构，就能实现空间索引。通过上面的 GEO 编码就能实现这个特性：只要按照类似 string 的比较方式，前面重复的编码越多，表示两个空间元素越接近。(后面会说如何解决边界突变问题)

  • 关于粒度 GeoHash 的 GEO 码其实并不能完全等价于输入的坐标，比如输入的坐标精确到了厘米级但是对应的 GEO 码只是到 10 米级别。所以在实际存储时，仍然会保存输入的坐标值。在查询时，先按找 GEO 码快速缩小范围，再通过具体坐标值进行比较。整个过程类似 HashTable 的 Key 的查找过程，先用 Hash 值查找，如果发生了碰撞(如果是开链法)则用真实值和链上每个元素进行比较。

  • Peano 分形编码示意图 Peano 这种类型的空间填充曲线的优点是将二维空间转换成一维曲线（事实上是分形维），对大部分而言，编码相似的距离也相近， 但 Peano 空间填充曲线最大的缺点就是突变性，有些编码相邻但距离却相差很远，比如 0111 与 1000，编码是相邻的，但距离相差很大。

  • 除 Peano 空间填充曲线外，还有很多空间填充曲线，如图所示 空间填充曲线 其中效果公认较好是 Hilbert 空间填充曲线，相较于 Peano 曲线而言，Hilbert 曲线没有较大的突变。为什么 GeoHash 不选择 Hilbert 空间填充曲线呢？可能是 Peano 曲线思路以及计算上比较简单吧，事实上，Peano 曲线就是一种四叉树线性编码方式。

  • 关于边界突变误差的修正 边界误差

    • 问题： 如图所示，红色是当前点，想找到距离最近的绿色点。可以很容易看出 WX4G2 的绿色点较近，但是由于曲线突变这个点被划到了 WX4G0 的边界外。如果只是简单的通过 GEO 码比较，则会误选 WX4G0 中的绿色点为结果。
    • 方案： 如图，通过 GEO 码比较找到区域后，把附近 8 个区域也包括进来，然后在其中查找坐标，这样就能通过较小的代价避免边界突变导致的误差。

  • Base32 组码 Base32

如图，是 Base32 的编码表，可以用一个字符(0-9、b-z、去掉 a,i,l,o)表示 0 ～ 31 之间一个值。Base32 编码的目的是用一个字符表示 32 位数据(32=2^5)，同时具有较好的可读性，编码中去掉和’0’相近的’a/o’以及和’1’相近的’l/i’。 例如”11100 11101 00100 01111”这个 GEO 码，把每 5 个 01 值分为一组转刚好转为一个 Base32 码(2^5)，对应为 28、29、4、15，结果为”wx4g”。反向即可转为 GEO 码。 “Base”中文译作”基数”，表示一种数制可以有多少个符号，Base32 意思是有 32 个字符可以用来表示数值中的一位。除了 Base32 外，常用的还有 Base64、Base16。

  • GeoHash Base32 编码长度与精度 Base32 当 geohash base32 编码长度为 8 时，精度在 19 米左右，而当编码长度为 9 时，精度在 2 米左右，编码长度需要根据数据情况进行选择。

  • GeoHash 只适合对点进行快速索引，而线、面、线段、多边形的空间索引最好用 R 树实现。MongoDB 中的 GeoJSON 对象以及 MySql InnoDB 中的空间索引，都是利用 R 树实现的。

  • http://geohash.org/<geohash-string>可以直接查询 GEO 码对应的经纬坐标，例如http://geohash.org/sqdtr74hyu0

  • 参考链接：GeoHash 核心原理解析、Redis GEO & 实现原理深度分析