摘要： 基本的结构连接是XML数据库查询处理的一个核心操作。Stack_Tree_Desc_B+算法能够有效地跳过不参加连接的后代,但跳过祖先的能力不强。通过对B+树叶子结点的每一项增加了parent和nextNeighbour指针,该文提出了一种改进算法Stack_Tree_Desc_B+_pn。改进算法不但具有较强的跳过后代的能力,而且具有较强的跳过祖先的能力。实验表明Stack_Tree_Desc_B+_pn算法可以有效地减少I/O次数,具有更高的性能。

关键词: XML数据库, 结构连接, B+树

Abstract: The basic structural join is a core operation in XML query processing. Although the Stack_Tree_Desc_B+ algorithm can effectivelyskip descendants without mathces,it is not efffective in skipping ancestors.By adding the parent and next neighbour pointers among the leaf recordsof the B+ tree,the paper proposes the Stack_Tree_Desc_B+_pn algorithm. The algorithm can effectively skip both ancestors and descendants that donot participate in a join, and the experiment shows that the improved algorithm has better performance.

中图分类号: 

• TP311.13