基于互关联后继树的XML索引技术

作者：雷向欣; 胡运发; 杨智应; 刘勇; 张凯

来源：计算机研究与发展, 2005, 42(7): 1261-1271.

• XML
• XPath
• 互关联后继树
• 索引
• 查询

提出了一种新的根树节点编码方法--基于叶序区间的节点编码(LOINS).编码方法只需对根树后序遍历一次即可完成,能实现常数时间内对任意两个树节点间前后代关系的判断.同时,结合互关联后继树模型(IRST)的标引性、可压缩性等特点,提出基于IRST的根树索引模型IsBaRTI-Ⅰ,及对该模型空间优化的索引模型IsBaRTI-Ⅱ.IsBaRTI-Ⅰ,Ⅱ采用树节点名称(标签)及其在根树(XML文档树)中的出现计数索引节点间的父子关系和节点叶序区间编码,实现索引结构和节点编码的相互统一.IsBaRTI-Ⅰ,Ⅱ索引建立时间、空间代价小,可快速查询满足XPath表达式在XML文档树中的节点序列和路径.

• 单位
  复旦大学