摘要: GIS中的地理特征是包括几何、属性、关系与操作在内的集合体。空间索引是特征操作中的重要组成部分。 当涉及数据文件的实时增加与劃除操作时,如GIS-T数据库中零维交通特征的实时增减,静态索引方法显然难以胜任。本文中,我们提出基于Hilbert空间排列码的平衡二叉...
GIS中的地理特征是包括几何、属性、关系与操作在内的集合体。空间索引是特征操作中的重要组成部分。
当涉及数据文件的实时增加与劃除操作时,如GIS-T数据库中零维交通特征的实时增减,静态索引方法显然难以胜任。本文中,我们提出基于Hilbert空间排列码的平衡二叉排序树零维交通特征动态索引方法。平衡二叉排序树中的关键字即Hilbert空间排列码。这种索引方法主要面向内存索引,由于Hilbert空间排列码的目标聚集特征,使空间上相近的零维特征尽可能地聚集存储,也使之适合于磁盘索引。与四叉树与K-D树内存索引方法相比,基于空间排列码的平衡二叉排序树索引节点的利用率很高,不会出现四叉树和K-D树中由于点目标的非均匀分布 或数据的读入顺序而产生的不平衡现象。而且目标的空间位置由关键字值决定,与树中的层次与位置无关,与四叉树和K-D树相比更易于维护,此外,由于四叉树中Key值与所处层次之间关系不定,对于经常跨越子象限边界的区域査询,也造成了从四叉树中提取满足条件的节点比较困难。
对于零维交通特征,在根据其一维交通特征偏移两 或二维坐标计算出对应Hilben空旬排列码后,首先对排列码排序,然后按图所示结构存储。
这样,当读入内存时,不必对二叉排序树做过多的左右平衡处理。这种方法在不涉及GIS-T零维几何数据的实时操作时,就是使索引文件与数据文件合二为一的过程。