基于节点的索引

基于节点的索引本质上即是将XML数据分解为数据单元的记录集合，同时在记录中保存该单元在XML数据中的位置信息。与基于路径的索引不同，基于节点的索引打破了必须通过标签路径查找节点这一限制，将XML数据分解成规范形式的节点记录。由于保存了节点的位置信息，而且能够很好地结合到成熟的关系数据库管理系统中，因此它是目前应用最广泛的一种索引。

根据对位置信息的编码方式不同，基于节点的索引一般可以分为一下几类：

1. 基于前缀的索引

基于前缀的索引主要是根据Dewey[12]编码生成的索引，文献[13]的 ORDPATH 编码采用的也是类似的方法,并给出了压缩 ORDPATH的方法，该方法已应用于SQL Server 2005的索引组织中。

前缀编码的基本思想是直接将一个节点的双亲节点的编码作为该节点编码的前缀，对于前缀编码，要判断一个节点v是否另一个节点u的后裔，只要判断u的编码是否v的编码的前缀。前缀编码索引的一个重要性质是它们的字典有序：以节点r为根的子树中的任意一个节点u，它的前缀编码c(u)大于（小于）它的左兄弟子树（右兄弟子树）中所有节点的前缀编码。因此，基于前缀的索引不仅能够有效地支持包含关系的运算，而且能够有效地支持文档位置关系的计算。

2. 基于区间编码的索引

对于区间编码索引,树T中的每一个结点被赋予一个区间编码[begin,end],满足:一个结点的区间编码包含它的后裔结点的区间编码.也就是说，树T中 的节点u是节点v的祖先，当且仅当start(u)

第一个区间编码方案是Dietz编码,树T中的每一个结点被赋予一个具有先序遍历序号和后序遍历序号的二元组.由于树T中的一个祖先结点u在先序遍历(后序遍历)中必然出现在它的后裔结点v之前(之后),因此, 节点u和v是祖先/后裔关系,当且仅当pre(u)

另一个区间编码索引的典型例子是XISS索引，它为每个节点赋予一个数字对，其中order为扩展的前序编码，size为节点的子孙的范围。对一棵文档树中的任意节点X和Y，当且仅当order(x)

XISS索引通过将原始查询语句分解为子表达式。然后分别针对这些子表达式实现查询，最后对这些中间结果进行联结获得查询结果集。从而能较好地支持含通配符的查询语句。不过，它是对每一个中间结果进行联结后得到最终查询结果。虽然这样一种方法的确能够解决所有的通配符问题，可是，这种中间结果的联结很有可能是非常耗时的，特别是对于长路径的简单表达式。

两种索引机制的比较

基于路径的索引主要基于节点合并的策略，通过节点等价、路径等价等技术，得到比原始文档小得多的索引结构，它的结构仍然是树型的，所以在处理查询时，基本上仍须遍历整个索引树才能得到结果。基于路径的索引可以很好地支持简单路径表达式的查询，但是对于正则路径表达式，它效果不是很理想。

基于节点的索引通过编码技术索引每一个节点，节点之间的结构关系通过编码可以在常数时间内确定它可以很好地支持正则路径表达式，但是对于长的路径表达式，尤其是在查询产生的中间结果很多的时候，节点索引的连接操作代价高昂。

基于路径的索引和基于节点的索引各有优缺点，但可以优势互补。目前在实际应用中，基于节点的索引应用更为广泛，研究得也比较成熟，因此，达梦公司有关XML索引结构研究主要以基于节点的索引为主，并适当参考基于路径的索引加以改进。

• 上一篇:讲解Javascript的splice函数
• 下一篇:讲解Javascript的sort函数