《毕业设计（论文）-移动对象的存储和查询系统设计与实现.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）-移动对象的存储和查询系统设计与实现.doc（36页珍藏版）》请在三一文库上搜索。
1、摘 要随着GPS技术的发展和成熟，很多“基于位置的服务”应用软件也迅速的发展起来。旅行时迷路了，我们可以用手机上的导航系统定位现在所处的位置，还可以查询离我们最近的公交点，甚至可以查询正向我们这个方向驶来的无人出租车。人，公交点，出租车都可抽象成一个个的移动对象，这些对象的运动生成一条条的轨道。移动对象的位置可能时刻发生变化，像以往的数据库，是无法存储这种数据量极大且更新频繁的数据，为了解决大量移动对象位置频繁更新所带来的性能下降问题，我们提出了一种基于改进的四叉树和哈希表的基于位置和时间的索引结构。这种索引结构以位置为主索引，时间为第二索引，并对四叉树的叶子节点采用适时合并的方法来防范分支太
2、深而造成的查询效率低下。本论文主要讨论对移动对象数据几种主要建模方法，并对相关索引及其存储查询技术进行概述分析。本论文以时空历史点数据的密度为依据，引入四叉树对轨道点进行区域划分存储和查询，并在四叉树单元内采用时态索引机制对数据块进行索引。同时介绍了几种在这种索引存储结构上的几种算法，通过对算法的描述我们可看出这种索引结构的优势所在。关键词： 移动对象；四叉树；索引结构 ABSTRACT With the development and maturation of GPS technology, a lot of location-based services applications are
3、 rapidly developed. When we get lost on travel, phone navigation system can tell us where we are. We can get the nearest public transportation points, or even the taxis coming in our direction. Either people, public transportation points or taxis can be abstracted into a moving object. The Movement
4、of these objects can be described as a track. The position of moving objects may change all the time. Traditional index structures do not work well on moving objects because of the need of frequently updating the index which leads to the poor performance. We presents a novel indexing structure based
5、 on quadtree and Hash table which use location as the first index and time second. Merging timely the corresponding nodes to degrade the depth of the tree can guarantee the query efficiency.This paper focuses on several major data modeling of moving objects and analyze its indexing and storage and q
6、uery technology. In this study, we base on the density of space-time history point data, introduce the quadtree and divide the track point on region to storage and query. Inside the quad tree cell system, the data blocks are divided by time index. Last we introduce several query on this index storag
7、e structure and we can see the advantages of this index storage structure.Keywords: moving object; quadtree; index structure目 录第1章 绪论11.1 研究背景和意义11.2 国内外研究现状11.2.1时空数据库国内外研究现状11.2.2移动对象索引研究现状21.3 该课题研究的主要内容31.4 本论文结构与安排31.5 本章小结3第2章 相关技术介绍42.1 移动对象数据库基本概念42.2 移动对象数据建模52.2.1 线段模型52.2.2 点模型62.3 基于Quad
8、tree和Hash表的移动对象索引72.4 磁盘块存储技术82.5 本章小结9第3章 系统实现103.1 系统介绍103.2 模块介绍103.2.1 内存处理103.2.2 存储结构163.3 四叉树生成243.3.1 数据导入243.3.2 生成算法243.4 几类查询算法253.4.1 范围查询253.4.2 轨道查询283.4.3 某时刻位置查询283.4.4 KNN查询303.5 本章小结30第4章 结论31参考文献32致 谢33III第1章 绪论1.1 研究背景和意义近年来，随着无线通信技术的高速发展，时空数据库越来越多地应用在地理信息系统、交通管理、定位、城市规划等各个领域。在无线
9、定位业务（Location-BasedService,LBS）应用中，LBS通过无线通信网络获取移动对象的位置信息，在地理信息系统平台的支持下为客户提供相应的服务，其中包括儿童保护、个人导航应用、寻友服务、销售人员管理、资产跟踪服务等，获取的移动对象及其位置信息组成的数据库称为移动对象数据库（Moving Objects Databases,MOD），它基于时空数据库中时间和空间变化类型之一：实体的运动。随着GPS技术的发展和成熟，很多“基于位置的服务”应用软件也迅速的发展起来。旅行时迷路了，我们可以用手机上的导航系统定位现在所处的位置，还可以查询离我们最近的公交点，甚至可以查询正向我们这个方
10、向驶来的无人出租车。人，公交点，出租车都可抽象成一个个的移动对象，这些对象的运动生成一条条的轨道。移动对象的位置可能时刻发生变化，像以往的数据库，是无法存储这种数据量且更新频繁的数据。因此我们提出了移动对象数据库，用来存储移动对象的运动轨迹。为了解决大量移动对象位置频繁更新所带来的性能下降问题，我们必须在移动对象数据库上加上空间和时间的索引。1.2 国内外研究现状1.2.1时空数据库国内外研究现状目前国外对于时空数据库已经开展了广泛的研究工作。其中，chorochronos项目组是由欧洲委员会资助的培训和流动的研究人员项目组，他们在时空数据库的设计、实现和应用方面做了大量的研究工作，研究内容主
11、要包括时空对象表达、时空数据的建模、时空信息图形用户接口、时空对象查询处理、时空对象的存储、时空对象索引以及时空数据库体系结构等内容。美国普顿(Purdue)大学的PLACE项目组在时空数据库方面也有一定的研究成果，主要涉及无线通讯技术、个人定位系统、信息科技环境下为用户提供基于位置的服务等，其中为用户提供的基于位置的服务是一个可扩展的基于位置的数据库服务器。国内在时空数据库的研究方面起步稍晚，目前主要有复旦大学、香港城市大学、华中科技大学等几所高校的教研室对时空数据库进行了广泛研究。当前国际上一些权威期刊如VLDB Journal、ACM TODS、IEEE TKDE、DKE等和国际著名会议
12、如ACM SIGMOD、VLDB、ICDE、SSTD等也对空间和时空数据库给予了很大的重视，并将其作为主要研究内容之一。全球主流的数据库厂商Oracle、DB2以及Informix等也纷纷提供了可扩展的对象关系数据库技术，以支持时空数据库方面的扩展。例如，Oracle定位器(LocatoO、Cartridges的DomainIndexes技术以及Oraclc9i数据库系统中提供的对基于位置查询的支持等。1.2.2移动对象索引研究现状为了快速、有效地处理海量数据，近年来，针对移动对象索引的研究，专家们提出了大量基于磁盘的时空数据库索引方法。其中时空索引研究的两个重要的途径是对于R-tree和四叉
13、树(Quadtree)扩展构建新的索引结构。在针对移动对象索引结构的性能测试中，大量的合成数据集被用来进行试验工作。虽然时空数据处理对于现实世界建模非常重要，但是由于时空数据的复杂性，目前好的时空索引却不是很多。索引的研究多集中在支持多维数据的纯空间索引研究和对于一般传统数据类型(如数字，字符串)的时态索引上。由于R-tree及其变体在空间索引上的优势，在过去几年里，研究者们提出了许多基于R-tree的时空索引版本，可以把它们大致分为如下几类：(1)把时间信息添加到空间维中，从而将空间索引转变为支持时空的移动对象索引方法；(2)使用重叠和多版本结构，将时间维和空间维隔离开来，一个时间片的空间数
14、据集中存放在一个索引结构中；(3)处理迹线方式，将数据在逻辑上看成是各条轨迹的集合。同时，TTzouramanis等人的四叉树(Quadtree)也被广泛地应用于时空对象索引中。1.3 该课题研究的主要内容本论文主要讨论对移动对象数据几种主要建模方法，并对相关索引及其存储查询技术进行概述分析。本研究以时空历史点数据的密度为依据，引入四叉树对轨道点进行区域划分存储和查询，并在四叉树单元内采用时态索引机制对数据块进行索引。由于移动对象为断地产生大量的时空信息，因此如何有效地管理这些动态信息一直是被广泛关注的研究课题。时空存取方法主要分为两类：一类是对移动对象历史位置的存储和访问；另一类为移动对象当
15、前和未来位置的存储和访问。索引技术发展也因此侧重不同方面。例如，STR-tree结构和TB-tree结果是针对移动对象过去位置信息的索引，TPR-tree结构是对移动对象当前和未来位置的索引。在当前已提出的移动对象索引方法中，基本上都不支持对移动对象标识的查询，由此导致索引结构的更新和查询存在一定的缺陷。本文着重讨论一种基于QuaoTree和Hash表的基于位置为第一索引，时间为第二索引的索引结构及其实现。1.4 本论文结构与安排第一章 绪论，主要阐述研究的背景和意义，以及国内外的研究现状。同时简要介绍本论文的研究内容及本论文的结构与安排。第二章 相关技术介绍，本章分别介绍了时空数据库，移动对
16、象数据库及其数据模型和查询，同时介绍一种基于Quadtree和Hash表的位置和时间索引结构。第三章 系统实现 本章主要介绍系统实现，系统各模块及QH索引更新策略及算法和查询处理及其算法。第四章 结论。1.5 本章小结本章主要介绍移动对象数据库的研究背景和意义。然后介绍时空数据库国内外研究的现状及移动对象索引研究现状，同时提出本论文实现的基于Quadtree和Hash表的移动对象基于位置和时间的索引结构。最后介绍本论文的各章节安排。3第2章 相关技术介绍2.1 移动对象数据库基本概念移动对象数据库是作为时空数据库的分支发展而来的，它基于时空数据库中对象的运动的特性，具有移动的特性。移动对象数据
17、库是对移动对象的位置及其相关信息进行表示与管理的数据库。在移动对象数据库中通常管理着两类空间对象，一类是静态的空间对象，比如“查询离我最近电影院”所提到的电影院，这类信息通常依赖于用户所在的位置；另一类则是移动对象，其位置是不断变化的，比如“查询位于A街区地警车”中所提到的警车。移动对象数据库是指对移动对象（如车辆、飞机、移动用户等）及其位置进行管理的数据库。移动对象管理技术在许多领域展现了广阔的应用前景。在军事上，移动对象数据库可以回答常规数据库所无法回答的查询；在民用领域，利用移动对象数据库技术可以实现智能运输系统、出租车/警员自动派遣系统、智能社会保障系统以及高智能的物流配送系统。此外，
18、移动对象管理技术还在电子商务领域有着广泛的应用前景。目前，移动对象管理主要研究问题包括：1.位置的表示与建模：为了对移动对象的位置进行行之有效的管理,移动对象数据库系统必须能够准确地获取移动对象的当前位置信息（位置信息的获取）,并建立有效的位置管理模型（位置信息的表示）。2.移动对象索引技术：在移动对象数据库中，通常管理着数量非常庞大的移动对象。在查询处理时，如果逐个扫描所有的移动对象显然会极大地影响系统的性能。为了减小搜索空间，就必须对移动对象进行索引。移动对象的索引技术是一个充满挑战性的研究领域。到目前为止，这方面的研究还比较初步，尚待进一步地深入。3.移动对象及静态空间对象的查询处理：移
19、动对象数据库中的查询目标分为两种：一种是移动对象、（如汽车、移动用户等），另一种是静态空间对象（如旅馆、医院等），对这两类数据的查询各自需要相应的索引结构的支持。移动对象数据库中的查询具有位置相关的特性,即查询结果依赖于移动对象当前位置，同一个查询请求，其提交的时间、地点不同，返回的结果也将不同。典型的查询包括区域查询（查询某个时间段处于某个地理区域的移动对象）、KNN查询（查询离某一点最近的K个移动对象）以及连接查询（查询满足条件的移动对象组合）等。2.2 移动对象数据建模移动对象的运动，是一条条连续的轨道，为了简化问题，我们考虑移动对象为二维空间里的一个点。其轨迹投影到平面上为一条有方向的
20、曲线，如图2.1和2.2所示。为了存储一条轨道，将要对轨道进行建模。 图2.1 轨道1 图2.2 轨道2对于图2.1和2.2所示的轨迹，是二维平面上一个点在一段时间内位置，图中并未将时间维度表达出来，为计论方便，我们假设图中所示的点p0,p1,p2,p3,p4,p5分别指对象在时刻t0,t1,t2,t3,t4,t5的位置。2.2.1 线段模型如图2.1所示，移动对象在时间(t0,t1)，(t1,t2)，(t2,t3) ,(t3,t4)，(t4,t5)的运动轨迹是一条线段，从图示中可看出移动对象的速度方向在这几个时间段里是没有发生变化的，由于图示上没有时间维度，所以看不出速度大小，我们假设速度大
21、小也未发生变化。这样的话，从点p0到p1，从p1到p2，从p2到p3，从p3到p4，从p4到p5，我们可以认为移动对象是恒速的，p0，p1，p2，p3，p4是速度的变化点，线段模型就在此基础上提出：将轨道按速度矢量的不同（此处的不同包括方向和大小）划成一个个的子轨道，使得每个子轨道内的速度是一致的。如图2.1所示，轨道p0,p5将被划分成p0,p1，p1,p2，p2,p3，p3,p4，p4,p5五个子轨道（也可用时间表示成t0,t1，t1,t2，t2,t3，t3,t4，t4,t5五个子轨道）存储这样一条轨道，我们只需要存储每一个速度变化点的一个四元组(OID,P,V,T)，其中OID表示对象的
22、ID(也可当作是轨道的ID)，P表示速度变化点，用空间点坐标(x,y)表示，V表示一个速度矢量，用二维空间的矢量(x,y)表示，T表示时间段，用tb,te表示，其中tb表示轨道开始时间，te表示轨道结束时间。如2.1所示的轨道，存储数据可为(oid1,p0,t0,t1,v0)、(oid1,p1,t1,t2,v1)、(oid1,p2,t2,t3,v2)、(oid1,p3,t3,t4,v3)、(oid1,p4,t4,t5,v4)。oid1为此移动对象的ID，vi表示移动对象在点pi(或时间ti)时的速度。这种模型对于速度变化不多的移动对象很适应，存储的数据量也很小。但对于像图2.2中所示的轨道，基
23、本是曲线的，速度基本一直在变化。对于这种轨迹，这种模型显示出其弱点，不过也可近似的方法将曲线分割成很小的线段近似代替。对于线段模型，本文不作太多讨论。以下别一种数据模型，也是本文所研究的数据模型点模型。2.2.2 点模型相比于线段模型，点模型不再以速度变化点为取样点进行存储，而是以时间点作为取样点。将轨道变成一个个离散的点，取样的时间因不同的应用系统可不一样，为讨论方便，我们这里定义一个单位时间片刻，我们研究的时间大多以这时间片刻为对象，对于不是取样点的时刻查询，我们有种近似计算方法，取离此时刻最近的前后两个取样时刻，将这两时刻以线连起来，按比例计算其位置。将时间离散化成一个个的时刻，是我们研
24、究点模型的基础。对图2.2中的曲线进行取样，我们得到图2.3的点轨道 图2.3 点模型图对于点模型，我们存储起来十分方便，只需要存储每个取样点的一个四元组（OID,X,Y,T）其中oid为移动对象（或轨道）的ID，X，Y分别表示其在二维坐标系中的横纵坐标，T表示时刻。与线段模型相比，这种模型基本上适用于任何形状的轨道，其精度取决于点样时间点，而这时间点可随应用系统的实际应用而变化。本论文中讨论的移动对象的存储和查询，都在此模型基础上提出。2.3 基于Quadtree和Hash表的移动对象索引在移动对象数据库中，通常管理着非常庞大的移动对象。在查询处理时如果扫描所有的移动对象将会极大地影响系统性
25、能。为了减小搜索时间，就必须对移动对象进行索引。移动对象的索引方法通常借鉴于空间数据索引技术，这些索引方法对移动对象的索引具有很好的借鉴意义，但是它们并不能直接用于移动对象的索引。这是因为上述方法更多地考虑查询效率，而没有着重考虑索引的更新代价。在移动对象数据库中，移动对象的位置更新会引起索引结构频繁的动态变化，因此，需要重点考虑索引的更新性能。为r提高查询效率，引入了标识查询；为了提高更新性能，引入了改进的Quadtree。因为Quadtree结构简单，更新时不需要对树进行平衡调整，所以可以提高更新效率。图2.4 索引结构图Quadtree是基于空间划分的时间索引，主要适用于二维空间(分支数
26、为4)，也可以推广至更高维以分支数扩大到2的d次幂)。如图1所示，它基于递归分解的原则，不断将空间四等分成东北、西北、西南、东南4个象限，直至每个子空间中的对象数目不大于某个阈值。四叉树结构简单，进行空间搜索时，性能较高；可以索引多种对象，如点、曲线等。为了在空间索引的基本上再添加时间索引，我们又用到了HashTable。我们的数据全部存储在磁盘的文件块中（下面将在介绍），每个块的大小一般是固定值，数据量过大时，一级哈希表可能存储不下，所以我们用到了两级哈希，这样的话大大增加了数据存储量上限。在哈希表结点中，我们给出了结点中所有点的最小时刻和最大时刻，也就是二级时间索引。下面先简单介绍图2.4
27、中各点的含义，更具体的模块信息请参考论文第3中的系统实现：我们先假设所有轨道的数据都存在一个vectorP里在，Point就是点模型中所提到的四元组。P中所有点的横纵坐标的最大最小值形成了图2.4中的大矩形，将该矩形中的点数目超过阀值，将此矩形分裂（四叉树的分裂），递归处理，将得到图2.4中所示的四叉树（四叉树结点具体存储信息请参考第三章系统实现）。图2.4中所标的四叉树中的圆形代表非叶子结点，方形代表叶子结点。叶子结点里用哈希表存储了该空间范围内的所有点信息。一级哈希表对应了多个二级哈希表，一个二级哈希表对应N个HashNode，其中第i个HashNode存的是轨道i里的点。由于存储块大小有
28、限，一个二级哈希表只能存m个HashNode,但轨道数Nm，这也是二级哈希表的作用。对应关系是，假设一个二级HashTable最多存n个HashNode，一个一级HashTable最多存m个二级HashTable，这们0n-1的轨道数据存放在第一个二级HashTable中，n2n-1的轨道数据存放在第二个二级HashTable中，依此类推。这样的话，哈希表所能存的轨道数为m*n。通过上面的哈希映射，我们能很块将QuadNode所述的空间范围中某一轨道的数据放入相应的HashNode里。由于数据量巨大，一个哈希结点是无法存储所有点的，所以又引进了分页机制，用链表的形式将所有点按数目划分成一个个的
29、页并形成链表，每个PageNode中，同样有该页中的时间最小值和最大值，也就是时间索引。2.4 磁盘块存储技术为也能将图2.4所述的逻辑结构存入磁盘中，并从磁盘中恢复此结构，我们用到了磁盘块存储技术。我们将一个磁盘文件以某一固定的大小（比如4096B）来划分成一个个的块，存储每一个逻辑结点时，以此块为分配单元。图2.4中所示的每一个逻辑结点，包括QuadNode，HashTable，HashNode，PashNode存储时都会对应磁盘文件中的一个块，块用唯一的非负整数作为块号。也就是每一个逻辑结点对应一个块号，这个块号所对应的块里将存储这个逻辑点的所有信息。至于如何存储这些信息，每个结点都封装
30、一个write_block()和read_block()函数，这两个函数是对应的，分别实现逻辑点自已的信息存储和读取方式，相当于系列化和反系列化。图2.4中各逻辑结点间的对应关系，其实就是用这些块号来描述的。最后说明一下文件块中比较特殊的一块，也就是第一块，这块就文件创建时就自动分配的，里面存有图2.4中结构中最重要的一个逻辑结点的块四叉树根结点的块。按照上述方法，就能将图2.4中各逻辑结点信息存入磁盘块文件，并从磁盘文件中恢复此逻辑结构或读取某一特定逻辑结点的信息。2.5 本章小结本章主要介绍一些相关的技术，第一节介绍移动对象数据库的基本概念；第二节介绍移动对象的数据建模，其中提出了一种线段
31、模型和一种点模型，点模型为我们所讨论的主体；第三节介绍点模型上的基于Quadtree和Hash表的移动对象空间和时间的索引；第四节介绍磁盘块存储技术。33第3章 系统实现3.1 系统介绍系统主要开发环境在VS2008上，开发语言为C+。程序主界面用的是XTremeToolkitPro v12.1.1开发包，3D模拟用的是OpenGL。3.2 模块介绍本节主要对系统设计中的各模块进行介绍，主要介绍系统设计中的主要类的成员及其接口。3.2.1 内存处理该模块主要实现数据的写入和读出图3.1 内存模块类关系图（1）类 BlockFile该类是一个块文件模拟器，负责对文件进行块操作。类及其成员图如表3
32、.1所示：表3.1 类BlockFile类图属性名称类型描述fpFILE *文件指针对象，指向存储到磁盘中的文件filenamechar *存储到磁盘中的文件的文件名blocklengthint数据块长度act_blockint当前正在处理的数据块的块号numberint当前文件中数据块的总数量new_flagbool标记文件是否是新创建的接口描述：1、void put_bytes(char * bytes, int num)：输入：字符串指针，字符串长度输出：无功能：将一定长度的字符串写入文件2、void get_bytes(char *bytes, int num)：输入：字符串指针，字符
33、串长度输出：无功能：从文件中读出一定长度的字符串3、void fwrite_number(int num)：输入：整形数据输出：无功能：将整形数据写入文件中4、int fread_number()：输入：无输出：整形数据功能：从文件中读出一个整形数据5、void seek_block(int bnum)：输入：指定的数据块块号输出：无功能：将文件中的指针从当前正在处理的数据块移动到指定的数据块6、void read_header(char *header)：输入：文件头信息输出：无功能：从文件中读取文件头信息7、void set_header(char *header)：输入：文件头信息输出：
34、无功能：将文件头信息写入文件8、bool read_block(Block b, int i)：输入：字符数组，数据块块号输出：读取成功与否功能：从文件中读出指定的数据块到字符数组中9、bool write_block(Block b, int i)：输入：字符数组 数据块块号输出：写入成功与否功能：将字符数据组中的内容写入到文件中指定数据10、int append_block(Block b)：输入：字符数组输出：当前分配的数据块块号功能：申请一个新的数据块11、bool delete_last_blocks(int num)：输入：数据块块号输出：删除成功与否功能：删除文件中指定数据块之后
35、的所有数据块12、bool file_new()：输入：无输出：返回文件标记功能：获取文件标记信息13、int get_blocklength()：输入：无输出：数据块长度功能：获取数据块长度信息14、int get_num_of_blocks()：输入：无输出：数据块总功能：获取数据块总数量（2）类 Cache该类是一个缓冲池，对内存数据的存储和读取进行缓冲操作，类及其成员如表3.2所示：表3.2 类Cache类图属性名称类型描述ptrint缓冲区的指针cachesizeint缓冲区的大小blocklengthint数据块长度page_faultsint未命中次数cache_contint
36、*在缓冲区中的数据块的块号数组LRU_indicatorint *记录缓冲区中各个数据块的未使用时间的数组dirty_indicatorbool *记录各个数据块是否被修改的数组cachechar *存储数据块的字符指针数组接口介绍：1、int in_cache(int index, Cacheable *rt)：输入：数据块块号，数据块所属的缓冲区输出：数据块在缓冲区中的位置功能：在缓冲区中寻找指定的数据块2、bool read_block(Block b, int i, Cacheable *rt)：输入：字符数组，数据块块号，数据块所属的缓冲区输出：读取成功与否功能：从缓冲区内读出一个数
37、据块，将其内容写入字符数组中3、bool write_block(Block b, int i, Cacheable *rt)：输入：字符数组，数据块块号，数据块所属的缓冲区输出：写入成功与否功能：将字符数组的内容写入缓冲区中的指定块4、bool fix_block(int i, Cacheable *rt)：输入：数据块块号，数据块所属的缓冲区输出：锁定成功与否功能：在缓冲区中锁定指定的数据块5、bool unfix_block(int i, Cacheable *rt)：输入：数据块块号，数据块所属的缓冲区输出：解锁成功与否功能：解锁缓冲区中指定的数据块6、void unfix_all()
38、：输入：无输出：无功能：将缓冲区中所有被锁定的数据块解锁7、void set_cachesize(int s)：输入：缓冲区大小输出：无功能：重置缓冲区8、void flush()：输入：无输出：无功能：将缓冲区的数据块写入磁盘（3）类 Cacheable该类将类BlockFile和类Cache进行连接，实现文件数据块操作的缓冲，类间关系如图3.2：图3.2 Cacheable类关系图Cacheable类中有两个成员，第一个是BlockFile类的指针对象file，第二个是Cache类对象cache。（4）枚举类型uses 该枚举类型用来标记缓冲区中的数据块状态，成员如图3.3：图3.3枚举类
39、型3.2.2 存储结构该模块主要实现四叉树的数据结构以及轨道数据的逻辑存储。图3.4 存储结构类关系图（1）类QuadTree该类继承自类Cacheable， 主要实现四叉树的配置、根节点的创建以及和树的基本信息的保持与读取。类及其成员图如表3.3所示：表3.3 类QuadTree类图属性名称类型描述size_blockint数据块的长度num_points_cellint单个结点下数据点个数splitting_factorfloat分离因子merging_factorfloat合并因子num_of_dataint数据点总数量rootint根结点块号root_is_databool根节点是否有
40、信息num_trajectorysint轨道数量trajectoryvector数据点集合接口介绍1、void RangeQuery(double xmin, double xmax, double ymin, double ymax, double starttime, double endtime)：输入：横纵坐标上下阀值，时间的初始值和终止值输出：满足条件的点的集合功能：实现范围查询2、void read_header(char *buffer)：输入：字符指针数组输出：无功能：从内存中读出树的基本信息3、void write_header(char *buffer)：输入：字符指针数组
41、输出：无功能：将树的基本信息写入内存中4、int get_num()：输入：无输出：数据点的总数量功能：获取树中数据点的总数5、vector get_trajectory(int ID)：输入：轨道ID号输出：指定的轨道功能：从文件中获取指定ID号的轨道（2）类QuadNode该类主要实现四叉树的创建和树的结点信息的保存与读取，类及其成员图如表3.4所示：表3.4 类QuadNode类图属性名称类型描述blockint当前结点存储的数据块块号num_pointsint当前结点含有的数据点总数pvector当前结点含有数据点的集合block1Int第一个孩子结点存储的数据块块号block2int
42、第二个孩子结点存储的数据块块号block3int第三个孩子结点存储的数据块块号block4int第四个孩子结点存储的数据块块号hashtable_blockint当前结点下的哈希表存储的数据块块号leafbool当前结点是否是叶子结点dirtybool当前结点信息是否已经修改接口介绍：1、void read_from_buffer(char *buffer)：输入：字符指针数组输出：无功能：从内存中读出当前结点信息2、void write_from_buffer(char *buffer)：输入：字符指针数据输出：无功能：将当前结点信息写入内存3、bool Build()：输入：无输出：树是否
43、建立成功功能：建立四叉树4、void RangeQuery(double xmin, double xmax, double ymin, double ymax double starttime, double endtime)：输入：横纵坐标上下阀值，时间的初始值和终止值输出：横纵坐标上下阀值，时间的初始值和终止值功能：实现范围查询5、bool FindTrajectory(int ID)：输入：轨道ID号输出：是否找到该轨道功能：获取当前结点中指定ID号的轨道6、_AddChild(Point nCornerTL, Point nCornerTR Point nCornerBL, Poin
44、t nCornerBR)：输入：矩形区域四个角的坐标输出：一个新的结点功能：添加子节点7、bool _SubDivide()：输入：无输出：是否分割成功功能：对满足条件的结点进行分割8、bool _SetCorners(Point nCornerTL, Point nCornerTR Point nCornerBL, Point nCornerBR)：输入：矩形区域四个角的坐标输出：设置是否成功功能：设置当前结点所代表的矩形区域的四个角点坐标9、double GetStartTimevector point)：输入：数据点集合输出：最小时间戳功能：获取当前结点下数据点中最小的时间戳10、dou
45、ble GetEndTime(vector point)：输入：数据点集合输出：最大时间戳功能：获取当前结点下数据点中最大时间戳（3）类HashTable该类实现哈希表的存储，类及其成员图如表3.5所示：表3.5 类HashTable类图属性名称类型描述blockint哈希表所在数据块块号flagbool当前是第一级还是第二级哈希表numint第一级哈希表中结点数量num_hashnodeint第二级哈希表中结点数量dirtybool哈希表信息是否修改hashnode_setvector第二级哈希表中哈希结点结合block_setvector第二哈希表所在数据块块号集合接口介绍：1、void arrange()：输入：无输出：无功能：构成两级哈希表，并保存信息2、void read_from_buffer(char *buffer)：输入：字符指针数组输出：无功能：从内存中读取哈希表信息3、void write_to_buffer(char *buffer)：输入：字符指针数组输出：无功能：将哈希表信息写入内存中（4）类HashNode该类主要实现哈希结点的保存与读取，类及其成员如