动态广义表空间索引方法

何 珍 文，郑 祖 芳，刘 刚，吴 冲 龙

动态广义表空间索引方法

何 珍 文，郑 祖 芳，刘 刚，吴 冲 龙

（中国地质大学（武汉）计算机学院，湖北 武汉 430074）

提出了一种新的动态空间索引结构X-Lists，设计实现了X-Lists的动态插入、动态删除、查找等算法，并进行了算法实验。X-Lists是一种支持高维点查询和区域查询的广义表，实验表明，X-Lists在索引构建与区域查找方面性能明显优于现有R-Tree及其改进索引结构。

空间索引;R树;广义表;X-Lists

0 引言

高效的多维空间索引是海量多维空间数据存储管理与有效调度的基础。由于空间数据的海量性及空间查询的高度复杂性，如何建立高效的多维空间索引实现海量空间数据的快速调度一直是人们研究的重点与难点问题之一。近30年众多学者提出了多种空间索引方法［1－3］，大致可分为线性索引、网格索引和树形索引三大类（图1），但目前研究使用最广泛的三维空间索引依然是R树系列索引方法。

线性索引是一种最直观简单的索引，但在大型空间数据库中访问效率较低，较少被采用。网格索引是将研究区域纵横分成若干个均等的小块，每小块都作为一个桶，将落在该小块内的地物对象放入该小块对应的桶中。当用户进行查询时，首先计算出用户查询对象所在格网，然后在该网格中快速查询所选空间实体。目前在3DGIS中常被用作一级索引与R树系列索引混合使用［3］。目前绝大部分的空间索引都是树形索引（图1），并且高维索引大都基于R-Tree［4］。R-Tree奠定了高维空间索引的技术架构［5］，是目前应用最为广泛的一种空间索引结构，许多商用空间数据库系统（如Oracle Spatial、IBM DB2 Spatial DataBlade、MySQL Spatial Extensions和MapInfo Spatial Ware等）均提供对R-Tree的支持，开放源码系统PostgreSQL也实现了R-Tree。近20多年来，许多学者致力于R-Tree的研究，在R-Tree的基础上衍生出了许多变种，比较典型的有R＋－Tree［6］、R＊-Tree［7］、压 缩 R-Tree［8］、Hilbert RTree［9］、ER＊－Tree［10］、CSR－Tree［1，2］等。

图1 空间索引方法分类［3］Fig.1 Classification of spatial index method

目前大量使用和研究的多维空间索引依然是以R-Tree及其衍生索引结构为主。广义表是一种非线性数据结构，是线性表和树的推广，被广泛应用于多项式处理、DNA计算机、表处理语言LISP、人工智能等领域。2010年，笔者对基于广义表的三维空间索引进行了研究，提出了R-Lists［11］空间索引结构，其边界矩形采用三维矩形，没有给出该结构实现的具体辅助算法。

本文以R-Lists为基础，对基于广义表的动态空间索引结构进行了研究，提出了一种新的动态索引结构X-Lists，设计实现了X-Lists的动态插入、动态删除、查找等算法，并进行了算法实验。研究表明：在内存空间占用方面，X-Lists的构建性能明显优于R-Tree和CSR-Tree;在索引构建时间方面，X-Lists与 R-Tree相 当，优 于 R＊-Tree和 CSR-Tree;XLists的查询性能在时间和空间占用上均明显优于R-Tree和CSR-Tree;X-Lists能有效地支持高维点查询和区域查询，具有广义表的一般属性及其优良性质，在具有高效的空间索引性能的同时，将更有利于对大规模空间数据集进行空间关系推理，或将为基于索引结构的空间关系的智能推理提供新的实现思路和方法。

1 X-Lists索引结构

广义表一般记为：

