title: HBase与时空索引技术
date: 2021-05-13 10:04:05
tags:

• HBase
• GIS

所谓时空数据，顾名思义，包含了两个维度的信息：空间信息与时间信息。空间信息，以地理位置点最为基础，还包括线、多边形以及更为复杂的多维结构。最典型的时空数据，莫过于移动对象的轨迹点数据，如每隔5秒钟记录的车辆实时位置信息。这类数据，在物联网领域司空见惯，在可预见的未来，这类数据将会出现爆炸性的增长。

用HBase存放时空数据

时空数据，尤其是移动对象位置点数据，结构简单，但关于吞吐量的要求却往往很高。单从这点信息来看，这类数据属于HBase的适用范畴。

先不谈论时间纬度与复杂的多边形数据，我们先从最简单的地理位置点数据开始，探讨一下如果用HBase来存储这类数据会遭遇哪些技术挑战。

地理位置点Point中包含两个信息：经度X与纬度Y，按照传统的思路，将一个Point存成一行数据，而经度X与纬度Y则分别是构成这行数据的两个列，可以为每一个Point设置一个ID，并以此ID作为数据RowKey。所有的Points在表中按ID字典顺序存放。

围绕地理位置点的典型的查询方式，如“查询某一个建筑附近有哪些酒店？”，按照刚刚表设计思路，数据如按主键ID顺序存放，某个建筑附近的所有酒店，它们在主键顺序上却未必是相邻的，因此，这个查询可能涉及扫描大量的无关数据。

可见，针对最简单的时空数据类型，传统HBase表设计思路已经显得非常低效，传统关系型数据库基于B-Tree的数据组织结构也更是疲于应对。再放大到整个时空数据的范畴，要支持的典型场景更为复杂：

• 查询某一个地理区域在某个历史时间范围内发生的关键事件
• 查询某一个地理区域的人流量、车流量信息
• 查询某一天上午先后在A，B，C三个地理区域出现过的具有某些特征的人
• 查询某嫌疑人在某一天的行动轨迹

归根结底，HBase中的数据按照RowKey单维度排序组织，而我们现在却面临的是一个多维数据问题。因此，HBase如果想很好的支持时空数据的存储，需要引入时空索引技术。

从上面的查询场景来看，原生HBase的访问接口难以直接支持这些能力，因此，时空数据领域需要更加专业的访问接口，这是GeoMesa项目存在的关键原因。

常见的时空索引技术

关于时空索引，已经有不少常见的技术，这里，我们主要介绍一下R-Trees、Quad-Trees、K-D Trees以及Space Filling Curve这四种技术。

R-Trees

R-Trees源自论文《R-Trees: A Dynamic Index Structure For Spatial Searching》，下面的图也源自此论文：

R-Trees基于这样的思想设计：

每一个空间对象，如一个多边形区域，都存在一个最小的矩形，能够恰好包含此时空对象，如上图中的矩形R6所包含的弯月形区域。这个最小包围矩形被称之为MBR(Minimum Bounding Rectangle)。

多个相邻的矩形，可以被包含在一个更大的最小包围矩形中。如R6、R9以及R10三个矩形，可以被包含在R3中，而R11与R12则被包含在R4中。

继续迭代，总能找到若干个最大的区域，以一种树状的形式，将所有的时空对象给容纳进去，如上图中的R1, R2。这样，整个树状结构，呈现如下：

从最小的矩形区域，到最大的矩形区域，就好比地图中的行政区域划分：村 -> 县 -> 市 -> 省份。查询时，先从锁定的最大区域开始，逐级缩小比例尺后，就可找到最终的对象。如若将上图中的R1与R2理解成两个平级的”行政区域”，却又存在本质的区别：不同的行政区域，并不存在相互重叠，而R1与R2却可能是重叠的。

R-Trees的定义：

\1. 每一个Leaf Node包含m到M个索引记录（Root节点除外）。

\2. 每一个索引记录是一个关于(I, tuple-identifier)的二元组信息，I是空间对象的最小包围矩形，而tuple-identifier用来描述空间对象本身。

\3. 每一个Non-leaf节点，包含m到M个子节点（Root节点除外）。

\4. Non-leaf节点上的每一个数据元素，是一个(I, child-pointer)的二元组信息，child-pointer指向其中一个子节点，而I则是这个子节点上所有矩形的最小包围矩形。

如上图中，R3、R4以及R5，共同构成一个non-leaf节点，R3指向包含元素R8，R9以及R10的子节点，这个指针就是child-pointer，而与R8，R9以及R10相关的最小包围矩形，就是I。

\5. Root节点至少包含两个子节点，除非它本身也是一个Leaf Node。

\6. 所有的Leaf Nodes都出现在树的同一层上。

从定义上来看，R-Trees与B-Trees存在诸多类似：Root节点与Non-Leaf节点，均包含限定数量的子节点；所有的Leaf Nodes都出现在树的同一层上。这两种树也都是自平衡的。

前面也已经提到了，B-Trees主要用来存放一维排序的数据元素，而R-Tree存放的则是多维空间数据元素。从查询方式上来看，两者也存在显著的差异：B-Trees更擅长于数据点查，它的设计并不利于数据的范围查询。基于空间元素的查询，却以范围查询为主，而且往往需要对多个子树进行并行查询，例如，在地图上划定某一个区域，查询这个区域内有哪些公园，可能有多个子树都与划定的这个区域存在交集。从这一点看来，R-Tree的搜索性能其实并没有很好的保障。

R-Trees有多种变种，如R±Trees，R*-Trees，X-Trees, M-Trees，BR-Trees等等，不再展开过多的介绍。

Quad-Trees

同很多数据结构类似，Quad-Trees也存在多种变种，最初的Quad-Trees设计源自论文《Quad Trees: A Data Structure for Retrieval on Composite Keys》，下图源自论文，是关于Quad-Trees的直观呈现：

上图中的A,B,C,E,F,G均为Point，以每一个Point作为中心点，可以将一个区间分成4个象限。

假设，先写入Point A，以A为中心，将整个区间分成了4个象限。

写入Point B，Point B位于A的东北象限中，同样，以B为中心，依然可以将A东北象限进一步细分为4个子象限。

写入Point C，Point C位于A的东南象限中，以C为中心，可以将A的东南象限细分成4个子象限。

……

任何新写入的一个Point，总能找到一个某一个已存在的Point的子象限，来存放这个新的Point。

整个树状结构呈现如下：

可见，Quad-Trees有几个鲜明的特点：1. 对于非叶子节点，均包含4个子节点，对应4个面积不一的象限。2.**不平衡，树的结构与数据的写入顺序直接相关。**3.有空的Leave Nodes，且所有的Leave Nodes则是”参差不齐”的(并不一定都出现在树的同一层中)。4.数据既可能出现在分枝节点中，也可能出现在叶子节点中。

