随着大数据时代的来临,数据规模呈指数级速度增长,越来越多的复杂结构数据需要用图数据结构模型来表示。即点代表事物,边代表事物之间的关系。在现实生活中,图数据模型有着十分广泛的应用前景,其中包括:社交网络、蛋白质交互网络、交通网络等,因此如何高效而快速地检索大图数据成为近几年来研究的热点。可达性查询是图查询中一个主要的研究方向。然而,实际应用中,和传统的可达性查询相比,k步可达性查询可以为用户提供更多的有用信息,因此k步可达性查询问题成为图数据管理中的热点问题之一。本文从以下几个方面对k步可达性查询的处理方法进行了研究,具体研究内容如下:首先,对现有k步可达性查询算法进行了详细分析,发现现有方法在处理k步可达性查询时,存在大量冗余顶点对的重复判断现象。其次,在BiRch-BTL算法的单向双区间标签和四种剪枝策略的基础上提出了新的查询方法——基于哈希表的单向搜索算法(A unidirectional search algorithm based on hash table,UniRch-Hash),该算法采用哈希表来存放已经判断过的不可达顶点对和相应的步数,防止对不可达顶点对造成重复判断,从而提高了算法的性能和系统的响应速度。再次,经研究发现UniRch-Hash算法存在一些不足,即该算法不适合处理不同分支顶点之间的k步可达性查询,为了解决上述问题,本文接着提出了一种双向双区间标签索引,RE-UniRch-Hash算法就是在新的区间标签索引的基础上实现的。最后,在20个不同特征的数据集上进行实验,并从索引构建时间、索引大小、查询时间、访问顶点数量、哈希表占用空间大小和扩展性等多方面进行验证,实验结果表明,UniRch-Hash算法和RE-UniRch-Hash算法都优于现有的多种算法。