随着移动技术进步和移动应用深入生活,移动对象规模及由其产生的信息量急速增长,促使移动对象数据库迅猛发展。作为提升移动对象数据库查询效率的关键技术,移动对象索引结构及其相应算法的优劣直接影响到应用的性能表现。由于移动对象新特性使得传统数据库的索引结构不能被直接继承使用,新的移动对象索引结构不断被提出,大致可分为管理移动对象的过去信息历史信息索引和管理移动对象近期及未来信息的预测查询索引两大类别。但是,移动对象索引技术还没有达到可以进行大规模商用的程度,移动对象索引的性能还需要进一步提高。通过对移动对象的数据特性的研究,我们总结了移动对象管理的难点,结合前人的工作,提出了高效的索引结构和相关算法。首先,针对移动对象查询过程中出现的候选查询范围过大问题,提出了基于时间域、速度域和空间域的多域划分技术,其中时间域提供处理移动性的能力,速度域划分负责缩减候选查询范围,空间域划分结合空间填充曲线完成高维位置属性维化。多域划分使得每个划分对应的查询候选范围大幅减小,从而获得较小的移动对象候选集,减小了查询耗费。在多域划分的基础上,设计实现了移动点状对象索引MPB-tree。以该结构为平台,证明了多域划分的可行性和有效性,验证了对于多域划分的定性和定量推理,得到了关于最佳多域划分参数的计算方法。MPB-tree使用空间填充曲线结合空间域划分将高维移动对象一维化,其中空间填充曲线的秩对索引效率有直接影响。通过对查询过程中节点访问问题进行研究,推导出MPB-tree中空间填充曲线秩与多域划分参数之间的关系,设计了自适应的空间填充曲线秩,提出了以此为基础的自适应移动点状对象管理机制。其次,针对移动多边形对象形状不规则、拓扑和距离计算复杂度高的问题,提出使用基于时间参数化外包矩形和时间参数化多重内接圆的多重时间参数化近似表达来分别对移动多边形的内外边界进行拟合。多重时间参数化近似表达能够在索引的叶子节点入口中代替移动对象,参与更新与查询过程,完成组织和过滤任务。提出了基于多重时间参数化近似表达的M2TPR-tree及其相应算法,验证了多重时间参数化近似表达在拟合移动多边形对象方面的优势。多重时间参数化近似表达会引起叶子节点入口尺寸增大,引起索引高度的增长,导致索引结构性能退化。根据时间参数化多重内接圆不参与结构组织的特点,提出使用单独的哈希结构对其进行管理,在不影响查询性能的同时解决了索引退化问题。针对TPR*-tree周期性整体重建引起的服务不连续,采用时间域划分策略,以时间域上的多子树交替更新代替周期性整体重建,提高了索引结构的可用性。另外,本文还针对基于位置服务中最常见的kNN查询进行了特别的研究。在点状移动数据查询方面,提出了基于MPB-tree的半径迭代算法,利用多域划分的优势,提高了点状移动对象kNN查询的效率。移动多边形对象的kNN查询方面,提出基于多重时间参数化近似表达分支界限算法。通过研究移动点、TPBR和TPMultiEC之间的空间关系及距离计算,得到了基于TPBR和TPMultiEC的分支界限查询距离度量。通过低误差的距离度量,索引结构遍历过程中的剪枝效果得到大幅提升,查询过程中的节点访问数量明显下降。本文通过实验性研究,证实了以上理论的正确性和方法的高效性,并通过大量序列对比实验,初步掌握了这些结构和方法的性能规律,为实用推广和更深层次的研究奠定了良好的基础。