因为Quad-Trees存在诸多变种，为了有所区分，上面提到的最简单的这种Quad-Tree，被称之为Point Quad-Trees。还有一种典型的Quad-Trees，被称之为Point Region QuadTrees(简称为PR QuadTrees)：

PR Quad-Trees中，每一次迭代出来的4个象限，面积相同，且不依赖于用户数据Point作为分割点，或者说，数据分区与用户数据无关。每一个划分出来的子象限中，只允许存在一个Point。

与Point Quad-Trees相比，PR Quad-Trees允许两份不同的数据集，拥有相同的分区信息。但PR Quad-Trees存在的问题也明显：1. 两个相邻的Points，可能在树的Level高度上相隔甚远。2.两份数据集如果追求相同的分区信息，可能需要进行足够粒度的分割，这可能导致空间浪费。

K-D Trees

K-D Trees是一种针对高维点向量数据的索引结构，一棵简单的K-D Tree如下图所示(原图源自James Fogarty的”K-D Trees and Quad Trees”，但为了更直观，关于分区分割线的线条做了改动)：

与Quad Trees思想类似，K-D Trees也是将整个区间进行不断分割，不同之处在于，Quad Trees每一次迭代，将一个区间分割成四个象限，而K-D Trees则是分成左右或上下两个区间。如上图所示：S1把整个空间分成了左右两个区间，左侧区间中，又被S2横向分割成了上下两个区间，而S3又在S2的分割基础上，将下部分分割成了左右两个区间，….

如果已经存在一批Points，则较容易针对这批数据构建出一棵趋于平衡的K-D Tree，如若接收实时写入的数据，或者说数据更新频繁，K-D Tree则难以维持平衡态，除非对整棵树进行重构。

Space Filling Curve

如果将一个完整的二维空间，分割成一个个大小相同的矩形，可以将Space Filling Curve简单理解为它是一种将所有的矩形区域用一条线”串”起来的方法，因”串”的方式不同，也就引申出了不同的Space Filling Curve算法。

比较典型的如Z-Order Curve：

再如Hilbert Curve:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-43z6zHOE-1620871556108)(data:image/gif;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABCAYAAAAfFcSJAAAADUlEQVQImWNgYGBgAAAABQABh6FO1AAAAABJRU5ErkJggg==)]

Space Filling Curve事实上是为空间数据提供了一种一维排序的方法，它拉近了空间数据与传统数据库的距离：因为这意味着可以使用传统的B-Tree或B±Tree索引，来存储空间数据。

我们再借助于Z-Order的迭代构建过程，来加深读者关于Space Filling Curve的理解：

如果将整个区间划分成4个象限，第一轮迭代就是将这4个象限利用Z-Order曲线连接起来：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zTNW3nCz-1620871556108)(data:image/gif;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABCAYAAAAfFcSJAAAADUlEQVQImWNgYGBgAAAABQABh6FO1AAAAABJRU5ErkJggg==)]

而后，将第一轮迭代中的每一个象限，再进一步细分成4个象限，这样共变成了16个区间。在第二轮迭代中，再将16一个小区间用Z-Order曲线连接起来：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zlvUOgjf-1620871556110)(data:image/gif;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABCAYAAAAfFcSJAAAADUlEQVQImWNgYGBgAAAABQABh6FO1AAAAABJRU5ErkJggg==)]

第三轮迭代再进一步拆分、连接，变成下图的样子：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DbbDkGxl-1620871556111)(data:image/gif;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABCAYAAAAfFcSJAAAADUlEQVQImWNgYGBgAAAABQABh6FO1AAAAABJRU5ErkJggg==)]

每一次迭代，都是在上一次迭代的”方格”基础上，将每一个”方格”拆成了4个”子方格”，这种思想与Quad-Tree的思路是一致的，尤其是PR Quad-Tree，因此，也可将Space Filling Curve理解成一种高效构建Quad-Tree的方式，但需要说明的一点是，Z-Order论文的发布时间要远早于Quad-Tree论文的时间。

GeoHash

GeoHash可以将Point编码成一个字符串，如：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vke3Ejyf-1620871556112)(data:image/gif;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABCAYAAAAfFcSJAAAADUlEQVQImWNgYGBgAAAABQABh6FO1AAAAABJRU5ErkJggg==)]

http://geohash.org这个网站提供了经纬度与Geohash的在线转换能力。从编码结果来看，可以发现三个特点：

1. 越高的精度，字符串越长，可对比上表中的P1到P3的Geohash值变化。

2. P3所表示的区域涵盖了P2，而P2涵盖了P1，这层关系，在生成的Geohash值中这样体现：

   “ws10rn6y”(对应P2)以”ws10rn”(对应P3)为前缀

   “ws10rn6yp9ms”(对应P1)以”ws10rn6y”(对应P2)为前缀。

3. 位置相近的点，生成的Geohash值也相似，如P2与P4，两者纬度相同，经度仅差0.001，在生成的Geohash值中仅最后一个字符有区别。

GeoMesa官方资料中，也给出了这样一个典型的例子：

针对 (-78.48, 38.03)，编码的过程，如下：

第1步：经度二分

规则：先将完整的坐标系统(-180.000 -90.000, 180.000 90.000)按经度中点0.000进行二分，如果处于左边则编码为0，处于右边，则编码为1。

结果：因 (-78.48, 38.03)处于左侧区间(-180.000, 0.000)，因此，实际编码为0。此时， (-78.48, 38.03)所处的区间被缩小为(-180.000 -90.000, 0.000 90.000)。

第2步：纬度二分

规则：基于第1步的结果，再将(-180.000 -90.000, 0.000 90.000)按纬度中点0.000进行二分，如果处于上侧则编码为1，处于下侧，则编码为0。

结果：因 (-78.48, 38.03)处于上侧区间(-180.000, 0.000)，编码为1，与第一步的结果结合在一起，编码变为”01″。此时， (-78.48, 38.03)所处的区间被缩小为(-180.000 0.000, 0.000 90.000)。

第3步：经度二分

规则：基于第2步的结果，再将(-180.000 0.000, 0.000 90.000)按经度中点-90.000进行二分，同样，如果处于左侧则编码为0，处于右侧，则编码为1。

结果：因 (-78.48, 38.03)处于上侧区间(-90.000, 0.000)，编码为1，与前两步的结果结合在一起，编码变为”011″。此时， (-78.48, 38.03)所处的区间被缩小为(-90.000 0.000, 0.000 90.000)。

第4步：纬度二分

……

就这样，经度纬度不断交替二分迭代，每一步的输出结果如下表所示：

关于上表中的Bounding Boxes的不断编码，可直观的体现在下图中：

通过Base-32 Encoding，可以将上表中的编码结果进一步编码成字符串。例如，基于Base-32编码规则：

因此，(-78.48, 38.03)的编码为01100 10110 01010 00000 10110，将其转换成对应的字符：

