子图同构查询是指在给定的数据图中搜索所有与查询图结构相同的子图。子图同构的研究在多种领域被广泛应用,例如,蛋白质相互作用分析,化合物研究,图分类,场景分析,电子电路的计算机辅助设计等等。在理论上,子图同构查询属于NP-Complete问题,但研究者在真实数据集上做了大量的工作以期在合理的时间内解决这个问题。为了进行高效的子图同构查询,需要为数据图构建相应的索引,但是现有的索引构建方法效率低、扩展性差。因此,本文针对子图同构查询中数据图的索引构建问题展开研究,具体研究内容如下。首先,通过深入分析现有的子图同构查询中数据图的索引构建方法,发现现有方法效率低、扩展性差的原因是:(1)在邻居结点中分步查找等价结点时存在冗余计算,导致效率低;(2)索引构建过程中,中间结果数据量大,导致扩展性差。其次,提出排序加验证求解等价结点的思想,并设计相应的算法gIndex BasedSV来提升等价结点查询效率。gIndex BasedSV算法将结点按照标签分组,组内排序找到具有等价关系的结点后,对于没有等价关系的结点,进一步验证其隶属的等价关系,减少了对结点的重复计算,提高了索引构建的效率。再次,提出两次排序求解等价结点的思想,并设计相应的算法gIndex BasedTS,进一步提升索引构建的效率和扩展性。gIndexBasedTS算法根据结点等价的定义,将等价结点用两种邻居信息来表示,将算法的空间复杂度降为线性。通过两次排序,gIndex BasedTS算法避免了gIndexBasedSV算法在验证阶段的高昂代价,进一步提升了索引构建的效率。最后,基于不同规模的数据集,通过实验对本文所提出的索引构建算法的效率和扩展性进行了验证。