随着结构化数据在互联网应用中的大量出现,对复杂数据进行图建模在近年来越来越流行。图索引问题在图数据库应用中至关重要。本文主要研究了图数据库上的图索引问题。本文提出了MSTA索引方法及MSTA索引方法上的子图查询算法、超图查询算法、相似性查询算法和相关性查询算法。MSTA索引方法利用最小生成树作为数据特征,将所有的最小生成树依据边序列的包含关系和最大公共子图距离度量组织成MST树索引结构,高效的支持各种查询算法。传统索引方法的索引大小和索引建立时间是MSTA索引方法的数十倍,甚至上百倍。MSTA索引方法上的查询算法都是近似的,返回的结果是最好的部分结果。我们还分析了MSTA索引方法的原理和正确性。实验结果辅证了该索引方法的高效索引性能及查询性能。本文提出了RQ索引方法及RQ索引方法上的相关性查询算法。我们分析了相关性查询算法的代价组成,从而得出代价影响的两个结论;分析了已有索引方法在支持相关性查询上的不足。RQ索引方法,利用四种不同维度选择策略得到高维空间矩阵作为数据特征,将所有的高维空间矩阵组织到R树索引结构中。实验结果表明,RQ索引方法具有优秀的索引性能,并具有很好的可扩展性。RQ索引方法可以高效的支持相关性查询。