​ 01100 -> d

​ 10110 -> q

​ 01010 -> b

​ 00000 -> 0

​ 10110 -> q

连在一起，(-78.48, 38.03)的最终编码结果变为：dqb0q

经Geohash编码后，其顺序与Z-Order编码保持一致，因此，也可以将Geohash是针对Z-Order算法的一种编码机制。Geohash编码带来的显著优势是：以字符串字典顺序表达Z-Order顺序，利用字符串的前缀匹配规则，也可快速实现多边形区域的重叠计算，但在编码效率上却并无任何优势，如sfcurve项目中提供的Z2编码算法，性能要远高于Geohash算法。

哪种时空索引可应用于HBase?

HBase基于LSM-Tree架构，底层HFile文件以B+ Tree形式组织。在不影响HBase现有架构的基础上，我们来分别探讨一下各种时空索引与HBase结合的可能性。

从R-Trees的原始论文描述来看，它的设计是为了充分利用Disk Page的优势，这一点与B-Tree类似。它支持良好的数据随机写入能力，能够自平衡，从设计上来看，非常适合于矩形/多边形空间对象的存储。既然是致力于磁盘上的索引设计，对HBase现有架构带来较大的侵入性，即使能对HBase进行改造，与B-Tree类似的这种设计，已经被证明难以支撑高吞吐量数据写入。如果不做任何改造，我们只能考虑如何将R-Trees的数据映射到HBase的KeyValue模型中：HBase的数据按RowKey排序，从而能够按照RowKey快速检索，如果将R-Trees的数据以HBase原生数据形态组织，自然希望能提供一种方法，使得R-Trees中的数据排序方式与RowKey的排序一致，或者说，如何为R-Trees中的数据对象找到一种RowKey生成机制，使得R-Trees中的数据顺序就是RowKey的字典顺序。但我们知道，R-Trees中，其实已经弱化了数据对象”排序”的含义，一个节点与子节点之间，更多是一种包含于被包含的关系，一个空间对象可能归属于不同的分枝，这取决于那种划分方案更优，当一个Leaf Node承载的对象过多时，也可能出现Split。如果按照传统的树遍历的顺序来理解R-Trees中的对象排序，这种排序是不确定的。这意味着，我们无法构建出一种确定顺序的RowKey。

再来看一下K-D Trees：K-D Trees是针对高维点向量而设计，用来存储二维的Point数据，自然也能很好的应对。K-D Trees的结构，与数据的写入顺序强相关，也可以说，同样的一批数据，因顺序不同，所构成的树的结构截然不同，这个问题也存在于Point Quad Trees中，因树结构的不确定性，它们与HBase结合的最大障碍，依然在于如何将Trees中的数据映射到KeyValue模型中。

PR Quad Tree的分区则不依赖于数据本身，更与数据的写入顺序无关，但PR Quad Tree限制每一个Point都独占一个小方格的设计，使得每一个Point可能处在树的不同层次/高度中，而且随着数据的不断写入，同一个Point所处的高度可能会发生变化：如原来某一个方格中只有一个Point，但如果有新的数据写入后，这个方格需要进一步被分拆成4个新的子方格，原来的Point在树中的位置也发生了变化，因此，PR Quad Tree也无法直接应用于HBase。

如果对PR Quad Tree进行稍加改造：

1. 将完整空间经过X次迭代后，预先将其划分成4^x个小方格。
2. 所有的Point都必须存放在最小的方格中。
3. 不限制每一个小方格中存放的Points的数量。

这样，带来了三点”确定性”：树的层次是确定的，每一个小方格在树中的访问路径是确定的，每一个Point所属的小方格也是确定的。因此，只要我们存在一种方法，将每一个小方格的访问路径，映射成HBase的RowKey，就完美解决了时空Points数据存放在HBase中的问题，这种思路正是Spatial Filling Curve的核心思想。

我们提到了两种常见的Spatial Filling Curve: Z-Order Curve与Hilbert Curve。评价一种Spatial Filling Curve的优劣，有两个关键的维度：

1. 距离保留度：将二维空间对象映射成一维曲线后，两个对象在二维区间上如果是相近的，那么，在一维曲线中也应当是相近的。一个更优的曲线，理应更大程度上在一维曲线中维持对象在二维空间上的距离，或者说，应该有更高的距离保留度。对于查询而言，更高的距离保留度，也往往意味着更高的Caching命中率。
2. 编码复杂度：可以简单理解为将二维空间对象映射成一维曲线的计算复杂度。

Z-Order曲线在距离保留度上，略弱于Hilbert曲线，但在编码复杂度上，却比Hilbert曲线更低，这是GeoMesa选择Z-Order曲线的关键原因。

References

R-trees: A Dynamic Index Structure for Spatial Searching
The R±Tree: A Dynamic Index For Multi-Dimensional Objects
https://www.geomesa.org/documentation/
https://github.com/davidmoten/rtree
https://en.wikipedia.org/wiki/Z-order_curve
https://www.slideshare.net/shakil0304003/b-tree-rtree
https://en.wikipedia.org/wiki/Quadtree
https://github.com/davidmoten/rtree
https://github.com/varunpant/Quadtree
Comparison of Advance Tree Data Structures
Space-Filling Curves An Introduction
A dive into spatial search algorithms
James Fogarty: K-D Trees and Quad Trees

https://en.wikipedia.org/wiki/Space-filling_curve
http://geohash.org
https://github.com/geomesa/geomesa-tutorials
https://en.wikipedia.org/wiki/Geohash
Spatial Keys – Memory Efficient GeoHashes
GeoServer: CQL And ECQL
GeoServer: ECQL Reference
GeoMesa: Scaling up Geospatial Analysis

一、背景

近年来智能城市建设在云计算和大数据技术的推动下，取得了飞跃式的发展，产生了海量可记录的数据，如文本、视频、传感器读数等。每年移动互联网接入流量消费超过711亿GB，其中，80%的数据都与时空相关。北京出租车三个月内产生了远超790万条轨迹数据，NASA卫星数据档案库已经超过500TB。迅速产生的时空数据，背后蕴藏着巨大的对智能城市发展有用的信息。如，根据交通轨迹来优化交通信号灯的时间、实时提醒路况、辅助规划交通道路等。此外，时空数据还在农业、金融、环境、能源等方面拥有众多的应用。这一系列的时空应用，加快推动了时空数据处理的需求。然而，时空数据的产生速度和体量决定了传统数据库不能满足其存储和分析的需求。因此，需要利用分布式数据库管理这些海量的时空数据。

二、HBase存放时空数据

