GeoMesa源码学习:空间索引

拼搏现实的明天。 2022-03-30 10:40 523阅读 0赞

本文转自：[http://keep.01ue.com/?pi=298096&\_a=app&\_c=index&\_m=p][http_keep.01ue.com_pi_298096_a_app_c_index_m_p]

分布式空间索引可以说是GeoMesa的灵魂了，它直接决定了空间数据的：（1）行主键（2）数据分区与负载均衡（3）索引高效查询。所以说要想真正了解GeoMesa的核心代码，必须要把索引这一部分弄懂吃透。空间索引方法是一套完整切复杂的理论体系，建议读者在阅读本文之前先看这篇论文：

Böhm, Klump, and Kriegel. “XZ-ordering: a space-filling curve for objects with spatial extension.” 6th. Int. Symposium on Large Spatial Databases (SSD), 1999, Hong Kong, China. (http://www.dbs.ifi.lmu.de/Publikationen/Boehm/Ordering\_99.pdf)

下面进入正文。

### 1. 空间填充曲线（Space Filling Curve） ###

基于空间目标排序的索引方法的基本思想是按照某种策略将索引空间细分为许多均等的网格，并给每一网格分配一个编号，然后用这些编号为空间目标获得一具有代表意义的数字。这样，多维空间目标就可以背影射成一维的目标，从而也就可以使用现有的数据库管理系统中比较成熟的一维索引技术来提高对空间数据的快速查找和存取。问题的关键在于影射算法必须较好地保持多维空间目标间的临近关系以提供较好的空间查询性能。空间填充曲线（后面简称sfc）是一种降低空间维度的方法。sfc能够将高维空间中的数据映射到一维空间，使用经典线性索引结构存储数据。空间目标排序的技术很多，最常见的sfc是基于Z排序(Z-order)和Hilbert排序的空间索引技术，技术的区别主要在于建立的多维到一维的映射关系是否能够很好的保持多维空间目标间的临近关系。关于Z-order和Hilbert曲线本文不做详细阐述，请读者自己查阅相关文献。

**Z-order：**

![on_crawl_img_252F48_252F20180520214015_un_5b017abf5b6c1.png_a_crawl_c_index_m_obj][]

如图所示，我们将二进制编码的结果填写到空间中，当将空间划分为四块时候，编码的顺序分别是左下角00，左上角01，右下脚10，右上角11，也就是类似于Z的曲线，当我们递归的将各个块分解成更小的子块时，编码的顺序是自相似的（分形），每一个子快也形成Z曲线，这种类型的曲线被称为Peano空间填充曲线。

**Hilbert曲线：**

![on_crawl_img_252F48_252F20180520214015_un_5b017abfdb755.png_a_crawl_c_index_m_obj][]

Z-Curve sfc可以将多维的空间数据降为一维，空间内某个区域的点的Z 序值可通过其位置计算出来，Z-Curve 空间填充曲线将地理空间按Z 字形划分成不同的区域，同一区域内的空间对象Z 序值相等。Z-Curve 曲线定义为d 维空间Rd与一维空间I 之间的一一映射，其可以记作 Z：Rd→I。若点 p∈Rd，则象Z(p)∈I，也将象Z(p)称为点 p 的 Z值。d 维m 阶Z-Curve 曲线的映射算法对应的伪代码如下所述。

![on_crawl_img_252F48_252F20180520214016_un_5b017ac06b398.png_a_crawl_c_index_m_obj][]

在d 维m 阶Z-Curve 曲线的映射算法中外层循环for 的循环次数为m，内层循环for 的循环次数为d，则二重循环的执行次数为md，故d 维m 阶Z 曲线的映射算法的时间复杂度为O(md)。存储点p 需要长度为d 的数组，故d 维空间索引m 阶Z-Curve 曲线的映射算法的空间复杂度为O(d)。下图给出HBase in Action中的一个例子：

![on_crawl_img_252F48_252F20180520214016_un_5b017ac0c75e9.png_a_crawl_c_index_m_obj][]

注意：**偶数位放经度，奇数位放纬度。**

### 2. GeoMesa空间索引技术 ###

GeoMesa使用了基于Z-order的空间索引技术。具体实现请参见locationTech另外一个sfcurve工程。使用IntelliJ打开sfcurve工程，可以看到主要包含三个模块： api、hilbert以及zorder。api中定义了sfc操作接口，zorder与hilbert分别是api中各个接口的基于Z曲线与Hilbert曲线的实现。

![on_crawl_img_252F48_252F20180520214017_un_5b017ac15fe82.png_a_crawl_c_index_m_obj][]

首先我们分析一下api模块。api模块中一共包含三个类：SpaceFillingCurve2D、SpaceFillingCurveProvider以及SpaceFillingCurves。SpaceFillingCurve2D是一个trait，其中定义了所有sfc类需要实现的接口，其中toIndex是获取z值，toPoint是根据z值获取坐标，toRanges是根据MBR获取sfc所有被包含的range集合，用于row key扫描查询。

![on_crawl_img_252F48_252F20180520214017_un_5b017ac1b7cf4.png_a_crawl_c_index_m_obj][]

SpaceFillingCurveProvider提供了一个获取SpaceFillingCurve2D的工厂方法：build2DSFC。

![on_crawl_img_252F48_252F20180520214018_un_5b017ac21093f.png_a_crawl_c_index_m_obj][]

SpaceFillingCurves类中包含了使用SpaceFillingCurveProvider获取SpaceFillingCurve2D的标准业务逻辑：

![on_crawl_img_252F48_252F20180520214018_un_5b017ac298ddc.png_a_crawl_c_index_m_obj][]

基于api，sfcurve提供了zorder与hilbert两种实现，下面我们再来分析一下geomesa中使用的zorder的实现，打开zorder目录如下：

![on_crawl_img_252F48_252F20180520214018_un_5b017ac2e26d3.png_a_crawl_c_index_m_obj][]

在本模块中，ZOrderSFCProvider实现了api中的SpaceFillingCurveProvider，ZCurve2D实现了实现了api中的SpaceFillingCurve2D，通过ZCurve2D可以获取Z-order sfc的两种具体实现类：Z2与Z3，Z2为二维Z曲线，仅仅针对空间，Z3为三维Z曲线，同时考虑了空间与时间，它们有个共同的基类ZN，N代表维数：

![on_crawl_img_252F48_252F20180520214019_un_5b017ac345a94.png_a_crawl_c_index_m_obj][]

再了解了sfcurve中sfc的整体架构之后，我们再来分析一下z曲线的具体实现。

### 3. SFCurve中Z2的实现： ###

下面我们来看看sfcurve是如何实现Z2索引的。打开Z2类，如下图所示。Z2中有一个构造函数apply(x:Int,y:Int)。sfcurve中使用了一个比较巧妙的算法实现了GeoHash空间编码，即首先将lat与lon根据用户设定的精度转换为int型（调用normalize方法），生成对应的x：Int与y：Int，然后分别对x与y调用split函数，也就是将前31位的相邻两位之间插入0，最后对split(y)左移一位然后与split(x)取并，即得到对应的z-order曲线上的值（因为根据geohash的定义，偶数位放经度，奇数位放纬度）。

![on_crawl_img_252F48_252F20180520214019_un_5b017ac394bc4.png_a_crawl_c_index_m_obj][]

GeoMesa中并没有直接使用sfcurve中的SpaceFillingCurve2D，而是提供了geomesa-z3\_2.11模块，它基于sfcurve工程zorder模块提供了一些了sfc相关的工具类，如下图：

![on_crawl_img_252F48_252F20180520214019_un_5b017ac3ea150.png_a_crawl_c_index_m_obj][]

SpaceFillingCurve是GeoMesa所有空间填充曲线的基类，其子类Z2SFC对应的就是Z2：

![on_crawl_img_252F48_252F20180520214020_un_5b017ac4659a6.png_a_crawl_c_index_m_obj][]

我们接下来分析一下Z2SFC是如何生成Z-order code的：

![on_crawl_img_252F48_252F20180520214020_un_5b017ac4b03e8.png_a_crawl_c_index_m_obj][]

首先index方法会将经纬度进行一下normalize，转换成int类型，然后调用前面我们分析的sfcurve中的Z2的apply(x:Int,y:Int)方法然后构造Z2实例，GeoMesa就是通过返回的Z2对象实例计算具体Z-order code值得的

[http_keep.01ue.com_pi_298096_a_app_c_index_m_p]: http://keep.01ue.com/?pi=298096&_a=app&_c=index&_m=p
[on_crawl_img_252F48_252F20180520214015_un_5b017abf5b6c1.png_a_crawl_c_index_m_obj]: /images/20220330/ce4bdd4ee0544fe0a4ad6e7670763360.png
[on_crawl_img_252F48_252F20180520214015_un_5b017abfdb755.png_a_crawl_c_index_m_obj]: /images/20220330/d2fed462a67b49a79b1e22f376351262.png
[on_crawl_img_252F48_252F20180520214016_un_5b017ac06b398.png_a_crawl_c_index_m_obj]: /images/20220330/bbdc6c9a51c64bb68c8308c242756c5c.png
[on_crawl_img_252F48_252F20180520214016_un_5b017ac0c75e9.png_a_crawl_c_index_m_obj]: /images/20220330/809bff51d97d48fb88f4fe15369f8890.png
[on_crawl_img_252F48_252F20180520214017_un_5b017ac15fe82.png_a_crawl_c_index_m_obj]: /images/20220330/34ca4183e59b4cfcb33a69a9cf53fdb0.png
[on_crawl_img_252F48_252F20180520214017_un_5b017ac1b7cf4.png_a_crawl_c_index_m_obj]: /images/20220330/80e6bc5eb6494301afe543e27c892594.png
[on_crawl_img_252F48_252F20180520214018_un_5b017ac21093f.png_a_crawl_c_index_m_obj]: /images/20220330/634719c6dcc34e419eb74a1e79686eba.png
[on_crawl_img_252F48_252F20180520214018_un_5b017ac298ddc.png_a_crawl_c_index_m_obj]: /images/20220330/965ea324db0843e286ea7f3e1f31112f.png
[on_crawl_img_252F48_252F20180520214018_un_5b017ac2e26d3.png_a_crawl_c_index_m_obj]: /images/20220330/6fa769b6524145368cc38e8c7cccdcd7.png
[on_crawl_img_252F48_252F20180520214019_un_5b017ac345a94.png_a_crawl_c_index_m_obj]: /images/20220330/230853b1895f4c0788278aa91f4ab0e4.png
[on_crawl_img_252F48_252F20180520214019_un_5b017ac394bc4.png_a_crawl_c_index_m_obj]: /images/20220330/eb6ced1d11a44138919f7570a99d583c.png
[on_crawl_img_252F48_252F20180520214019_un_5b017ac3ea150.png_a_crawl_c_index_m_obj]: /images/20220330/570e96bfb1c74452aa8f7d5f4b310042.png
[on_crawl_img_252F48_252F20180520214020_un_5b017ac4659a6.png_a_crawl_c_index_m_obj]: /images/20220330/e3683990f1b647c4b61d8dfa93bda2c6.png
[on_crawl_img_252F48_252F20180520214020_un_5b017ac4b03e8.png_a_crawl_c_index_m_obj]: /images/20220330/5a5eacbb06064cf48569f30059437126.png