| 基于改进B+树索引的结构连接算法 |
| |
| 引用本文： | 吴恒山,徐晓军,桂浩. 基于改进B+树索引的结构连接算法[J]. 计算机工程, 2005, 31(16): 86-88 |
| |
| 作者姓名： | 吴恒山 徐晓军 桂浩 |
| |
| 作者单位： | 华中科技大学计算机科学与技术学院,武汉,430074;华中科技大学计算机科学与技术学院,武汉,430074;华中科技大学计算机科学与技术学院,武汉,430074 |
| |
| 摘 要： | 基本的结构连接是XML数据库查询处理的一个核心操作。Stack_Tree_Desc_B＋算法能够有效地跳过不参加连接的后代，但跳过祖先的能力不强。通过对B＋树叶子结点的每一项增加了parent和nextNeighbour指针，该文提出了一种改进算法Stack_Tree_Desc_B＋_pn。改进算法不但具有较强的跳过后代的能力，而且具有较强的跳过祖先的能力。实验表明Stack_Tree_Desc_B＋_pn算法可以有效地减少I/O次数，具有更高的性能。
|
| 关 键 词： | XML数据库 结构连接 B+树 |
| 文章编号： | 1000-3428（2005）16-0086-03 |
| 收稿时间： | 2004-06-28 |
| 修稿时间： | 2004-06-28 |
A Structural Join Algorithm Based on Improved B+ Tree Index |
| |
| Wu Hengshan,Xu Xiaojun,GUI Hao. A Structural Join Algorithm Based on Improved B+ Tree Index[J]. Computer Engineering, 2005, 31(16): 86-88 |
| |
| Authors: | Wu Hengshan Xu Xiaojun GUI Hao |
| |
| 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. |
| |
| Keywords: | XML database Structural joins B+ tree |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