近年来快速发展的分布式技术可以为海量数据的存储与查询提供有效的支持。时空数据，特别是位置点数据，具有产生快、数量大的特点。因此，对吞吐量的要求往往很高。建立在Hadoop文件系统之上的分布式数据库HBase，基于谷歌的Big Table设计，可以提供快速随机读/写访问海量数据的能力。因此，很多企业都采用HBase管理海量数据。HBase中的数据按照RowKey单维度排序组织。然而，时空数据具有多维属性，至少具有经度和纬度两个维度，而分布式存储一般以键值对的形式组织数据，很难直接存储时空数据。因此，为了高效地支持时空数据的存储和查询，需要引入时空索引技术便于在分布式数据库中管理多维时空数据。传统关系型数据库主要基于B-Tree数据结构组织数据，可以很好地支持单维数值范围等查询，如查询属性A > 1000的记录。然而，对于时空数据，要支持的基础查询场景更为复杂：如

（1）查询某一个区域一段时间内进过的人数；

（2）查询某一个区域的车辆数；

（3）查询某罪犯某一天的行动轨迹；

（4）查询某传染病患者的密切接触者。

这些查询往往需要调用时空范围查询，如二维空间范围加一维时间范围，是多维度的范围。针对时空数据的特殊查询场景，已经有很多常用的索引技术，可高效地支持特定的时空范围查询。这里我们主要介绍R-Tree、Quad-Tree、K-DTree、以及Space Filling Curve、LSH这五种技术。

三、常见的时空索引技术

3.1 R-Tree

R-Tree是一种平衡树，它只在叶节点中存放指向数据的指针，由Guttman在1984年SIGMOD中提出[1]。Guttman首先提出了MBR的概念，即最小边界矩形Minimum Bounding Box，如图1所示，其用一个边平行于坐标轴的最小的矩形框住空间对象。在查询时，只需要先找到空间对象的MBR即可。找MBR的任务相对于直接寻找空间对象本身来说容易了很多。

图1 MBR

R-tree吸纳了B+tree的思想，对数据进行分割。多个相邻的MBR，可以被包含在一个更大的MBR中，如图2中R6、R9以及R10三个矩形，可以被包含在R3中，而R11与R12则被包含在R4中。因此，可以用一个更大的MBR框住内层的小MBR。继续迭代，总能找到若干个最大的区域，如图2所示。一层一层构建MBR的操作，非常类似B+tree的构建，最终以一种类树状的形式，将所有的时空对象给容纳进去，如图3所示。查询时，通过先找外层的MBR，再不断遍历相交的子层，我们便可以很快找到内层MBR的大概位置。

图2 R-Tree示意图

图3 R-tree结构图

R-Tree有多种变种，如R+-Tree，R*-Tree，X-Tree,M-Tree，BR-Tree等等，其提升主要是针对MBR的分割算法方面的, 本文不再展开介绍。

3.2 Quad-Tree

Quad-Tree的最初设计源自论文《Quad Trees: A Data Structure for Retrieval on Composite Keys》[2]。Quad-Tree在二维上将空间分为四组相同的子象限，且只有每个叶节点中会包含有关时空数据。Quad-Tree里的每个节点要么正好有4个子节点，要么就是没有子节点(为一个树叶节点)。如图4所示，是一种典型的Quad-Tree。同样地，Quad-Tree也可以表示为树状结构，如图5所示。

图4 quad-tree

图5 quad-tree树结构

执行空间查询时，首先从根节点开始检查子节点是否与查询范围相交，如果相交则继续检查子节点，直到达到叶子节点。如果不与查询范围相交，则不再继续检索其子节点。

3.3 K-D tree

与Quad Tree思想类似，K-D Tree也会将整个空间不断进行分割，最终得到较为合适的分割区域。不同之处在于，QuadTree每一次分割，都将当前区域分割为等大小的四个子象限。而K-D Tree则是分成左右或上下两个区间。K-D Tree根据每个维度上数据的方差，取最大方差的维度作为分割轴，并对当前数据按分割轴维度进行检索，找到中位数数据，再根据所有数据与中位数当前维度值的大小关系，确定其它数据所属分支。如图6中，从左边开始的第三根红色线将整个区域分割为了左右两个区间，从上开始的第一根蓝色线将上一步红色线分割出的右边区域再次分割成了两个区域。因为K-D Tree每一次分割都会得到两个子空间，所以可以得到类似二叉树的结构。因此，K-DTree的空间查询类似二叉树的遍历检索过程。

图6 K-D Tree

3.4 Space Filling Curve

空间填充曲线是一种降低空间维度的技术，是由意大利科学家皮亚诺于1890年首次构造出来的，并由希尔伯特于1891年正式提出的，之后空间填充曲线就得到了深入的研究和广泛的应用[5]。空间填充曲线可将高维空间数据映射到一维空间上，其通过有限次的递归操作将多维空间划分为众多的网格（如图7所示），再通过一条连续的曲线经过所有的网格。因“串”的方式不同，也就衍生了不同的SFC算法。其中，比较典型的为Z-Order、Hilbert Curve。如图7所示，Z曲线递归地将空间分成四个子空间，每一个空间分裂出的四个子空间分别按照图7（a）所示的方式从0到3编号，直到达到最大递归次数r，最大递归数控制着最小网格的大小。如果没有达到最大分辨率，则继续划分每一个子空间，并依次递归编码，如图7（b）所示。最终，每个最小网格都会有唯一的编码序列。我们通过一条曲线按照编码的字典序列将最大分辨率下的所有网格连起来，可以看到每一层的编码形成的形状类似字母Z。Hilbert曲线是一种能填充满一个平面正方形的分形曲线。如图8所示，Hilbert曲线通过把一个正方形空间不断的分成4个子空间，再把小正方形的中心点连接起来得到的曲线，即希尔伯特曲线。在希尔伯特曲线的编码映射中，使用U字型来访问每个空间，对分成的4个子空间也同样使用U字形访问，但要调整U字形的朝向使得相邻的空间能够衔接起来。

图7 Z-Order曲线

图8 Hilbert 曲线

评价一种SpatialFilling Curve的优劣，有两个关键的维度：

（1）空间特性保留度：SFC将空间对象映射到一维后，如果两个对象在二维空间上是相近的，那么，在一维曲线中也应该尽可能是相近的。因此，一个好的曲线，理应更大程度上使得在一维曲线中维持空间对象在二维空间上的空间邻近性。对于查询而言，更高的空间特性保留度，也意味着更高的命中率。

（2）编码复杂度：可以简单理解为将空间对象映射成一维的计算复杂度。

Z-Order在空间特性的保留度上稍微低于Hilbert曲线。但在编码复杂度上，Z-Order更低。因此，很多分布式技术采用Z-Order管理空间数据，如GeoMesa和JUST[7]。

3.5 LSH（Locality Sensitive Hashing）

LSH（局部敏感哈希）是一系列可以将数据从高维度映射到低维度，同时使得在高维度相近的数据在低维度也大概率相近的哈希函数。对于一个相似性函数s，局部敏感哈希族H是一组哈希函数，其对于任意两个对象有

