k步可达查询与现实生活息息相关，是目前研究者的热点关注问题之一，能够应用于生产生活中方方面面，例如无线传感网络，生物信息网络，社会交际网络等等。k步可达查询可以看成可达查询+长度约束k值。相比于传统的可达查询，k步可达查询能够给信息查询者提供更多更有效的信息。k步可达查询用于在给定的有向无环图中回答两点之间是否存在长度不超过k的路径。然而，现有方法处理k步可达查询时，存在索引规模大或者查询效率低的问题。
　　为了解决现有方法存在的问题，本文首先提出一种部分点构建双向最短路径索引的策略，其次基于该策略提出一种固定顶点数量的双向最短路径索引，再次基于该策略提出一种基于可达信息覆盖的双向最短路径索引，最后提出拓扑层和下沉拓扑层加速算法的查询效率。具体来说，本文主要贡献如下：
　　首先，针对现有方法索引规模大的问题，提出一种基于部分顶点的双向最短路径索引策略降低构建索引的代价，并且给出加快查询和降低索引的剪枝策略及证明：1）遍历过程中访问到已经处理过的顶点时，不更新索引并停止对该分支的遍历；2）在处理k步可达查询时，当存在一条长度不大于k的路径时，直接判定该查询满足k步可达性。基于该策略，本文提出基于固定数量的双向最短路径索引和基于可达信息覆盖率的最短路径索引。除此之外，本文在存储索引方面做了优化，1）顶点处理的序号代替顶点自身序号，从而避免排序，有效地减少了构建索引的时间；2）基于整数bit的存储方式，使用前16位存储顶点信息，后16位存储路径长度信息，从而降低索引规模。
　　其次，针对部分点的最短路径索引处理不可达查询效率低的问题，本文提出一种基于剩余图的拓扑层和下沉拓扑层索引，从而加速算法处理不可达查询时的效率。除此之外，针对不能用索引直接判定查询，本文提出远距离优先的双向遍历策略来提高处理查询的效率。
　　最后，在25个不同特征的真实数据集上将本文方法与现有方法分别从索引代价、查询效率等方面做比较。实验结果表明，本文提出的算法具有更小的索引代价和更快的查询响应速度。