在外存模式图处理系统处理大规模图数据时,由于图应用访问的随机性和图数据的低局部性,导致此类图处理系统在访问图数据时产生大量的外存储器随机I/O请求,从而严重影响文件缓存命中率,削弱I/O性能。因此,如何优化此类外存模式型图处理系统的I/O性能是提高图处理效率的关键。通过对外存模式图处理系统X-Stream、GraphChi和PrefEdge的I/O处理原理进行分析和对比,探讨了各方案的优势与局限性。在不改变图处理模型和用户操作复杂度的前提下,提出了基于图结构逻辑关联性进行图数据布局的I/O优化方案,设计以广度优先搜索访问序列作为图节点偏序关系进行图节点号映射布局,提高图遍历访问顺序性与局部性的方法BOGL。建立BOGL的BFS访问多叉树,给出图邻接矩阵,并统计分析布局前后的顺序I/O请求平均次数和图邻接矩阵非零元素的分布,论证了BOGL数据布局算法提高了图遍历的顺序性和局部性,从而可提高图处理的性能。开发了支持BOGL算法的图处理引擎原型系统BOGLE,主要包括预处理模块、加载模块、计算模块和预取模块,相比X-Stream和GraphChi图系统,使用BOGLE可以不改变其原有图编程模型,不增加用户操作复杂性,并且BOGLE可以和现有图处理系统结合使用;相比PrefEdge系统,尽管其已经专门面向图处理过程优化缓存,增加BOGLE数据布局优化后进一步提高了I/O效率。通过对不同来源、类型、尺寸的图数据集重新进行数据布局,对比测试布局前后的图处理应用性能,验证了BOGL数据布局策略I/O优化的有效性。将BOGLE用于SimPrefEdge和GraphChi图处理系统中,相比于原系统,对于高密率、平均度较高的“肥胖型”图数据集,采用BOGLE进行数据布局之后,其图遍历过程中I/O性能都有一定的提升,从而改善图处理效率。