即，对于，随机选取的哈希函数会使它们得到同一哈希值的概率与它们本身的相似度相近。局部敏感哈希最终希望得到满足下列条件的哈希表：

其中，表示p和q相似。表示p和q相异。根据实际场景，相似度的定义会有不同，局部敏感哈希算法设计也有不同，更多细节请查看文献[6]。

四、时空索引应用于HBase

HBase基于LSM-Tree架构，底层HFile文件以B+Tree形式组织。在不影响HBase现有架构的基础上，我们来分别探讨一下各种时空索引与HBase的结合方式。

从R-Tree的设计上来看，其充分利用了Disk Page的优势。因此，它支持数据的随机写入能力，并能够做到自平衡。它非常适合多边形对象的存储。但是，HBase的数据按Rowkey排序，并按Rowkey进行快速检索。因此，需要提供一种方法，使得R-Tree中的数据按照Rowkey字典排序。然而，在R-Tree的设计中弱化了对数据排序的功能。因为，其节点与子节点之间，更多的是一种包含与被包含关系。并且，当一个叶子节点承载多过数据时，还可能出现分裂的状态。因此，按照传统的树遍历顺序对R-Tree中的对象排序，会导致顺序不确定等问题，这意味着根据R-tree很难构建出一种很好的Rowkey。

对于Quad-Tree来说，其分区可不依赖于数据本身，也与数据写入顺序无关。但随着数据的不断写入Quad-Tree可能需要进一步拆成四个子空间，导致原有数据在树中的层次也发生变化。因此，Quad-Tree也不便于直接应用于HBase。但对其稍加改造过后便可很好的支持HBase。

（1）预先完成空间划分;

（2）所有的数据都必须存放在叶节点中；

（3）不限制叶节点的存放数据的数据量。

同样的办法也适用于K-DTree.

上面提到的方法可使Quad-Tree很好地支持HBase的思想，也可看作Spatial Filling Curve的核心思想。SFC首先会确定好树的最大层次，并且会通过一条曲线串联起最大层次的每一个空间，进而根据曲线访问的顺序确定每一个空间的编码，并映射为HBase的Rowkey。

LSH本身是一个哈希函数表，因此它可以很快速地将数据转换到一维上，进而组成Rowkey。

参考文献

[1] Guttman, Antonin. "R-trees: A dynamicindex structure for spatial searching." Proceedings of the 1984ACM SIGMOD international conference on Management of data. 1984.

[2] Finkel, Raphael A., and Jon Louis Bentley."Quad trees a data structure for retrieval on composite keys." Actainformatica 4.1 (1974): 1-9.

[3] Jaison. HBase与时空索引技术，http://www.nosqlnotes.com/technotes/hbase/hbase-spatial-index/

[4] 李喆. 空间索引技术，https://zhuanlan.zhihu.com/p/38597148

[5] 维基百科. 空间填充曲线, https://en.wikipedia.org/wiki/Space-filling_curve

[6] Lv, Qin, et al. "Multi-probe LSH: efficient indexing forhigh-dimensional similarity search." 33rd International Conference on VeryLarge Data Bases, VLDB 2007. Association for Computing Machinery, Inc, 2007.

[7] Ruiyuan Li, Huajun He, Rubin Wang, Yuchuan Huang, Junwen Liu, SijieRuan, Tianfu He, Jie Bao, Yu Zheng. JUST: JD Urban Spatio-Temporal Data Engine.The 36th IEEE International Conference on Data Engineering. (ICDE 2020)

一、问题背景

城市中超过80%的数据都与时空有关，如加油站点、出租车轨迹、交通路况等。这些数据多为半结构化和非结构化数据，并且需要管理的数据量巨大。

传统的时空数据库管理海量数据时会出现性能严重下降的情况，如带有PostGIS插件的PostgresSQL。HBase等具有高可扩展性的分布式数据库又不能直接管理时空数据。为此，GeoMesa提供了大量的时空索引工具管理时空数据。但是，它支持的时空类型不够全面，并且在有些场景下它提供的索引效率很低。因此, 我们在GeoMesa的基础上研发了JUST引擎。

我们提出了三种新颖索引，Z2T、XZ2T和time_range索引，加快了点时空查询、非点空间对象的时空查询，并提供了时间段范围查询。此外，我们实现了SQL接口，方便用户快速构建时空数据表和索引。我们还提供了九大时空数据模型和三个特定时空业务数据模型，并为它们默认建立了必要的时空字段和最合适的高效索引。

JUST系统论文已发表在ICDE会议上（数据库顶级会议之一），并且目前已落地雄安、南京、南通、宿迁等城市。您可以通过http://just.urban-computing.com/免费体验JUST公测版。

下面将介绍JUST系统的核心索引、数据模型、以及使用指南。

二、时空数据

随着互联网的发展，城市中产生了大量数据，其中超过80%的数据与时空有关，如空气质量报点读数、天气、出租车移动轨迹、实时路况等。这些数据都至少具有时间或者空间维度，并且可能还有其它属性维度。

从二维地理要素的几何特征上分，空间对象可分为点（如，加油站点）、线（如，路段）、面（如，行政区域）、网（如，路网）等对象。

从时间维度上分，可分为时间点（如，2020年11月10日 16时03分59秒）和时间段（如，早上8点至早上10点）对象。因此，包含空间或者时间的对象可抽象出六种基础数据类型（点、线、面、网、时间点、时间段）。由这六种基础类型根据时空属性的变化情况可组合出24种既包含空间也包含时间属性的数据结构（8种静态时空类型，16种动态时空类型）（见第3节）。

三、时空索引

通常，数据库会通过时空索引来管理时空数据，而在硬件资源固定的情况下，时空索引的好坏和使用方法会影响系统性能。带有PostGIS插件的PostgresSQL利用R-tree和GiST索引管理时空数据，但是这两种索引的效率在海量数据的场景下会极大的下降。HBase等具有高可扩展性的分布式数据库能支持海量数据的存储，但它们没有直接集成管理时空数据的索引。为此，GeoMesa提供了大量的时空索引工具方便HBase管理时空数据。但它支持的时空类型不够全面，并且在有些场景下，如时间跨度很大的查询场景，它提供的索引效率会很低。所以JUST引擎采用了GeoMesa提供的四种时空索引Z2、Z3、XZ2、XZ3，并自研了三种时空索引Z2T、XZ2T、time_range。此外，时空数据通常会有ID和属性。因此，JUST还提供了id索引、属性索引以及属性的二级索引。