其中：GL（Generalized List）是广义表名称，n是其长度，ei是GL的一个元素，可以是原子（Atom）或子表（Sublist），这就决定了广义表的递归结构。X-Lists是一种带有最小包围边界并限定了表长度的广义表。这里的X代表单个或多个空间对象的任意形状的可进行叠置（Overlap）运算的最小包围体，常用的是超维最小边界矩形（MRB）、超球体或超维凸包体等。在高维点查询中一般采用超球体具有较高效率，在区域查询中一般采用多维最小边界矩形。在本文的算法实现中，如果没有特殊说明，最小包围体用最小边界矩形（MRB）表示。

在X-Lists中，每个原子元素对应一个空间对象SOj，记为：

其中：X＝（X0，X1，…，Xd－1）是一个d维最小包围体，d是空间维度;SO＿Identifier代表空间数据库中空间对象的唯一标识，在实现过程中一般采用空间对象ID或指针表示。对于X-Lists的子表，则对应一个约束在一定空间范围的空间对象集合或者集合的集合，记为：

如果X代表矩形，以 Guttman［4］给出的R-Tree的示例数据为例，且令m＝3，则采用X-Lists表示广义表XL为：

采用扩展线性存储方式，XL的存储结构如图2所示，标有数字的为原子，标有圆圈的为子表。

图2 Guttman示例数据对应的X-ListsFig.2 X-Lists for Guttman′s sample data

为了便于查找与更新实现，本文对扩展线性存储方式采用了双向链表形式，如果需要节省空间，也可以采用单向链表实现。后面的相关算法采用的是双向链表的实现方式。采用双向链表的扩展线性存储方式，X-Lists中的节点元素用C⧺语言描述如下：

其中：模板参数MBXVALUETYPE表示包围盒的分量类型，一般为float或double型;NUMDIMS表示空间维数;OBJTYPE表示空间对象或其唯一标识类型，当X-Lists用于文件系统时，OBJTYPE是一个带有文件指针和偏移位置信息的结构体，为阐述方便，本文将其定义为int型;Element的prev和next成员变量用于双向链表指针;type表示元素类型，如果为0表示原子，为1表示子表;当类型为原子元素时，obj用于唯一标识空间对象;当类型为子表时，sublist指向子表的头节点;bound表示子表或原子的最小包围边界，可以是超矩形或超球体等，本文采用对象Bound Box实现，只要实现了Bound Box的overlap、union等相关虚函数的几何实体都可以在X-Lists中使用，提高了X-Lists的可扩展性。

2 查找与更新算法

查找与更新算法是索引的核心算法，其效率直接决定索引的性能好坏。本文重点讨论X-Lists索引结构的查找、动态插入、动态删除等算法。假定空间对象的 MBX的集合为R＝｛Ri｜i∈［0，n］｝，当前待处理的 X-Lists为CXL＝｛C0，C1，…，Cj，…，Ck｝，其中0≤j≤k，且k＜m。

2.1 查找算法

查找算法（Searching）即在X-Lists中查找符合给定条件的原子元素。最常用的查询是空间范围查询，也即给定一个待查询的MBX值S，查询X-Lists中有哪些原子元素落在MBX中。设CXL的头指针为H，由于X-Lists是一种递归结构，因此，查找算法可以采用递归方式描述如下：

［Searching］

（1）以H为头指针，向后遍历链表，访问每个元素Cj;

（2）如果Cj对应的MBX与S相交，则进一步判断Cj的类型：如果是原子，则直接将Cj添加到查找结果列表中，如果是子表，以子表的头指针为H，递归调用查找算法［Searching］;

（3）如果Cj对应的MBX与S不相交，则指针后移一个元素，重复步骤2，直到j等于k为止。

2.2 插入算法

插入算法（Insert）是X-Lists的关键，是一种动态插入算法，设当前的X-Lists为CXL，其中已有k＋1个元素。现要在集合R中依次取出一个元素，顺次插入CXL中。

［Insert］

（1）设当前取出的元素Ri∈R，首先计算Ri与C是否相交;

（2）如果不相交，并且k＜m－1，则将Ri作为CXL的表尾元素添加;

（3）如果不相交，并且k＝m－1，则将CXL作为表头，Ri作为表尾，构建新的表，重新记为CXL;

