基于位置信息服务(Location Base Service, LBS)设备的流行使得与位置相关的服务已经慢慢走进了人们的日常生活当中。例如，移动电话，便携式笔记本(PDA)，车载GPS等电子产品都可以提供位置查询的功能。如今，支持LBS的设备的普及要求LBS更加大众化和多样化，其中带有关键字的移动对象的最近邻查询就是基于位置信息服务的其中之一。例如，在道路网中，一辆正在高速公路上行驶的汽车利用GPS系统查询距离自己最近的去往“鞍山市中心”的高速公路出口；在数字化战场上，一辆坦克查询离自己最近的“敌军”指挥部；行人查询离自己最近的“11路”公交车站或“乐购”超市等等。目前，虽然时空数据库中有关最近关键字查询算法的研究工作已经取得了许多成果，但是大多数的讨论都是简单的查询，在移动对象高频率的移动环境下表现出来的性能却不佳。因此，本文主要从这一问题着手，进行了更深入的学习和研究。首先，本文根据带有关键字的移动对象在道路网中的分布及运动特性，利用网格文件和压缩四分树来处理移动对象频繁更新的问题，然后利用Voronoi图来处理最近关键字索引的问题，提出了一种基于区域覆盖的带有关键字的网格四分树(Keyword Virtual Grid Quadtree, KVGQ)与Voronoi图相结合的Vor-KVGQ索引结构。该索引充分的把网格文件、压缩四分树和Voronoi图的优点结合起来，最大限度的支持最近关键字索引并且支持动态索引。Vor-KVGQ索引通过索引移动对象所在的网格单元代替索引移动对象本身的位置，这样做大大的减少了由于移动对象本身位置的频繁更新而引起的索引结构的更新。其次，以Vor-KVGQ索引结构为基础做了能够提高查询效率的最近邻查询，根据网格文件的分布特点建立与之对应的Voronoi图。利用上述思想设计了最近邻查询算法，并且证明了算法的正确性与高效性。最后，为了证明Vor-KVGQ索引结构和最近邻查询算法的性能，本文做了仿真实验，实验结果表明Vor-KVGQ是一种高效的时空数据库索引方法，并且基于Vor-KVGQ索引结构提出的最近邻查询算法具有很好的性能，大大提高了时空数据库的查询效率。