近年来,随着科技的发展,与位置服务有关的定位技术、导航技术、监控技术已经广泛走进现实生活。如今,手机、车载设备等电子产品提供位置服务相关功能越来越普遍。这些应用的技术基础空间数据库的研究也越来越成为热点问题之一。其中移动对象的K近邻查询就是空间数据库中重要的应用之一。例如,在交通管理中,一辆出租车要查找当前时刻距它最近的前K个旅馆或加油站,使出租车司机可以选择一个离自己不远又顺路的结果；在战争中,一个战士要查找自己附近的人员的位置情况；在航海中,一艘轮船要查询距离自己较近的若干艘轮船等。尽管K近邻查询的研究工作已有很多成果,但对在大量移动对象频繁移动的环境下,现有索引在高效更新,快速近邻查询方面表现不是很理想。因此,本文从该问题作为切入点,进行了深入研究。首先,本文通过分析移动对象在频繁移动情况下进行k近邻查询的难点——查询与更新的特性,利用网格文件解决频繁更新的问题,利用Voronoi图解决近邻查询的问题,提出了一种基于区域覆盖的虚拟网格四分树(Virtual Grid Quadtree, VGQ)与Voronoi Diagram相结合(Vor-VGQ)的索引结构。结合两种结构的优点,该索引适合近邻查询并且支持动态更新。它通过索引移动对象所在区域而非移动对象本身来减少由于移动对象位置改变而引起的索引结构的更新。其次,在Vor-VGQ索引结构基础上做了2种策略的K近邻处理方法。一种面向于提高查询效率的实时动态Voronoi Diagram变换策略,随着网格的变化Voronoi Diagram同步变化。在试验过程中发现路网中数据分布的相对稳定性,从而提出了面向于提高更新效率的单调动态Voronoi Diagram更新策略,最终形成依据路网分布的稳定的Voronoi Diagram结构。利用上述两种策略设计了范围查询和KNN查询的算法,并且证明了算法的准确性。最后,本文设计了实验并进行了对比分析。实验结果表明,Vor-VGQ是一种高效的空间数据索引结构,基于Vor-VGQ索引结构的KNN查询与已有B+树类算法如BX树索引查询相比效率提高三个数量级。