gms数据库管理系统中时空索引的分析与实现

《gms数据库管理系统中时空索引的分析与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、重庆邮电大学硕士论文第一章绪论第二，通过阅读STOIRM，NT中和空间索引R树相关的源代码，详细分析和R树相关的其它模块的接口关系。因为要在SToRM，NT中实现TPR*．Link树必须首先了解索引如何在空间数据库管理系统中实现，以便了解要对索引进行哪些相关操作。第三，TPR*树没有加入右链结构，要考虑引入这种结构后，对查找、插入、删除算法的影响。第四，在S1DRM，NT中设计并实现TPR*一Link树。使得在现有S1’oRM仆『T系统的基础上，实现对移动物体现在和将来位置的查询。1．4论文组织结构本文共分七章，各章的内容安排如下：

2、第一章主要介绍国内外研究现状和研究意义。第二章主要介绍时空索引的基本概念和基础理论。第三章分析和比较几种索引移动物体现在和将来位置的典型索引结构，分析的目的是了解当前索引的现状、优势、缺陷，从中选取最佳方案。第四章详细分析了TPR*树的索引结构，索引操作。TPR·树在索日l移动物体时的主要优势以及存在的问题。第五章给出TPR*．Link树的索引结构的设计，查找、插入算法以及相关证明。第六章实现TPR*．Link树的基本操作，包括添加的数据结构、STORM，NT接口函数、实验结果和性能分析。第七章总结。重庆邮电大学硕士论文第二章时空索

3、引的基础理论从空间数据库中获得时空数据的有效方法，经常是通过使用时空索引完成的。它可以用来快速访问一条特定的时空查询所请求的数据，而无需遍历整个数据库。2．1时空索引的概念索引文件是用来提高数据文件查询效率的辅助文件。时空索引是从空间数据库中获得数据的有效方法。时空索引用一组桶(bucket)(通常对应二级存储的页面)来组织对象。每个桶有一个关联的桶区域，即包含了存储在桶中全部对象的一部分空间。桶区域通常是矩形的。对于点数据结构来说，这些矩形数据结构是不相交的，它们将空间分成每个点正好属于一个桶。对于一些矩形数据结构来说，桶区域可能

4、是交叠的。通过引入时间维表示每个对象的动态属性。2．2时空索引主要特点’}／时空索引要处理的数据具有：数据量大、多维和随时间变化的特点。空间数据库管理系统就是为处理海量空间数据而设计的。时空索引也不例外。空间数据的一个低分辨率的美国卫星图像就会消耗30兆磁盘的空间。正是因为空间数据量太大，它甚至都不能用一个中等规模的二级存储来装载，数据会溢出到三级存储中。读取数据时花费在访问随机存储器和磁盘的时间是不可同日而语的：前者大约是后者的十万分之一。这个比率还在逐年降低。时空索引的设计必须能迅速找到需要查询的数据，尽量减少内存和磁盘问的访问

5、速度。空间数据一般都是二维或更高维的。传统索引的实现主要依赖于索引域排序而存在。空间数据如果分类和排序，就会丢失空间的相邻性。如图2．1所示：图中有一个按行排序的网格。现在考虑4的相邻数字，在这个网格里4的相邻数据是3、7和8，但是如果按照排序的顺序来存储，它的相邻数字就成了3和5。因而，排序会破坏原有的相邻关系。值得一提的是，没有哪一种全排序可以安全保持空间的相邻性。由于多维空间不存在自然排序，在关系数据库管理系统中用的最广泛的索引B树，也就无法直接用于创建空间对象的索引。为了避免空间对象在自然排序方面的不足，必须从根本上修改B树

6、的思想，以适应扩展的空间对象。R树的数据结构是最早的专用于处理多维扩展对象的索引之一。重庆邮电大学硕士论文第二章时空索引的基础理论l23456789lOll121311IS16图2．I对多维数据的行排列时空数据是随着时间不断变化的，或者是速度的大小，或者是速度的方向。2．3R树的索引结构基于数据分区的时空索引都是在R树基础上发展的。索引R树(区域树)是一种利用B树的某些本质特征来处理多维数据的数据结构。B树的结点有一个键的集合，这些键把线分成片断，沿着那条线的点仅属于一个片断。如图2．2所示。B树因此很容易地找到点。如果把沿线各处的

7、点表示成B树结点，就能够确定点所属的唯一子结点，在那里可以找到该点。—_{—}_————_{——H图2．2B树结点沿线把键分成不相连片段另一方面，R树表示由二维或更高维区域组成的数据，称为数据区。一个R树的内结点对应于某个内部区域，或称“区域”，它不是普通的数据区。原则上，区域可以是任何形状，虽然实际中它经常为矩形或其他简单形状。R树的结点用子区域代替键，子区域表示结点的子区域的内容。如图2．3显示了一个与大矩形相关联的R树的结点。虚线表示的矩形表示与它的子结点相关联的予区域。子区域没有覆盖整个区域，只要把位于大区域内的所有数据区都

8、完全包含在某个区域中就合乎要求。进一步说，尽管希望部分重叠更小，子区域允许有部分重叠。R树中的最小外包矩形用来表示对象。R树有以下几条特性：1)每个叶结点包含m至M条索引记录(其中m