下面，将为大家详细介绍JUST提供的时空索引（Z2、Z3、Z2T、XZ2、XZ3、XZ2T、date、time_range），以及两种非时空索引（id、attr）。其中Z2、Z3、Z2T索引用于支持点对象的空间范围查询和时空范围，它们要求对象必须有点对象。XZ2、XZ3、XZ2T索引支持非点对象的空间范围查询和时空范围查询，它们要求对象必须有非点对象。非点对象是线、面和网对象。它们具有不确定的空间形状。因此，大部分空间索引都利用能包含它们最小的矩形边界来近似表达它们，再通过如R-Tree、XZ2等空间索引来进行管理。但是R-Tree不适用于分布式场景，因为JUST只提供了XZ2、XZ3、XZ2T三种适用于分布式场景的索引。date索引为时间点建立索引，它们要求对象必须时间点对象，它可以加快时间等值查询和时间范围查询。time_range索引为时间段建立索引，它们要求对象必须时间段对象，它可以加快时间段范围查询。JUST还支持两种非时空索引，id和attr索引，它们可对非时空属性建立索引。如id索引可以加快id属性的等值、大于、小于等查询，attr可以加快属性的等值、大于、小于等查询。此外，attr索引还支持二级索引，它可以加快属性+时空的条件查询。

1. 点对象索引

Z2 索引：将二维空间点编码到一维空间，进而方便存储和查询点对象，它可以加快点对象的空间范围查询。具有几何类型Point的对象可创建Z2索引。Z2采用Z-Ordering编码技术，它将空间递归分解成为更小的四个子空间，直到到达最大递归层级（resolution），分解过程中得到的四个子空间采用类似字母Z的顺序依次从0编码到3。所有的空间点都将被其所在最底层子空间的编码表示。如下图中空间点p1和p2都被“333”表示，p3被“331”表示。

Z3索引：将二维空间点和时间点编码到一维空间，它可以加快点对象的时空范围查询。具有几何类型Point和时间属性的对象可以创建Z3索引。地理空间是明确的经纬度边界（-180，180），（-90，90）。但是，时间是没有边界的。因此为了能递归分解时间，我们从1970-01-01 00:00:00开始（计算纪元时间），将时间按照固定周期（time period）进行切分, 每个周期都会有确定的边界。JUST引擎可设置time period为day、week、month、year。我们用T表示一个时间周期，T.s表示该周期开始时刻，T.e表示该周期结束时刻。在一个时间周期里，Z3索引首先将T从中间(T.m)分开，如果时间点小于T.m，那么编码为0，否则编码为1。然后按同样的二分规则划分经纬度。因此，我们可用三位编码(时间在前，经纬度在后)来表示时空点所在区域。然后，递归划分子时空区域，直到达到最大递归层级。如图中所示，最大递归次数为r=3, time period为day(24小时)，时空点p（t:10,lng:-73.97,lat:40.78）在第一层r=1时处于“001” 区域（t:0，lng:0，lat:1），在第二层时处于“001” 区域的“110”子区域，最后在最大层级r=3时处于“001 110” 区域的“101” 区域。最终，我们用“001 110 101”来表示p.

然而，通常查询的时间范围的跨度占整个时间周期的比列远大于查询的空间范围占整个地球面积(510,100,000km2)的比列，因此查询时Z3索引可能在空间的过滤效果不明显。如，查询1 km x 1km空间范围在01:00~02:00 时间范围的数据时，覆盖的时间跨度占整个时间周期的比列(2−1)/(24) >> 查询空间范围占比(1x1)/510,100,000。因此，扫描范围的key可能会覆盖到很大的不需要查询的区域。

Z2T索引：针对Z3存在的问题，我们提出了Z2T索引，，它可以加快点对象的时空范围查询。。我们先对时间分区得到不相交的time period，然后在每个time period中能单独使用Z2索引得到该时间周期中时空点的空间位置。查询时，我们首先找到与查询时间范围相交的time period，然后在每个满足条件的time period下利用构建好的Z2索引检索满足条件的数据。通常，每个time period需要查询的空间范围不会太大，因此相比于Z3索引，Z2T索引减少了大量的无用扫描。

2. 非点对象索引（线、面、网）

XZ2 索引：XZ2索引使用XZ-Ordering来索引非点空间对象，它可以加快非点对象的空间范围查询。XZ-Ordering是Z-Ordering的一种扩展，用于索引空间扩展的对象(即非点空间对象，如线串或多边形)。如果具有非点几何形状的对象，则可创建此索引。它用于有效地回答非点空间对象的空间查询。如下图(a)所示，XZ-Ordering的子空间（图（b））由Z-Ordering的子空间（图（a））扩大一倍得到，然后XZ-Ordering索引利用其恰好能完全包含非点空间对象的最小子空间来表示这个对象，如图（c）中，o1由“303”表示，o2由“033”表示。

XZ3索引：xz3索引使用XZ-Ordering的三维实现来索引非点空间数据的空间位置和时间，，它可以加快非点对象的时空范围查询。如果对象具有非点几何形状和时间属性，则可创建此索引。它用于有效地回答具有非点空间和时间成分的查询。

XZ2T索引： XZ2T索引优化了XZ3索引，非它可以加快点对象时空范围查询。类似Z2T，它在每个time period里面建立了XZ2索引。

3. 其它索引

时间索引：date索引用于支持时间查询。要求对象必须有时间字段。它用于有效地加快具有时间查询的需求。

时间段索引：time_range索引可看作是XZ-Ordering的一维实现来索引具有时间段的对象。时间段索引要求对象必须有开始时间和结束时间。如果对象具有时间段属性，则可创建此索引。它用于有效地回答加快时间段范围查询的需求。

ID索引：ID索引使用对象id作为主键。它被用于有关ID的任何查询，例如：等值、大于、小于等。另外，某些属性查询可能最终也从ID索引中检索数据。

属性索引：属性索引使用属性值作为主索引键。它允许在不使用时空查询的情况下快速检索查询。属性索引可包括一个二级时空索引，因此它可以加快使用多个条件的查询。属性索引的二级索引支持Z2、Z3、Z2T、XZ2、XZ3、XZ2T、date、time_range。如查询某辆车是否在某个区域出现过，我们就对车牌号建立属性索引，并使用Z2索引对车辆产生的轨迹点建立二级空间索引，然后我们就可以根据车牌号和空间范围快速查询对应数据了。时间索引可当作一种没有二级索引的属性索引。

表1和表2总结了索引和基础对象的对应关系，表3总结了索引可以加快的查询场景。

四、数据模型

虽然第一章提到的六大基础类型能单独表示六种数据类型，并在第二章介绍了针对这些基础类型的索引。但是，六大基础类型并不能完全所有的时空数据类型，因为现实世界中还存在大量地同时具有时间和空间属性的对象。因此，我们利用六大基础类型的在空间和时间属性的变化情况，组合出了24种时空类型。如表4所示，如果对象的空间和时间属性都是静态的，那么存在8种静态时空类型。如表5和表6所示，如果对象的时空属性会动态变化，那么又可以划分出16种动态时空类型，其中8种为空间不变，读数随着时间变化的时空类型，8种为时空都在变化的时空类型。

1. 静态时空类型

