论文部分内容阅读
本文提出一种对XML文档建立索引的新方法。该方法支持分支查询和带有通配符的查询。同时设计了一种通过一次遍历XML文档就可以建立索引的算法，XML文档被看作一条线，文档中各个元素被看作这条线的线段。查询XML文档就相当于指定相应的线段。使用一种基于区间的动态树标记模式，每个线段都被给予一个区间。然后把XML文档中所有的路径插入到一个trie结构中，并使用B+树管理这些区间。定义了三种运算，这些运算使不同B+树上的区间集合可以相互运算。三种运算对应算法的最差情况时间复杂度是O(m+n)。分支查询最后的结果可以通过这些运算直接得到。