4.2　要素集的空间近似查询

对于空间数据集D,在进行空间可视化查询时,需要同时满足空间条件W与时间约束t(或误差约束ε,或数量约束＃),一般的查询思路是分别取得对所有地理对象的空间条件与约束条件的处理结果,然后进行连接。该方法在大多数情况下效率不高,这是因为空间条件的查询结果与约束条件的结果可能数据量非常大,对两个大规模的空间结果集进行连接将同时耗费计算资源与I/O资源。因此,可以从查询处理的开始就同时采用空间条件和约束条件筛选结果,这也意味着索引建立时必须综合考虑空间维度与误差维度。

空间近似查询根据底层存储系统的不同而分为两种处理方案,一是内存模型,二是关系模型。内存模型是指基于块设备和文件系统,顶点层次结构在内存中采用内存指针引用的形式表达,在文件中采用偏移位置引用的形式表达。关系模型使用记录(行或者元祖)进行存储,顶点层次结构在关系模型中的表达有多种可选方案,包括嵌套集、邻接表、物化路径等。根据查询模式的不同,这些方案具有不同的性能表现,实际使用时应考虑应用目标选择方案。以关系数据库为基础进行空间近似查询处理实现具有通用、稳定、可扩展性强等特点。(https://www.daowen.com)

本书第3章采用物化路径的解决方案,即顶点层次结构中的每个顶点都关联上从根节点到其的路径信息,其最大的优势在于排序非常方便。在查询方法的实现中,根据实际的顶点层次结构所基于的存储系统的不同建立两类索引结构,分别对应于文件系统与关系数据库,以下分小节说明这两类实现中值得关注的细节及空间条件与近似条件联合索引的设计。