Abstract: Since online information changes frequently, being able to quickly detect changes in XML documents is important to Internet query systems, search engines, and continuous query systems Most previous work in change detection on XML or other hierarchically structured data uses the ordered tree model, with the best complexity of O（n log n ）, where n is the size of the document The best algorithm for unordered mode achieves polynomial time in complexity In this paper, a Key path based change detection algorithm named KF Diff+is represented, which transforms the traditional tree to tree correction into the comparing of the Key trees which are substantially label trees without duplicate paths, with the complexity of O（n） , where n is the total number of nodes in the documents In addition, KF Diff+is tailored to both ordered trees and unordered trees, which is also a significant difference compared with the previous work Experiments show that KF Diff+can handle XML documents at extreme speed