（4）如果相交，并且存在Cj与Ri相交，则将Ri与Cj合并成新的Cj;这个合并过程是一个将Ri递归插入Cj中的过程，其终止条件是Ri插入Cj中的与Ri相交的子表中，或者直接成为Cj的原子元素，使得Cj本身也是一个X-Lists;

（5）如果相交，并且在CXL中不存在任何元素与Ri相交，若k＜m－1，则将Ri作为C的表尾元素添加;若k＝m－1，则将CXL作为表头，Ri作为表尾，构建新的表，重新记为CXL，并调用［AdjustInsert］算法调整列表CXL;

（6）重复上述步骤，完成R集合的插入，也即完成X-Lists的构建过程。

按照上述插入算法，图2中R8至R19的插入过程如下（当前插入元素用黑体表示）：

2.3 删除算法

X-Lists的删除分为两种：第一种是给定一个空间对象的唯一标识，在列表中删除该元素节点;第二种是给定一个区域，删除列表中所有落在该区域中的元素节点，其可以由第一种算法多次执行得到。本文重点讨论第一种动态删除算法。

［Delete］

（1）设CXL中要删除的空间对象为obj，调用［FindPath］算法，得到obj的路径栈S;

（2）如果［FindPath］查找失败，则表明CXL中没有obj元素，直接返回，否则继续;

（3）取出S的栈顶元素，赋值给head，pNode;

（4）如果S为空，则pNode是顶层表元素，在该层双向链表中删除节点pNode，重新计算总体包围边界;

（5）如果S不为空，则取S栈顶元素，赋值给pParentNode，则pParentNode是pNode的父表元素;

（6）在pNode所在的同级链表中删除pNode，并获取其头节点head，令pParentNode→sublist指向h;

（7）如果head所在链表只有一个元素，则用head替换pParentNode，该步可以直接调用［AdjustDelete］算法实现;

（8）将S中的所有元素顺次弹出，计算调整各个父表元素的包围边界，最后计算调整总包围边界后返回，该步可以直接调用［Adjust Boundary］算法实现。

2.4 其他辅助算法

在X-Lists中除了上述的查找（Searching）、删除（Delete）、插入（Insert）3个主要算法外，还有一些辅助算法。

2.4.1 元素定位 定位算法（Find）主要实现在XLists中查找指定的空间对象所在的元素位置。设要定位的空间对象唯一标识为obj，需要返回obj对应的节点元素element及其父表元素parent＿element，具体算法描述如下：

2.4.2 路径定位 路径定位（FindPath）算法用于实现在一个X-Lists中查找指定的空间对象所在位置及从节点上溯到最顶层父表的所有各层级的父表元素构成的路径。为实现该算法，首先实现［Find-Parents］算法。设要定位的空间对象为obj，当前列表的头节点为head，head的上级父表节点为head＿parent，采用栈结构存储父表节点路径。

（8）如果上述步骤都无最终返回TRUE，则将栈顶元素出栈，返回FALSE。

（9）返回的栈内元素即为obj节点的各层级的父节点元素。

该算法采用递归方式实现了obj各个层级的父表节点，但在栈内没有包含obj节点，［FindPath］算法则在此基础上将obj找到，并压栈处理。具体算法描述如下：

2.4.3 调整算法 调整算法［Adjust］主要针对XLists的动态插入、删除过程中出现的一些异常情况进行处理和优化，是一个算法集合。在X-Lists的更新中常会涉及节点的包围边界的调整问题，本文给出指定节点边界调整算法［AdjustBoundary］，该算法的输入参数是一个路径栈，栈顶元素为当前改动边界范围的节点元素。

（7）如果S不为空，重复执行步骤3～7，直到S为空;

（8）遍历pNextTopNode所在链表，重新计算每个元素的边界之和，赋值给X-Lists总边界范围。

上述边界调整算法相对比较简单，可以单独成函数供调用，也可以在插入、删除中直接嵌入。为了叙述清晰，在边界调整的地方直接调用［Adjust-Boundary］。

