随着复杂多元社交信息网络的广泛应用,关联数据对于人们周围的现实世界和社交网络而言具有越来越重要的地位。如Facebook拥有十亿多的用户。图,作为一种通用化的数据结构,对于表达复杂的结构化和半结构化数据,例如wikipedia,twitter,free-base等社交网络数据,具有重要意义。其中一个重要应用是,如何在一个给定的大规模图中高效地查询两个给定结点之间是否存在路径,即可达性查询处理。然而随着图数据的持续爆炸式增长,传统方法由于存储和时间局限性,很大程度上限制了它们在大规模图数据中的应用。因此,如何保证在拥有紧凑存储结构的前提下,以更高效的时间解决大规模图数据可达性问题,依然具有极大挑战性。基于遍历树图划分和连续重编码的索引策略Interval-Index,提出了一种拥有紧凑存储结构且能保证高效查询效率的大规模图索引。Interval-Index索引技术通过图划分提高了图处理的局部性和并行性,并在划分基础上对大规模图数据的存储结构进行设计,确保索引结构具有较高压缩比。为了提高数据访问的顺序性,方便建立高效索引,Interval-Index对每一个遍历树分区进行连续重编码。同时重编码策略使得后续基于变长字节的邻接表压缩具有更高的压缩效率。利用基于遍历树生成图的索引结构,可以通过二分查找实现对结点快速定位,提高了查询处理速率。此外,Interval-Index采用mmap虚拟内存技术实现对数据的按需调入,提高了内存利用率和数据载入效率。通过对多种真实图和合成图在可达性查询处理上的存储性能和速度性能方面的测试。Interval-Index方法在存储空间上比Feline至少降低了23%,在查询处理时间上比Feline至降低了20%。实验表明,随着数据集大小的增长,Interval-Index在存储空间和查询处理时间上都大致呈亚线性增长;相对而言,Feline的扩展性则较差,尤其是在查询处理时间方面相当逊色于Interval-Index。