摘要：XML数据处理中一个基本问题是树形数据排序．本文针对已有算法的不足提出了一种XML文档多核并行外存排序算法---XPSort ．XPSort扫描XML文档产生相互独立的排序任务，利用多核CPU对任务进行并行处理；同时，利用数据压缩、单临时文件以及避免子树匹配等策略，有效地减少磁盘I/O ，提高排序性能；它克服了NEXSORT算法没能有效利用内存空间、存在大量随机I/O的问题以及难以处理“右深树”的缺陷，也克服了HERMES的数据冗余、大量磁盘开销等缺点．文章对不同特性的XML文档开展了大量比较实验，结果表明XPSort优于已有算法，所提优化方法是有效可行的．

关键词：xml文档 树形数据 排序算法 并行算法 

单位：浙江工业大学计算机学院; 浙江杭州310023; 杭州市公安局交通警察局科研所; 浙江杭州310014