样例：
时空静态点：具有空间点和时间点的数据，如：空气质量站点和其修建时间。
时空静态线：具有空间线和时间点的数据，如：道路和其修建时间。
时空静态面：具有空间面和时间点的数据，如：行政区域和其边界确定时间。
时空静态网：具有空间网和时间点的数据，如：路网和其修建完成时间。
时空段静态点：具有空间点和时间段的数据，如：加油站在下午1点至2点售出加油量。
时空段静态线：具有空间线和时间段的数据，如：某条道路在早高峰（早上8:00-早上10：00）的车流量。
时空段静态面：具有空间面和时间段的数据，如：北京大兴区早高峰人口流入总数。
时空段静态网：具有空间网和时间段的数据，如：早高峰北京路况。

2. 动态时空类型

样例：
空间静态时间动态点：不断产生读数的空间质量站点。空气质量站点的空间位置固定，但它会动态地在不同时刻产生读数。
空间静态时间动态线：道路经过的机动车。道路位置固定，但行驶在道路上的车会动态变化。
空间静态时间动态面：区域人流量。区域固定，但里面的人流量会动态变化。
空间静态时间动态网：城市动态路况。城市路网固定，但交通路况会动态变化。
空间静态时间段动态点：智能红绿灯指示信息。红绿灯空间位置固定，但它在不同时间段颜色不一样。
空间静态时间段动态线：道路车流量。道路位置固定，道路车流量不同时间段不一样。
空间静态时间段动态面：区域人流量。区域固定，但不同时间段的人流量会动态变化。
空间静态时间段动态网：城市路况。城市路网固定，但不同时间段的交通路况会动态变化，如早高峰。

样例：
时空动态点：GPS点。出租车产生的GPS报点，时间在变化，位置也随着变化。
时空动态线：最短路径或轨迹追踪。不同时刻，由于交通路径、天气、事故等，从A地到B地的最优路径可能在不同时刻不一样；出租车最近两分钟的行驶路线，时间在变化，行驶过的路线也随着变化。
时空动态面：火灾蔓延。火势蔓延，时间在变化，火势覆盖面积也会发生变化。
时空动态网：人口迁移网。人口迁移的地点可能会随着时间的变化而变化，进而可能会产生动态的网。
时间段动态点：停留点。停留的地点在发生变化，并且需要记录进入和离开停留点的时间。
时间段动态线：轨迹段。分段后的轨迹，每条轨迹段都具有线特性，并且都有开始和结束时间。
时间段动态面：驻留区域。驻留的地点在发生变化，并且需要记录进入和离开停留点的时间。
时间段动态网：铁路运行图。不同时间段的铁路运行图不同。

五、JUST插件类型

虽然第三章提到六种基础类型和24种既有空间又有时间的时空类型。但是实际的业务应用场景中，只有12种类型会经常使用，如表7九大常用时空类型和表8三种特定业务时空类型。参考表1、表2和表3，我们可以找出时空类型适合建立的索引以及可以加快的查询。但是，用户如果对它们的对应关系不熟悉的话，极容易创建错误的索引。因此，为了方便用户创建这些复杂的常用时空对象，JUST封装了9大常用时空类型和三种特定业务类型插件表，并为它们指定了合适的默认索引。表7和表8是JUST提供的插件表类型、名称以及创建的默认索引的参照表。

六、使用指南

为了方便用户快速管理时空数据，JUST提供了易用的SQL引擎，它可以让用户通过很简单的SQL语句建立时空数据表和时空索引。在建表时，JUST会根据表中包含的对象类型，自动创建对应表的所有默认索引，如创建时空点表时，JUST则会为该表创建Z2、Z3、Z2T、attr(attr+z3),id共三种索引。但是，索引表会占用磁盘空间，而且有些应用场景可能不需要某些查询功能，且在某些应用场景中，可能需要创建默认索引类型以外的索引。因此JUST支持通过userdata（用户自定义表参数）来需要创建指定的索引。注意，如果表中出现多个空间或者时间字段，默认使用建表语句中的第一个空间和时间字段建立索引。

1. 创建默认空间表

create table [表名](
[字段名] [空间类型],
…
)

例子：

create table point(
pPoint
)

2. 创建默认时空表

create table [表名](
[字段名] [空间类型],
[字段名] [时间类型],
…
)

例子：

create table non_point_time(
poly Polygon,
time Date
)

3. 创建指定索引表

create table [表名](
[字段名] [空间类型],
[字段名] [时间类型],
…
) userdata{
“geomesa.indices.enabled”:"[索引名]"
}

例子

create table non_point_index(
poly polygon,
time Date
) userdata {
“geomesa.indices.enabled”:“xz2t”
}

4. 创建时间索引表

create table date_table(
[字段名]Date:index=true,
…
)

5. 创建时间段索引表

create table [表名](
[开始时间字段名] Date:index=true,
[结束时间字段名] Date,
…
) userdata {
“geomesa.indices.enabled”:“attr”,
“geomesa.attr.type”:“time_range “,
“geomesa.xz3.timerange.key”:”[用于查询时间段字段名]”,
“geomesa.xz3.timerange.start”:"[开始时间字段名]",
“geomesa.xz3.timerange.end”:"[结束时间字段名]"
}

6. 创建空间时间段索引表

create table [表名](
[字段名] [空间类型],
[开始时间字段名]Date,
[结束时间字段名] Date,
…
) userdata {
“geomesa.indices.enabled”:“attr”,
“geomesa.attr.type”:“time_range “,
“geomesa.xz3.timerange.key”:”[用于查询时间段字段名]”,
“geomesa.xz3.timerange.start”:"[开始时间字段名]",
“geomesa.xz3.timerange.end”:"[结束时间字段名]"
}

例子

create table st_time_range_table(
p Point,
ts Date,
te Date
) userdata {
“geomesa.indices.enabled”:“z3”,
“geomesa.xz3.timerange.key”:“time_range”,
“geomesa.xz3.timerange.start”:“ts”,
“geomesa.xz3.timerange.end”:“te”
}

7. 创建ID索引

create table [表名](
[id字段名] [类型]:primarykey,
…
)
注：如果在userdata中设置了"geomesa.indices.enabled"，则必须加上”id”索引

例子

create table id_table(
fid string:primary key
)

8. 创建属性表

create table [表名] (
[属性字段名] [类型]:index=true
[非必要字段名] [空间类型],
[非必要字段名] [时间类型],
…
)userdata {
“geomesa.indices.enabled”:“attr”,
“geomesa.attr.type”:”[二级索引类型]”
}

例子

给属性a建立属性+点空间索引（z2）
create table attr_point_table(
astring:index=true,
geo Point,
time Date
) userdata {
“geomesa.indices.enabled”:“attr”,
“geomesa.attr.type”:“z2”
}

给属性a建立属性+点时空索引（z2t）
create table attr_st_table(
astring:index=true,
geo Point,
time Date
) userdata {
“geomesa.indices.enabled”:“attr”,
“geomesa.attr.type”:“z2t”
}

