基于动态哈希的格网法空间数据库索引技术 毕业论文.docx

本科毕业论文（设计）题目：基于动态哈希的格网法空间数据库索引技术姓 名： 学号： 20081001887院（系）：信息工程学院 专业： 地理信息系统 指导教师： 职称： 讲师 评 阅 人： 职称： 2012 年 5 月学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。本人完全意识到本声明的法律后果由本人承担。作者签名： 年 月 日 学位论文版权使用授权书本学位论文作者完全了解学校有关保障、使用学位论文的规定，同意学校保留并向有关学位论文管理部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权省级优秀学士学位论文评选机构将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1、 保密 ，在_年解密后适用本授权书。2、 不保密 。（请在以上相应方框内打“”）作者签名： 年 月 日 导师签名： 年 月 日 摘要 空间数据库索引技术是对存储在介质上的数据位置信息的描述，用来提高系统对数据后去的效率。空间数据库索引技术的提出是两方面因素所决定的：其一是由于计算机的体系结构将存储器分为内存和外存两种；其二是空间数据库所表现的空间数据多维性使得传统的数据库索引技术（如b-树等）并不适用，因为传统的数据库索引技术所针对的字符、数字等传统数据类型是在一个良序集之中，即都是在一个维度上，集合中任给两个元素，都可以在这个维度上确定，其关系只可能是大于、小于、等于三种1。而基于动态哈希的格网法是众多空间数据库索引技术中的一种。由于哈希索引能够根据查找关键字通过哈希函数直接定位查找记录，因此哈希索引被广泛应用于现有的数据库管理系统中。动态哈希是一类能根据需要而优美地扩充和收缩文件空间的哈希方法,它为现代数据库系统中,高效地组织和处理大型动态文件提供了一个新途径。基于动态哈系的格网方法的基本思路是将索引空间划分为相等或不相等的一些小方格网，与每个格网相关联的空间目标则存储在同一磁盘页，而格网的访问地址则可以直接通过求数组下标或某种算法得到。关键字： 动态哈希、格网法、空间数据库索引技术 abstract the spatial database is stored in the index technology to the data on the medium position information description, used to improve the system for the efficiency of data after. the index of the spatial database technology is put forward two aspects of factors: one is the system structure of the computer will be divided into memory and memory crt two; second is the spatial database of space data show that the traditional database multidimensionality index technology (such as b-trees, etc) is not applicable, because the traditional database index technology for characters, numbers of traditional data types are in a good order sets in, or in a dimension, set to the two elements of, can be determined in this dimension, the relationship between can only be larger than, less than, equal to three. based on dynamic and hash of the grid method of spatial database is one of the index technology. due to hash index according to find key words through the hash function directly positioning search records, so hash index to be widely used in the existing database management system. dynamic hash is a kind of can according to the need and elegant grace of the expansion and contraction of the hash file space method a dynamic hash, it for modern database systems, organization efficient and dealing with large dynamic file provides a new way. based on the dynamic, the grid method is the basic thought of the index is divided into space will be equal or not equal a few small squares nets, and each grid linked to the space the goal is in the same disk storage page, and grid access can be directly address by calculating an array subscript or some kind of algorithm to get. key word：dynamic hash、grid method、space database index technology 目录摘要iii第一章 绪论11.1空间数据库的起源和发展11.2空间数据库索引技术的现状11.3现今主要的几种空间索引技术21.3.1基于二叉树的空间索引技术21.3.2基于四叉树的空间索引技术31.3.3基于b-树的空间索引41.3.4基于空间目标排序的索引方法41.3.5qr-树51.4论文的组织结构5第二章 关于动态哈希方法62.1关于动态哈希方法的介绍62.2动态哈希法的分类7第三章 基于动态哈希的格网法的空间索引技术93.1网格文件93.1.1网格文件及其查找93.1.2插入103.1.3删除113.2 r-文件123.3 g树153.3.1 g树的空间模型153.3.1.1 g树的总体结构153.3.1.2 g树对n维对象的支持173.3.2 g树上的操作算法173.3.2.1树的构造173.3.2.2减少拐弯数的策略183.3.2.3 g树算法的讨论193.4 基于动态哈希的格网法的空间索引技术的分析203.4.1关于网格文件中的分析203.4.2关于r-文件的分析203.4.3关于g树的分析21第四章 基于动态哈希的格网法索引技术的发展前景234.1基于动态哈希的实际应用234.1.1基于动态哈希路由的peer-to-peer网络234.1.2 基于动态哈希树的流量跟踪算法234.1.3基于哈希函数高速网络入侵检测负载均衡算法研究244.1.4基于动态哈希函数的虚拟网格的过滤算法和p-stable分布244.2基于动态哈希的格网法的索引技术的发展24第五章 结束语26致 谢27参考文献：28中国地质大学2012年本科生毕业论文第一章 绪论1.1空间数据库的起源和发展近年来，空间数据信息在国内外各行业信息处理各个行业中的比重不断地上升，特别是与空间及地理分布数据密切相关的地理信息系统(gls)在20世纪90年代，广泛的应用于众多的业务领域中。由于地理信息系统中所需的处理的数据太多而且过程繁琐，所以如何使得未来的空间数据库系统能够快速便捷地获取不同来源的分布式数据，将这些空间数据集中分析，且进行网格计算，是空间数据库系统面临的一个重大挑战。实现空间数据和服务的共享是目前地理信息系统发展的主要方向之一，在实现技术上的研究主要集中在两个方面：1、面向对象技术，2、中间件技术。衡量空间数据库性能最重要的一项指标就是能够快速地响应用户提交的空间查询要求，而空间查询操作往往涉及海量的空间数据，以及需要对空间数据进行复杂而且高代价的几何操作。空间数据是某个空间框架中对象的位置信息。空间数据是多维的，它不仅要表达空间目标的属性信息，而且要存储目标的几何信息以及目标间的空间关系。一般而言，空间数据具有以下的特征:1、空间性，2、抽象性，3、多尺度与多态性，4、多时空性，5、非结构化特征，6、空间关系特征，7、分类编码特征，8、海量数据特征2。目前成熟的商用数据库是基于关系模型的数据库系统。空间数据库是一个存储空间数据和非空间数据的数据库系统，其数据模型和查询语言能提供空间数据类型，可以进行空间索引，且提供空间查询和其它空间分析方法。总之，空间数据库具备以下的特征:1、能够表达空间特征，2、空间数据具有多层次性，3、满足多粒度，4、能够描述非结构化特征，5、具备高效的空间数据索引技术。1.2空间数据库索引技术的现状由于实际应用的需要，近几十年来，国内外的学者十分重视空间索引的研究，相继地提出了多种空间索引结构与索引方法。如表1.1所示，概括介绍了空间数据库索引技术的历史研究情况，揭示了空间数据库索引技术目前发展的趋势和热点问题。基于不同的理论基础，空间数据库索引技术一般地可被划分成为四类:基于二叉树的空间数据索引技术、基于b一树的空间数据索引技术、基于哈希的空间数据索引技术和基于空间目标排序的空间数据索引技术。不过目前业界普遍认同的主流的空间数据库索引技术一般均采用树状索引结构3。表1.1空间数据库索引技术的研究历史研研究年代研究成果基于二叉树基于b-树基于哈希基于空间目标排序1984年kd-树r-树grid-文件基于位置链四叉树1986年1987年skd-树r*-树bang-文件等z-排序1988年1989年lsd-树cell-树、hb-树plop-哈希等1990年gbd-树r*-树、greens树r-文件等1992年1996年tv-树、k-树等filter-树1.3现今主要的几种空间索引技术1.3.1基于二叉树的空间索引技术二叉查找树是一种基本的索引数据结构。在随机情况下，其平均长度为1+4logn；平衡二叉查找树的平均查找长度为logn，它具有很好的查找性能。因此，二次查找树被采纳并予以推广，用于重复地划分数据空间，以期达到缩减查找空间、提高查找性能的目的。以下是基于二叉树的空间索引技术中的几种实例：1 、kd-树：kd-树或者是一颗空树，或者是一颗具有以下性质的二叉树：（1）若它的左子树不空，则左子树上所有结点的第d维的值均小于它的根结点的第d维值（d为根结点的分辨器值）；（2）若它的右子树不空，则右子树上所有结点的第d维的值均大于或等于它的根结点的第d维值（d为根结点的分辨器值）；（3）它的左右子树也分别为kd-树。2、k-d-b-树k-d-b-树是 kd-树与b-树的结合。它由两种基本的结构区域页（region pages，非叶结点）和点页（point pages，页结点）组成在k-d-b-树中，区域页显示存储了这些子空间信息。区域页的子空间两两不相交，且一起构成该区域页的矩形索引空间，即父区域页的一子空间。3、hb-树hb-树是一种有效的多维动态索引结构，其结点间搜索和增长过程模拟b-树的处理方法，结点内采用k维树组织和进行高效搜索。 1.3.2基于四叉树的空间索引技术 四叉树是建立在对区域循环分解原则之上的一种层次数据结构，在计算机图形处理、图像处理及地理信息系统中有广泛的应用，同样，它也可以应用于对空间点的表示与索引。这里的四叉树实际上是指2k叉树，其中k为数据空间的维数。以下是基于四叉树的空间索引技术中的几种实例4：1、点四叉树：点四叉树（point quad-tree）r.a.finkel and j.l.bentley，1974的提出主要是针对空间点的存储表达和索引。对于k维数据空间而言，点四叉树的每个结点存储了一空间点的信息及2k个孩子结点的指针，且隐式地与一索引空间相对应。2、区域四叉树采用区域四叉树索引多维空间的点比较常见的方法有mx四叉树和pr四叉树。mx四叉树将每个空间点看成是区域四叉树中的一个黑像素，或当作一方阵（square matrix）中的非零元素，因此称为mx四叉树。mx四叉树与区域四叉树的组织方式很相似，区别是叶子结点为黑结点或空结点分别表示数据空间某一位置空间点的存在与否。pr（point region）四叉树与区域四叉树的组织方式一样。区别是叶子结点或者为空、或者包含一数据点。3、cif四叉树cif（caltech intermediate form）四叉树是针对表示vlsi（very large scale integration）应用中的小矩形而提出的，它可以用于索引空间矩形及其他形体。它的组织方式与区域四叉树相似，数据空间被递归地细分直至产生的子象限不再包含任何矩形。1.3.3基于b-树的空间索引1、r-树r-树是b-树在多维空间的扩展，它由guttman 于1984年提出a.guttman，1984。 查找：为了找到与查找区域相交所有空间目标，查找必须从根结点开始，递归地遍历所有索引空间与查找区域相交的子树，当遇到叶子结点时，数据矩形首先与查找区域进行测试，如果数据矩形与查找区域相交，则再提取对应目标的几何信息进行计算。2、r*-树r*-树在结构上与r-树完全相同，在树的构造、插入、删除、检索算法上也基本相同，区别有三点：（1）插入路径的选择，为了选择一合适的插入路径，r-树只考虑了目录矩形的“面积”这一因素，r*-树除了考虑“面积”以外，还考虑了目录矩形的重叠（overlap）。(2)结点的分裂，r*-树考虑了三种“优势值（goodness values）”的计算方法，分别为area-value=areambr（group1）+areambr（group2），margin-value=margin mbr（group1）+marginmbr（group2），overlap-value= areambr（group1）areambr（group2）。(3)强制重新插入，无论是r-树还是r*-树都是动态建立的。对于同一空间目标集合，插入的顺序不同，所构造的r-树或r*-树是不同的5。3、r+-树r+-树是r-树的又一种变体。提出r+-树的主要思想是：如果裁剪数据矩形，那么中间结点目录矩形的零重叠可以获得，因此对于点查询，查找路径可以只有一条；对于区域查询，查找性能也可以得到提高。查找：r+-树的查找算法与r-树雷同。插入：r+-树的插入算法与r-树的插入算法不同的是：数据矩形可能被插入到多个叶结点；溢出的结点须执行分裂操作，且分裂可能向上蔓延到父结点，向下传播至子节点。删除：由于数据矩形可能被插入到多个叶结点，因此r+-树的删除算法必须同时删除一个数据矩形的多个拷贝。1.3.4基于空间目标排序的索引方法1、z-排序z-排序技术基于空间填充曲线，空间填充曲线基于这样一种假设：任何属性值都可以用固定长度的比特位表示，称为k比特位。沿着每一维的值的最大数目是2k。它通过将数据空间循环分解到更小的子空间来获得对于给定对象形状的近似。z-排序作为一种空间索引机制，它已经被用于数个商业化的空间数据库系统。2、hilbert曲线与z-排序类似，hilbert曲线也是一种空间填充曲线，它利用一个线性序列来填充空间。1.3.5qr-树qr-树是结合quadtree（准确地说，应该是2k叉树，k为空间的维数。为描述方便，以下称为quadtree）和r-树而提出的一种空间索引结构。qr-树的结构由quadtree和r-树的结构组成。1.4论文的组织结构第1章:绪论。概述了当前空间数据库的起源及其发展现状，简述了空间数据库与其索引技术的理论基础和基本知识，并且简介了当今社会上的几种主要的空间数据库索引技术。第2章：动态哈希技术是一种按内容访问的技术，并且它是一能实现高速数据存储和检索的方法,为此,在汇编语言和编译系统等方而得到了广泛的应用。所以这里对动态哈希技术进行了介绍和其种类的分析介绍。第3章：基于动态哈希的格网法的空间索引技术的提出和实现。而基于动态哈希的格网法的基本思路是将索引空间分为相等或不相等的一些小方格，与每个格网相关联的空间目标则存储在同一磁盘页，而格网的访问地址则可以直接通过求数组下标或某种算法得到。并且提出了网格文件，r文件和g树的索引方法以及具体的索引操作过程和其实现的过程。并且重点介绍了g树的算法思想。第4章：应用与发展。阐述在基于动态哈希的格网法空间索引技术方面上的实际应用，并且对基于动态哈希的格网法的空间索引技术提出一点技术展望。第5章：总结全文的论点及重点。第二章 关于动态哈希方法2.1关于动态哈希方法的介绍哈希技术自问世以来已有近四十年的发展历史,它是一种按内容访问的技术，它最吸引人的特点是能在常量级（这里的时间复杂性度量标准是概率平均）对哈希文件中的记录进行访问,而不依赖于文件中一记录的个数。是一能实现高速数据存储和检索的方法,为此,在汇编语言和编译系统等方而得到了广泛的应用。但传统静态哈希方法却不能像树结构那样根据需要而动态扩充或收缩其文件空问。人们为克服传统静态哈希 的这一不足,在七十年代末,八十年代初,提出了许多能根据需要而优关地扩充或收缩其文件空间的动态哈希方法,如litwin的线性哈希（1980年），larson的“部分扩充线性哈希“（1980年），martin的螺旋式存储（1979年），figin、nivergel和strong的可扩充哈希（1978年）等等 。在这类方法中,最有效的是线性哈希及其改进一部分扩充线性哈希和螺旋式存储。溢出处理和哈希函数的设计是传统静态哈希的两个关键问题,哈希函数的设计或溢出处理方法的不同导致了各种各样的静态哈希法!在动态环境中,除溢出处理和哈希 函数设计这两大问题外,还有哈希文件怎样动态扩充或收缩的问题。动态哈希的提出很好地解决了这一问题,从而使哈希技术的研究和应用进入了一个崭新的时期。动态哈希法是一类外哈希法,它实际上是传统哈希技术和树结合的变形产物。它的基本思想同传统哈希一样：首先设计从关键字域u到存储空间（又称哈希文件）的映射函数。一个哈希文件是关键字域 u 的一个子域所确定的记录集合。哈希文件中的一个记录是由关键字域u中一个关键字唯一确定的,文件含有干若个用于存放记录的桶。对文件操作的基本单位是桶,每桶可存放b个记录,见图1.当有超过b个记录通过哈希函数映射到同一桶时，该捅产生溢出,此时称哈希文件发生溢出,为此需进行溢出处理,可简单地用静态哈希中的链接法 ,将溢出记录存于溢出桶中,再将溢出桶链接到产生溢出的原始捅中。当记录的插人使文件的大小超过了分配给它的空间时,文件将扩充空间,并使一些记录重构至新增空间中。扩充一般是通过分裂操作实现的（ 如将一桶分裂成两伙伴捅,使整个文件增加一捅空间）。相反，删除记录引起的文件空间收缩,一般是通过合并操作（如合并两伙伴桶成一捅）实现的。对外哈希法来说，由于对外存的访问时间比内存访问时间要长得多,因此,可简单地将哈希文件上一个操作序列对外存的访问时间（一般是以访间次数作为度量标准）作为该序列的操作时间!内存空间代价,外存访问时间代价和文件空间利用率（类似于内哈希表的装载因子）是动态哈希法中相互制约的三大因素7。2.2动态哈希法的分类按动态哈希法组织的文件结构可将动态哈希法简单地分成两大类（1）有目录表的动态哈希法在该类方法中,对哈希文件中某捅的操作,首先要通过哈希函数获得目录表的某目录项,再由该目录项获得访间捅的地址,实现对其操作，属于该类方法的有“可扩充哈希”等。（2）无目录表的动态哈希法它是指对文件中某捅的操作将由哈希函数直接进行,即哈希函数是面向文件地址的!属于该类方法的有“线性哈希“,“螺旋式存储”等，两类动态哈希法构成的文件结构如图2.显然,当有目录表法中的目录表太大而不能完全放在内存时,就不可能实现最优检索。同样,若无目录表法中的溢出处理采用静态哈希中的链接法也不能达到检索最优。按动态哈希法采用的分裂原则也可将其分成两类。哈希文件空间的扩充或收缩是通过分裂或合并文件中的桶来实现的。因此,对分裂或合并存在控制和非控制两种原则。所谓非控制分裂原则是指：当文件中任何一桶产生溢出时,就对该桶进行分裂。相反地,控制分裂原则是通过容许溢出记录来推迟分裂的发生 ,推迟分裂会提高文件空间利用率,所以,一般是通过控制文件空间利用率来推迟分裂的发生即仅当文件空间利用率达到选定的上界（或下界）阀值时,分裂（或合并）文件中某桶。与分裂原则相对应就可把动态哈希法分成两种方法：1、控制分裂原则的动态哈希法,属于该类方法的有“带分离量的线性哈希“等。2、非控制分裂原则的动态哈希, “可扩充哈希” “改进的动态哈希”等都属于该类方法。非控制分裂动态哈希法的空间利用率较低,其期望值为ln2=0.693 。而控制分裂动态哈希法由于普遍采用以空间利用率来控制分裂,所以文件空间利用率可由人控制,一般都高于ln2。但空间利用率的增加会使哈希文件上各种操作代价增加,因为这导致了发生冲突的可能性增加。能根据需要而优美地扩充或收缩文件空间的动态哈希法,到今天已发展了十几年,在所提出的各种方法中,就两大类方法（有目录表法和无目录表法）比较起来,我们认为无目录表法优于有目录表法,而在无目录表法中,最有效,也是最实用的方法就数螺旋式存储和线性哈希两种方法及其上的改进方法。它们被应用于内哈希表以及在并行哈希等方面的实现,各种有目录表法和许多重要的关于动态哈希的成果,特别是基于动态哈希的格网法的空间索引技术的研究是重中之重。第三章 基于动态哈希的格网法的空间索引技术由于哈希索引能够根据查找关键字通过哈希函数直接定位查找记录，因此哈希索引被广泛地应用于现有的数据库管理系统中。基于动态哈希的格网方法的基本思路是将索引空间划分为相等或不等的一些小方格网，与每个格网相关联的空间目标则存储在同一磁盘页，而格网的访问地址则可以直接通过求数组下标或某种算法得到。下面主要介绍两种典型的空间索引结构：网格文件与r-文件。3.1网格文件3.1.1网格文件及其查找网格文件（the grid file）是针对点目标的索引而提出的。设k为空间的维数，则网格文件由两基本结构组成：1、k个线性刻度（k linear scales）；2、一个k维目录（directory）如图3所示。网格文件的基本思路是根据一正交的网格（orthogonal grid）划分k维的数据空间。k维数据空间的网格由k个一维数组表示的刻度（scales）所定义。刻度的每一边界（boundary）构成一（k-1）维的超平面（hyperplane，对于二维空间为平行于x或y的直线），这一超平面将数据空间划分维两个子空间。所有的边界一起将整个数据空间划分成许多k维的矩形子空间，这些矩形子空间称为网格目录（grid directory），由一k维的数组表示。目录项（即网格目录数组的元素）和网格单元（grid cells）之间具有一对一的关系。网格目录的每一网格单元包含一外存页的地址，这一外存页存储了包含于该网格单元的数据目标，称为数据页（data page）。由于没有每一网格单元必须至少包含m（m0）个目标的限制，因此一数据页允许存储多个网格单元的目标，只要这几个网格单元一起形成以矩形的区域。数据页所对应的一个活多个网格单元称之为存储区域（storage region）。存储区域两两不相交，它们一起跨越整个数据空间。对于大部分应用来说，目录的大小要求它必须存储在外存，但是，刻度（k个一维数组）往往很小，可以缓存在主存中。网格文件的查找操作较简单，只须找到查询涉及到的网格单元，并提取相应的数据页，然后比较数据页的目标是否满足查询要求即可。对于点查找，只需要访问一个网格目录项及其对应数据页；对于区域查找，需要访问与查找区域相交的少量网格单元及其对应的数据页，因此查找效率较高。3.1.2插入插入一目标的步骤如下（设数据页的容量为3个点目标）：（1） 定位正确的网格单元，提取相应的数据页。（2） 如果该数据页未满，则简单插入该目标。（3） 如果该数据页已满，则需要分裂该数据页。（a） 如果该数据页对应的存储区域覆盖多个网格单元，且该存储区域的数据目标并不是全部包含于同一网格单元，则该区域的网格单元分配已有的数据页和一存储了相应目标的新数据页。（b） 如果存储区域仅覆盖一个网格单元或该存储区域的数据目标全部包含于一网格单元，则网格必须由一将该区域划分为两个子空间的k-1维超平面扩展。一新边界必须被插入到某个线性刻度以维持网格和网格目录之间的一对一关系，同时一（k-1）维的“横截面”被插入到网格目录。划分成的两个存储区域不相交且每个存储区域与一数据页相关联，溢出数据页存储的目标被重新分布于该页及一新数据页。划分的k-1维超平面同时将其经过的网格单元都一分为二，但由于网格单元可以共享同一数据页，因此影响较小，如图4所示。3.1.3删除删除一个目标的处理步骤如下：（1） 定位正确的网格单元，提取对应的数据页。（2） 从数据页中删除该目标。（3） 如果删除记录的存储区域及其相连接的存储区域共同拥有的记录数少于某一阀值（nievergelt 等建议为数据页容量的70%），则合并与两存储区域对应的数据页，这样做是为了提高存储空间利用率。数据页合并的方法有两种：相邻系统（neighbor system）和伙伴系统（buddy system）：（a）相邻系统只要求两数据页的存储区域相邻且合并后形成的新区域保持矩形形状，就允许它们合并。相邻系统可能会产生“死空间”，即相邻的数据页阻止与某一下溢数据页的任何合并。（b）伙伴系统采取更严格的合并策略来预防“死空间”的产生。它规定，如果两数据页的存储区域可以由合并它们形成的较大存储区域的分裂而得到，则允许它们合并。不幸的是，对于k维数据空间而言，完全消除“死空间”往往是不可能的。当没有存储区域与边界邻接时，合并处理将使沿两老数据页的边界冗余6。如图5所示，3.2 r-文件r-文件（the r-file）可以看作是对网格文件的一种改进，用来索引点状空间目标及非点状空间目标，且不须进行空间目标的近似于映射和空间目标的裁剪或重复存储。在r-文件中，单元格的划分采用了与网格文件同样的策略，且溢出的单元格被分裂，为了使单元格更紧密地包含空间目标，单元格被重复地二等分直至得到包围空间目标的最小单元格。包含于一单元格的空间目标被存储在单元格相对应的数据页中，与划分线相交的空间目标则存储在原单元格。如果欲划分线相交的空间目标数超过一数据页的容量，则用沿另一维的划分线继续划分。如果这些空间目标都位于划分线的交点，且它们不能被任何划分线划分，则采用一连串的桶来存储之。经过分裂，原单元格与两个新单元格重叠，为了控制网格目录的大小，空单元格没有维护。经过分裂，原单元格与新单元格都包含有几乎相同数量的空间目标。尽管如此，对于相交查询，需要扫描很多的单元格，尤其是那些初始的大单元格。为了提高相交查询的效率，对于初始单元格，存储了在划分维（如x维）包住属于该单元的目标的两个额外值（x-min，x-max）。由于单元格重叠，网格目录可能很大。为了避免存储单元格边界，采用一种称为z排列的方案给单元格编号。对于每一个单元格，目录存储该单元格的序号，包围间隔（bounding interval）及数据桶的指针。实验说明，单元格的包围信息可以大大地减少页面访问。下面四个图为r-文件示意图。 r-文件单元格的级数与数量由索引数目及索引目标的大小所决定。当索引数量很大时，索引空间须经过多次细分，产生多级的大小单元格，这无疑会增加查询时访问单元格的数量；而且许多相对较大单元格的桶链会较长，这也会增加查找时的外存访问。因此对于大型的空间数据库系统，r-文件索引效率欠佳。3.3 g树3.3.1 g树的空间模型3.3.1.1 g树的总体结构g树从整体上看，它是一种多层次的动态生长的格网结构。对于每一层次，其结构是一棵基于页面的动态生长的格网结构。其结构图如下图1创建模型时，g树最下层格网采用了类似于a树的mbr的网格。设其大小为（m，n），插入时，当对象的实际范围大于最上层的格网时，则向上以某种比率（f（i），t（i）扩展一层格网，直至满足格网大小能覆盖其范围为止。为避免影响查询效率，格网应有一个高度限制，超过限制的对象应直接存储在最上层的格网上。在每一层格网内，用页面来表示范围的概念。页面被划分成许多小的单元，每个页面单元存储指向存放相应网格的对象集的地址。插入时，将对象所在网格按某种方式（g（x，y）投影到页面单元，以找到对象的存放位置。设页面被分为ab个单元，即一个二维数组（a，b），其动态格网构建方法是：（1）以第一个插入对象所在的格网（x，y）为基准，其地址存储在此页面的第一个单元，则任何格网（xi，yi）存放在（xi-x1）+a）moda），（yi-y1）+b）modb）单元。（2）记录该格网的范围，当此格网的范围超出（a，b）的范围时，就向上扩展一层，即用上一层页的页单元来存储此层页面的地址。这个格网页面地址存放在上层页的第一个单元。（3）超出的网格存放在另外的格网页面上，再将格网页面插入上层页面，格网页面在上层页的插入方法与上相同。因此，插入网格必须经过二层查询来找到插入的位置。格网结构如图11。依次结构，查询时即可避免比较与遍历的过程。设给定一查询范围（c，d），其查询步骤为：（1）比较查询范围与网格的大小，即在所有满足条件（af（i）c，dt(i)j）的格网层次上进行查询。（2）当查询格网层i（ai，bi）时，按给定的查询范围，可找到关联的所有网格。如图11中所示。以其中一边为例，因对象以其重心来确定所属网格，故当（c-c1）ai/2时，所关联的网格是c3以下的网格；当（c-c1）ai/2时，其关联的则是c3以下的网格。(3)确定网格后，可通过计算（g（x，y）来直接找到其对象存放的地址。精确查询时，其中c1以下网格内的对象可直接提交，其余则经过refinestep提交。3.3.1.2 g树对n维对象的支持g树的格网结构可支持n维对象。n维对象也可以表示为一种多层次结构，由最小对象（m1，m2，mn）的层次以某种比率（f1i,f2i，fn(i)）向外扩展。对于每个层次，将对象所在的位置以某种方式（g（x1，x2，xn）投影到页面，找出其存放的地址，以建立多层次基于页面的树状结构 。其插入、查询算法以及复杂度和二维对象基本相同。可见，g树较易实现n维对象的空间索引。3.3.2 g树上的操作算法g-tree算法包括steiner树的构造和拐弯数的优化两大部分3.3.2.1树的构造steiner树的构造算法步骤如下：stepl根据端点集合t，产生hanan网格step2令集合i等于tstep3计算i中节点坐标的重心，并选择一个坐标距离重心最远的点，计算它受到邻近点的引力之和step4根据得到的合力的水平和垂直分量的大小和方向，决定该点是向上下左右哪一个方向移动，改变该点的坐标并标记走线如果该点移动之后与已经存在的节点的坐标重合，则将两点合并(新点的质量等于1或原来两点质量之和采用何种为佳，在后面讨论)step5经过一次移动后，更新istep6转step3，重复移动过程直到i中只剩下一个点step7采用一些优化策略来调整走线，减少拐弯3.3.2.2减少拐弯数的策略减少拐弯数是g-tree算法的一个重要目标，该算法在steiner树的构造过程及构造后的优化过程中都对此进行了考虑在steiner树构造过程中的优化我们在构造树的引力计算中采用2个权重口和口来减少拐弯数用来增加2个点处于同一条水平或垂直线时的引力大小假设2个点a和b在hanan网格上的坐标分别为(x1，y1)和(x2，y2)如果点a和点b在同一水平位置，它们之间的引力是fab=1（x1-x2）2（1+）；如果它们在同一垂直位置，它们之间的引力则是fab=1（y1-y2）2（1+）在实验中，若令=0.51，则图1中t1和t2之间的引力是f12=1（0-30）2（1+0.51）=1.678103.用来保证一个点优先在一条直线上移动如果一个点的移动方向与它上一次的移动方向相同，则该点的合力等于该方向上的分力乘以(1+)例如，假设s3点是t1从点移动来的，并且s3点受到的合力的水平和垂直分量分别为26 x 10-3和35 x10-3，垂直力大于水平力，则s3，应该向上移动到s2但是根据上面所说的加权，应在水平力上乘以(1+)假设=09，则新的水平力是26 x 10-3 x(1+09)=494 x10-3，得到的新的水平力大于垂直力，则s3应该向右移动到s4，这样就减少了拐弯数和的取值都是正数越大，则处在同一直线上的2个点之间的引力越大；越大，则一个点越可能走它上一次的移动方向但是，如果和取值太大，则可能为了减少拐弯而增加了较长的走线，可以将和的上限定为2在一个点已有走线方向与另一点的连线方向相同时，和对引力的影响是同方向的；否则，二者的影响方向成90o，对走线的影响会相互抵消和的取值是独立的，经过多次实验，我们给定了2个比较适合的和值，分别取05和09steiner树构造之后的优化，在生成steiner树之后，g-tree算法还可以通过改变steiner树的形状来减少拐弯数，有2种优化方式:1、针对如图12 a所示的“z”型树如果s，不是一个端点，它可以被移动到s1，同时相应的边也进行了移动，如图12所示2、移动整段水平或垂直边如图13所示，如果图13 a中的点s1和s2不是端点，它们之间的线段可以向上拉动到图13b的位置，这样就减少了拐弯数 对g树的主要操作有建立、插入、查询和删除。其中，建立操作实际上是大量的插入。实现以二维对象为例，讨论g树的插入、查询和删除算法。g树的连续插入过程，即是g树的动态建立过程。g树的查询，则根据给定范围经过计算求出所关联网格的地址，然后经过refinestep提交结果。g树的删除算法直接删除指定对象，无须进行树型调整7。3.3.2.3 g树算法的讨论对g树效率的讨论，可从若干个方面进行：（1）插入、删除的效率：g树的插入和删除均较简单，只需经过基本的映射比较即可。其效率与a树、r树相仿。（2）查询的效率：这是g树主要优点之一，它彻底地消除空间的不相邻性以及因空间重叠而引起效率的下降，通过简单计算实现查询，大大地提高了效率。（3）最坏情况下的效率：在a树中，数据很不均匀情况下的效率比较差。而在g树中，因为g树将整个范围当作一个整体来对待，数据不均匀情况下的效率和平均效率相差不大。（4）空间利用率：由于g树以整个页面来进行索引，其空间利用率比a树稍低。但随着硬件技术的提高，计算机的存储容量日益增大，以少量的空间换取效率的提高还是很值得的。算法复杂度分析：给定端点集合t，若其含有n个元素，可以近似地认为hanan网格的大小是”nn，并假设其长度是ll因此rsmt的边数是o(n2)，该边数同时也是点的移动次数在每一步移动中，g-tree算法不需要计算该点受到其他所有点的引力，只计算该点的一个邻域(orl)可以令需要计算的邻近点个数为一个常数k，那么=knl当n较大时，k相对于n是一个小量；当kn时，令k=n从上面的分析可知，g-tree算法的复杂度是o(kn2)或o(n3)83.4 基于动态哈希的格网法的空间索引技术的分析3.4.1关于网格文件中的分析网格文件的优点是：当其用于索引低维空间的点状目标时，由于可以再较少的外存页面访问中得到查找结果，尤其是对于精确匹配的点查找，可以通过两次外存访问（一次是访问网格目录，一次是访问数据页）得到结果，因此效率较高。网格文件的主要问题是网格目录的存储，因为如果空间维数较高或数据量较多时，网格目录将变得非常庞大，每一次分裂，都要增加很多网格目录项。而且网格文件目录往往存储在外存，对其的存储于操作也需涉及外存访问。另外，当索引非点状空间目标时，需要采取目标近似于目标映射或允许目标重复存储的策略，区域查询效率较差9。3.4.2关于r-文件的分析r-文件单元格的级数与数量由索引目标数及索引目标大少所决定。当索引数据量很大时，索引空间必须经过多次细分，产生多级的大小单元格，这无疑会增加查询时访问单元格的数量；而且许多相对较大单元格的桶链会较长，这也会增加查找时的外存访问。因此对于大型的空间数据库系统，r-文件索引效率欠佳。3.4.3关于g树的分析对g-tree算法是否能有效地生成拐弯数较少的steiner树进行实验g-tree算法采用标准c+语言编码实现测试例子由geosteiner3.1附带的工具包生成在4 gb内存和双核3 ghz cpu的linux平台上，采用g-tree和geosteiner31分别对测试例子进行运算下面就2个节点合并时，质量是保持1还是等于2个点原有质量之和进行讨论若是前者，则合并生成的新节点与已有节点一样，质量都保持为l，新旧节点之间是平等的；若是后者，每合并一次，新节点的质量都会增加，更容易吸引其他节点，这种方法同时记录了一定的历史信息经过实验，我们发现在大多数情况下，采用后一种方法拐弯数和线长都比前一种方法的略少令=0.5，=0.9，k=20；并且合并2个节点时，新节点质量等于2个节点质量之和；得到的实验结果7如表1所示表1g-tree算法与geosteiner3.1的实验结果比较端点数g-tree算法geosteiner3.1线长算法时间/s拐弯数线长算法时间/s拐弯数8176930.0017176930.00179197990.0018197990.001810212070.0018211430.001820350120.00119347670.0012050540240.03149515950.0015470633170.06161595030.02070100816630.19791729790.0501044101613339.96936814811534.5441450017728718.14245616084432.055081000254165162.1871098从表1可以看出：1)当端点数大于10时，g-tree算法的拐弯数比geosteiner3.1的小；2)当端点数小于9时，g-tree算法可得到与geosteiner3.1同样的结果；3)当端点数大于9时，g-tree算法得到的线长比geosteiner3.1长了大约10；4)当端点数大于410时，g-tree算法的运行时间比geosteiner3.1少，因为g-tree算法只计算了一定邻域内点的引力综上所述，g-tree算法在可能牺牲一定线长(增加约10)的前提下，能够有效地减少约10的拐弯数。第四章 基于动态哈希的格网法索引技术的发展前景空间数据库索引技术是近些年来在应用中发展起来的一门新兴学科，它具有十分广阔的应用市场。同时，基于动态哈希的格网法空间数据库索引技术也是一门随着相关应用技术及计算机软件硬件的进步而不断发展和完善的学科。下面首先简要介绍几种常用的数据库的空间索引技术，接着概要性地介绍基于动态哈希的格网法空间索引技术存在的问题及发展动向。4.1基于动态哈希的实际应用4.1.1基于动态哈希路由的peer-to-peer网络napster采用了集中式的日录服务器实现搜索，gnutella和freenet采用了泛洪技术实现搜索。这