图3a显示的是图2的局部，如果删除R14节点，则以R13为头的链表只有一个节点，不符合X-Lists性质，需要进行调整，即把R13升级为其父表元素，并调整上层的包围边界，如图3b所示。删除过程中的调整算法描述如下：

（4）以S为参数，调用［AdjustBoundary］调整相关节点的包围边界;

（5）用pSubNode节点替换pNode节点。

图3 删除过程中的异常情况Fig.3 Anomalies in the process of deletion

图4显示了插入过程中经常出现一种异常情况。以图2所示的数据为例，如果R17先于R10插入，按照［Insert］的步骤5，则会出现如图4a所示情况，显然不如图4b所示的状况好，因为R8、R9、R17构成的包围边界范围远大于R8、R9、R10构成的边界范围，如果不进行调整，会大大增加X-Lists中节点重叠率和X-Lists的深度。调整的原则是使各个节点对应的子表的边界范围尽可能最小。这种异常情况一般出现在［Insert］算法的步骤5中，设当前节点为pNode，待插入的节点为element（对应图4a中的R10），如果element→bound与pNode→bound有重叠，不与pNode子表中的任何元素有重叠，并且pNode子表中的元素个数已经达到最大节点数m，在这种情况下则需要进行插入调整。

图4 插入过程中的异常情况Fig.4 Anomalies in the process of inserting

针对这种情况，调整算法设计如下：

3 算法实验与分析

为验证算法的有效性，对本文提出的算法进行了实验。实验设备为Sony VGN-SR48J，Intel Core2 Duo CPU 2.53 GHz，内存2 GB，操作系统为 Windows XP。由于CSR-Tree是以R＊-Tree为基类实现的，其性能高于R＊-Tree，为此，本文选择R-Tree和CSR-Tree与X-Lists进行对比分析，分别对RTree、CSR-Tree和X-Lists的构建算法和查找算法的时间和空间性能进行了测试。

测试数据集为随机生成数据。X-Lists和RTree一样，是一种动态多维空间索引结构，可以适用于高维查询，本文重点对三维数据集进行测试，结果见表1。

表1 X-Lists、R-Tree与CSR-Tree测试结果Table 1 Experimental results of X-Lists，R-Tree and CSR-Tree

为了更清楚地看出效率差异，将上述数据处理成折线图，见图5～图7。图5显示了R-Tree、CSRTree和X-Lists 3种索引结构的创建时间对比，随着空间对象个数的增加，X-Lists与R-Tree创建索引的效率基本相当，CSR-Tree由于需要进行聚类、排序操作，所以CSR-Tree的创建耗时要明显大于XLists和R-Tree。图6显示了R-Tree、CSR-Tree和X-Lists 3种索引占用内存空间情况的比较。由于CSR-Tree对数据集进行了聚类排序处理，因此CSR-Tree中的节点重叠率明显低于R-Tree。因此，对于同样的数据集，CSR-Tree的节点数要小于RTree，也即其内存占用量小于R-Tree的内存占用量，其节点数或内存占用量与空间对象数基本呈正比。X-Lists针对同一数据集创建的索引内存占用量小于CSR-Tree，明显优于 R-Tree，如图6所示。图7是 R-Tree、CSR-Tree和 X-Lists 3种索引查询效率的比较。由于CSR-Tree是对R＊-Tree的改进，随着数据量的增加，CSR-Tree相对于R-Tree的查询优势会变大。对于同样的随机数据集和同样的区域查询，X-Lists查询性能明显高于CSR-Tree和R-Tree（图7）。

图5 索引创建耗时Fig.5 The time cost of index creation

4 结论

本文对基于广义表的动态空间索引结构进行了研究，提出了一种新的动态索引结构X-Lists，设计实现了X-Lists的动态插入、动态删除、查找等算法，并进行了算法实验，结果表明：在内存空间占用方面，X-Lists的构建性能明显优于R-Tree和CSRTree;在索引构建时间方面，X-Lists与 R-Tree相当，优于R＊-Tree和CSR-Tree;X-Lists的查询性能在时间和空间占用上均明显优于R-Tree和CSRTree。

