移动对象的存储和查询系统设计与实现

与线段模型相比，这种模型基本上适用于任何形状的轨道，其精度取决于点样时间点，而这时间点可随应用系统的实际应用而变化。本论文中讨论的移动对象的存储和查询，都在此模型基础上提出。

2.3 基于Quadtree和Hash表的移动对象索引

在移动对象数据库中，通常管理着非常庞大的移动对象。在查询处理时如果扫描所有的移动对象将会极大地影响系统性能。为了减小搜索时间，就必须对移动对象进行索引。移动对象的索引方法通常借鉴于空间数据索引技术，这些索引方法对移动对象的索引具有很好的借鉴意义，但是它们并不能直接用于移动对象的索引。这是因为上述方法更多地考虑查询效率，而没有着重考虑索引的更新代价。在移动对象数据库中，移动对象的位置更新会引起索引结构频繁的动态变化，因此，需要重点考虑索引的更新性能。为r提高查询效率，引入了标识查询；为了提高更新性能，引入了改进的Quadtree。因为Quadtree结构简单，更新时不需要对树进行平衡调整，所以可以提高更新效率。

QuadTreeNENWSWSEHashTableHashTableHashNodeHashNodePageNodePageNode...PageNodeHashTable...HashTable...HashNode

图2.4 索引结构图

Quadtree是基于空间划分的时间索引，主要适用于二维空间(分支数为4)，也可以推广至更高维以分支数扩大到2的d次幂)。如图1所示，它基于递归分解的原则，不断将空间四等分成东北、西北、西南、东南4个象限，直至每个子空间

7

中的对象数目不大于某个阈值。四叉树结构简单，进行空间搜索时，性能较高；可以索引多种对象，如点、曲线等。

为了在空间索引的基本上再添加时间索引，我们又用到了HashTable。我们的数据全部存储在磁盘的文件块中（下面将在介绍），每个块的大小一般是固定值，数据量过大时，一级哈希表可能存储不下，所以我们用到了两级哈希，这样的话大大增加了数据存储量上限。在哈希表结点中，我们给出了结点中所有点的最小时刻和最大时刻，也就是二级时间索引。

下面先简单介绍图2.4中各点的含义，更具体的模块信息请参考论文第3中的系统实现：

我们先假设所有轨道的数据都存在一个vectorP里在，Point就是点模型中所提到的四元组。P中所有点的横纵坐标的最大最小值形成了图2.4中的大矩形，将该矩形中的点数目超过阀值，将此矩形分裂（四叉树的分裂），递归处理，将得到图2.4中所示的四叉树（四叉树结点具体存储信息请参考第三章系统实现）。图2.4中所标的四叉树中的圆形代表非叶子结点，方形代表叶子结点。叶子结点里用哈希表存储了该空间范围内的所有点信息。

一级哈希表对应了多个二级哈希表，一个二级哈希表对应N个HashNode，其中第i个HashNode存的是轨道i里的点。由于存储块大小有限，一个二级哈希表只能存m个HashNode,但轨道数N>m，这也是二级哈希表的作用。对应关系是，假设一个二级HashTable最多存n个HashNode，一个一级HashTable最多存m个二级HashTable，这们0~n-1的轨道数据存放在第一个二级HashTable中，n~2n-1的轨道数据存放在第二个二级HashTable中，依此类推。这样的话，哈希表所能存的轨道数为m*n。通过上面的哈希映射，我们能很块将QuadNode所述的空间范围中某一轨道的数据放入相应的HashNode里。由于数据量巨大，一个哈希结点是无法存储所有点的，所以又引进了分页机制，用链表的形式将所有点按数目划分成一个个的页并形成链表，每个PageNode中，同样有该页中的时间最小值和最大值，也就是时间索引。

2.4 磁盘块存储技术

为也能将图2.4所述的逻辑结构存入磁盘中，并从磁盘中恢复此结构，我们用

8

到了磁盘块存储技术。

我们将一个磁盘文件以某一固定的大小（比如4096B）来划分成一个个的块，存储每一个逻辑结点时，以此块为分配单元。图2.4中所示的每一个逻辑结点，包括QuadNode，HashTable，HashNode，PashNode存储时都会对应磁盘文件中的一个块，块用唯一的非负整数作为块号。也就是每一个逻辑结点对应一个块号，这个块号所对应的块里将存储这个逻辑点的所有信息。

至于如何存储这些信息，每个结点都封装一个write_block()和read_block()函数，这两个函数是对应的，分别实现逻辑点自已的信息存储和读取方式，相当于系列化和反系列化。

图2.4中各逻辑结点间的对应关系，其实就是用这些块号来描述的。最后说明一下文件块中比较特殊的一块，也就是第一块，这块就文件创建时就自动分配的，里面存有图2.4中结构中最重要的一个逻辑结点的块——四叉树根结点的块。

按照上述方法，就能将图2.4中各逻辑结点信息存入磁盘块文件，并从磁盘文件中恢复此逻辑结构或读取某一特定逻辑结点的信息。

2.5 本章小结

本章主要介绍一些相关的技术，第一节介绍移动对象数据库的基本概念；第二节介绍移动对象的数据建模，其中提出了一种线段模型和一种点模型，点模型为我们所讨论的主体；第三节介绍点模型上的基于Quadtree和Hash表的移动对象空间和时间的索引；第四节介绍磁盘块存储技术。

9

第3章 系统实现

3.1 系统介绍

系统主要开发环境在VS2008上，开发语言为C++。程序主界面用的是XTremeToolkitPro v12.1.1开发包，3D模拟用的是OpenGL。

3.2 模块介绍

本节主要对系统设计中的各模块进行介绍，主要介绍系统设计中的主要类的成员及其接口。 3.2.1 内存处理

该模块主要实现数据的写入和读出

图3.1 内存模块类关系图

10