给属性a建立属性+非点空间索引（xz2）
create table attr_npoint_table(
astring:index=true,
geo Polygon,
time Date
) userdata {
“geomesa.indices.enabled”:“attr”,
“geomesa.attr.type”:“xz2”
}

给属性a建立属性+非点时空索引（xz2t）
create table attr_nst_table(
astring:index=true,
geo Polygon,
time Date
) userdata {
“geomesa.indices.enabled”:“attr”,
“geomesa.attr.type”:“xz2t”
}

给属性a建立属性+时间段索引（time_range）
create table attr_timerange_table(
astring:index=true,
tsDate,
teDate
) userdata {
“geomesa.indices.enabled”:“attr”,
“geomesa.attr.type”:“time_range”,
“geomesa.xz3.timerange.key”:“time_range”,
“geomesa.xz3.timerange.start”:“ts”,
“geomesa.xz3.timerange.end”:“te”
}

9. 创建插件表

（1）创建非SD插件类型表：SS表和DD表

–(pluginName = SSPoint/SSLine/SSRegion/DDPoint/DDLine/DDRegion)
create table <table_name> as
(
metaName1 dataType,
metaName2 dataType
)
[(
readingName1 dataType,
readingName2 dataType
)]
[userdata{“key”:“value”,“key”:“value”}]

插入时空静态插件类型（SS）：SSPoint/SSRegion/SSLine

• 默认字段：idString, oid String, geom Point/Polygon/LineString；
• 自定义字段：
  meta属性：表示静态空间对象的附加信息， 如LineString的长度；
  reading属性(可选)：表示表示空间对象的每个点的数据信息，如LineString的每个点的属性；
• 示例：create sspoint_table as sspoint (meta1String, meta2 Double)
• 注意：在创建表的时候最多两个括号，第一个括号里面是自定义meta字段，第二个括号里面是自定义reading字段；如果只有一个括号则认为是meta自定义字段，如果没有括号则认为没有用户自定义字段。SSPoint插件类型没有reading属性。

时空动态插件类型（DD）：DDPoint/DDRegion/DDLine

• 默认字段：idString, oid String, geom Point/Polygon/LineString, time Timestamp；
• 自定义字段：
  mete属性：表示整个空间对象随时间变化的读数信息。
  reading属性(可选)：表示空间对象的每个点上的读数信息。
• 示例 1：create ddline_table as ddline (lengthDouble) (point_deriction Double)
• 示例2：create ddregion_table as ddregion (areaDouble, regionName String)
• 注意：DDPoint插件类型没有reading属性

（2）SD插件类型表

–(pluginName = SDPoint/SDLine/SDRegion)
create table <table_name> as
(
metaName1 dataType,
metaName2 dataType
)
(
readingName1 dataType,
readingName2 dataType
)
[userdata{“key”:“value”,“key”:“value”}]

默认字段：idString, oid String, geom Point/Polygon/LineString, time Timestamp;
自定义字段: mete表示空间对象不随时间变化的信息；reading表示空间对象随时间变化的读数信息；
示例：create sdregion_table as sdregion (meta1String, meta2 Double) (reading1 Integer, reading2 Float)

（3）特定业务应用表

–(pluginName = Trajectory/RoadNetwork/RouteOfTrajectory)
create table <table_name> as
[(
metaName1 dataType,
metaName2 dataType
)]
[(
readingName1 dataType,
readingName2 dataType
)]

路网插件类型（RoadNetwork）

• 自定义meta字段：startidInteger, endid Integer, direction Integer, maxlanes Integer, level Integer,speedlimit Double, road_length Double
  用户还可以继续扩展meta字段。
• 示例：
  create roadnetwork_table as RoadNetwork (weightDouble, name String)

注意：在创建表时最多能有一个括号来扩展meta字段。

轨迹插件类型（Trajectory）

• 自定义meta字段如下：endtimeTimestamp, tid String, timeseries TimeSeries, startposition Point, endpositionPoint, point_number Integer, length Double, speed Double, signature Bytes
• 用户还可以继续扩展meta字段，比如区分是出租车轨迹还是行人轨迹，并且可以扩展自定义reading字段用来表示每个轨迹点的瞬时速度、方向、是否载客等信息。
• 示例：create trajectory_table as Trajectory (trajectorytypeInteger) (direction Double)

注意：在创建表的时候最多两个括号，第一个括号里面是自定义meta字段，第二个括号里面是自定义reading字段；如果只有一个括号则认为是meta自定义字段，如果没有括号则认为没有用户自定义字段。

RouteOfTrajectory插件类型（RouteOfTrajectory）

• 自定义meta字段如下：endtimeTimestamp, startposition Point, end_position Point, tid String, routesArray[RouteInTrajectory]
• 用户还可以继续扩展自定义meta字段，比如routeoftrajectory的长度、平均速度。
• 示例：create route_of_trajectory_table as RouteOfTrajectory(length Double, avg_speed Double)

注意：在创建表时最多能有一个括号来扩展meta字段。

七、查询需求

JUST为时空表提供了大量的时空索引和非时空索引，可以加快时空查询和一些非时空查询的效率。下面是JUST使用范围和属性查询的示例：

1. RangeQuery

（1）时间范围查询

select
*
from
date_table
where
time >= to_timestamp(‘2020-11-12 00:00:00’) and time <=to_timestamp(‘2020-11-13 00:00:00’)

（2）空间范围查询

select
*
from
point
where
pwithin st_makeBBox(110.0, 30.0, 110.7, 30.8)

（3）时空范围查询

select
*
from
non_point_time
where
polywithin st_makeBBox(110.0, 30.0, 110.7, 30.8) and time >=to_timestamp(‘2020-11-12 00:00:00’) and time <= to_timestamp(‘2020-11-1300:00:00’)

（4）时间段范围查询

select
*
from
time_range_table
where
time_range between to_timestamp(‘2020-11-12 00:00:00’) andto_timestamp(‘2020-11-13 00:00:00’)
或
st_ecql(“time_range during2020-11-12T00:00:00/2020-11-13T00:00:00”,time_range_table,local)

（5）空间时间段范围查询

st_ecql(“bbox(p,110.0, 30.0, 110.7,30.8) and time_range during2020-11-12T00:00:00/2020-11-13T00:00:00”,time_range_table,local)

2. 属性查询

select
*
from
attr_st_table
WHERE
a =“xxx” and geo within st_makeBBox(110.0, 30.0, 110.7, 30.8) and time>= to_timestamp(‘2020-11-12 00:00:00’) and time <=to_timestamp(‘2020-11-13 00:00:00’)

往期好文推荐：
一文读懂联邦学习的前世今生（建议收藏）
深度解读京东金融App（Android）的秒开优化实践
京东数科七层负载 | HTTPS硬件加速 (Freescale加速卡篇)