此外，X-Lists是一种广义表，R-Tree是 X-Lists的一个子集，能支持高维点查询和区域查询。由于广义表的优良性质，X-Lists在具有高效的空间索引性能的同时，更有利于对大规模空间数据集进行空间关系推理，或将为基于索引结构的空间关系的智能推理提供新的实现思路和方法。

［1］何珍文.泛型聚类排序3DR树批量构建算法［J］.地理与地理信息科学，2009，25（3）：12－15.

［2］HE Z W，WU C L，WANG C.Clustered sorting R-Tree：An index for multi-dimensional spatial objects［A］.GUO M Z，ZHAO L，WANG L P.Proceedings of 4th International Conference on Natural Computation（ICNC 2008）［C］.Jinan：IEEE Computer SOC，2008.348－352.

［3］何珍文.地质空间三维动态建模关键技术［D］.华中科技大学，2008.

［4］GUTTMAN A.R-Trees：A dynamic index structure for spatial searching［A］.YOUMARK B.Proc.of the ACM Int′l Conf.on Management of Data［C］.Boston：ACM Press，1984.47－57.

［5］张军旗，周向东，王梅，等.基于聚类分解的高维度量空间索引B＋-Tree［J］.软件学报，2008，19（6）：1401－1412.

［6］SELLIS T，ROUSSOPOULOS N，FALOUTSOS C.The R＋-Tree：A dynamic index for multi-dimensional objects［A］.VLDB［C］.1987.507－518.

［7］BECKMANN N，KRIEGEL H P，SCHNEIDER R，et al.The R＊-tree：An efficient and robust access method for points and rectangles［A］.CLIFFORD J，KING R.Proceedings of the ACM SIGMOD International Conference on the Management of Data［C］.Denver，Colorado：ACM Press，1991.322－331.

［8］KAMEL I，FALOUTSOS C.On packing R-Trees［A］.BHARAT B，TIM F，YELENA Y.Proceeding of the 2nd Conference on Information and Knowledge Management （CIKM）［C］.Washington DC，1993.490－499.

［9］KAMEL I，FALOUTSOS C.Hilbert R-Tree：An improved R

Tree using fractals［A］.BOCCA J B.Proceedings of the 20th International Conference on Very Large DataBases［C］.San Francisco：Morgan Kaufmann Publishers Inc，1995.500－509.

［10］周学海，李曦，龚育昌，等.多维向量动态索引结构研究［J］.软件学报，2002，13（4）：768－773.

［11］HE Z W，LIU G，WU C L.R-Lists：A dynamic spatial index structure based on generalized lists［A］.2th International Conference on Future Computer and Communication［C］.2010，9（2）：553－556.

Dynamic Generalized List Spatial Index Method

HE Zhen－wen，ZHENG Zu－fang，LIU Gang，WU Chong－long
（SchoolofComputer，ChinaUniversityofGeosciences，Wuhan430074，China）

A new dynamic spatial indexing structure named X-Lists has been presented in this paper.The X-Lists algorithms including the dynamic insertion，dynamic deletion and searching algorithms have been designed and implemented，and the algorithm experiments have been carried out.X-Lists is a type of generalized lists which supports multi-dimensional point query and range query.Experimental results show that，X-Lists in the two aspects of construction and regional searching is superior to the existing R-Tree index structure and its improvement index structures.

spatial index;R-Tree;generalized lists;X-Lists

P208

A

1672－0504（2011）05－0009－07

2011－03- 18;

2011－05－06

国家自然科学基金项目（41101368）;教育部高校博士点基金项目（20100145110009）;中央高校基本科研业务费专项资金资助项目

何珍文（1978－），男，博士，副教授，主要研究领域为数据库技术、空间信息科学与技术。E－mail：zwhe＠foxmail.com