基于CB+-tree索引的XML时态查询技术

马 程 徐海燕 姚保峰 王 磊 朱洪浩

(1. 蚌埠学院计算机科学与技术系， 安徽 蚌埠 233000；2. 华为软件技术有限公司南京研究所， 南京 210008)



基于CB+-tree索引的XML时态查询技术

马 程1徐海燕2姚保峰1王 磊1朱洪浩1

(1. 蚌埠学院计算机科学与技术系， 安徽 蚌埠 233000；2. 华为软件技术有限公司南京研究所， 南京 210008)

针对XML时态查询问题，使用CB+-tree索引，将时态信息作为索引关键字，采用实体地址和长度随机读取查询，在叶子节点处添加新的链表节点，对叶子节点中的关键字按照tend进行二次排序，减少了查询比较次数。实验结果表明，CB+-tree索引在实现实体轨迹、快照和时间段3类时态查询时，优于B+-tree索引，特别是对于大容量的XML文档，其时态查询效果更佳。

CB+-tree索引； XML； 时态查询

随着计算机和网络技术的不断发展，XML(Extensible Markup Language)成为Web上一种信息表示与交换的标准数据格式，其存储、索引和查询成为XML相关技术领域研究的热点[1-3]。索引对查询起着重要的作用，要实现某种查询必须为其建立适当的索引机制，为此，针对时态查询效率问题，基于CB+-tree(Changing B+-tree)索引，分别实现了实体轨迹、快照和时间段查询，该方法在实现时态查询时，比B+-tree索引更高效。

1 CB+-tree原理

CB+-tree是改进B+-tree的平衡树，根节点处至少有2个子节点，包含m个关键字的中间节点，m+1个指针Pi(每个指针指向下层子节点)[4-6]。CB+-tree不同于B+-tree，其叶子节点新增3种指针。

(1) 第1种指针，用于指向同一层次节点，有前向指针和后向指针，即叶子节点之间形成一个双向链表，如图1所示。

图1 前向指针和后向指针

(2) 第2种指针，用于指向处理重复键值的查询链表(QList)，每个叶子节点中包含1个指针数组m_pointer，添加QList之后的叶子节点如图2所示。如插入的键值与叶子节点中的某个键值相同时，就在其后面分配1个链表，用来存储刚插进的新键值，插入时按照tend从大到小的顺序进行。

图2 处理重复键值指针

(3) 第3种指针，仍然指向链表，但该链表的作用是，将该叶子节点中的所有数据(不包括m_pointer所指链表中的数据)按照tend从大到小的顺序，依次插入单链表。当进行快照查询或时间段查询时，可以减少与tend的比较时间，以提高查询效率。

2 CB+-tree查询

基于CB+-tree索引，针对实体轨迹的查询、快照和时间段查询比较高效。下面分别介绍CB+-tree如何实现这3类查询。

2.1 实体轨迹查询

定义实体轨迹查询的索引关键字类型如下：

public struct KeyType

{public string id；∥ id为实体号

public int addr；∥ addr为实体在文档中的地址

public int length；∥ length为实体的信息长度

public string filename；∥ filename为XML文档的路径

}；

实体轨迹查询，需查询某个实体的历史和当前信息，以实体的ID号作为索引关键字，按照ID号从小到大的顺序，依次将所有实体插入CB+-tree。

实体轨迹查询算法描述：

Input：ID实体号；Output：满足查询条件为ID的实体历史轨迹，即实体信息XML片段。

Step1：从根节点开始，使pNode=根节点；

Step2：循环查找到第一个关键字≥ID的位置i，取pNode=pNode.GetPointer(i)。如果pNode为叶子节点，则循环停止，否则继续执行Step2；

Step3：在叶子节点中继续查找，当找到满足ID的关键字时，则通过该关键字中的addr和length，到filename中读取满足查询条件的实体信息。

2.2 快照和时间段查询

以下建立的索引，可以同时满足快照和时间段查询。

快照和时间段查询的关键字类型定义与实体轨迹关键字结构定义方式相同，但该处新增了tend和tstart字段，结构为(ID，tstart，tend，addr，length，filename)。其中tstart和tend分别表示实体号为ID的事务的开始时间和结束时间。

快照和时间段查询都需要跟时态属性进行比较，因此以每个实体的tstart作为索引关键字，根据tstart从小到大的顺序，依次将每个实体插入CB+-tree，最后在叶子节点的MPointer和m_pointer[i]的链表中将关键字根据tend进行第2次排序。

快照查询算法描述：

Input：快照查询时间snapshot；Output：满足快照时间的所有实体信息。

Step1：从根节点开始，将pNode指向根节点；

Step2：通过while循环查找到第1个键值大于等于snapshot的位置i，pNode指向GetPointer(i)所指的下一层节点，若pNode为叶子节点，循环结束。否则，继续执行Step2；

Step3：在pNode中继续查找。若pNode是第1个满足条件的叶子节点，则其中只有部分关键字的tstart满足条件。通过循环统计出满足条件的关键字个数nocount，循环nocount次可以输出该关键字中满足条件的实体信息。然后pNode通过前向指针m_PreNode指向其前一个叶子节点。若pNode非空，转向Step3继续执行，否则，循环结束。若pNode非第1个满足条件的叶子节点，到达pNode之后，通过MPointer和m_pointer[i]中关键字的tend与snapshot继续比较， 找到符合tend>=snapshot的关键字，通过addr及length取出满足条件的实体信息。pNode通过前向指针m_PreNode指向其前一个叶子节点。若pNode非空，则转向Step3继续执行，否则循环结束。

时间段查询与快照查询过程类似，找到tstart满足条件的实体之后，将时间段结束时间与各实体的tend进行比较，而快照查询直接用快照时间与tend进行二次比较筛选。时间段查询算法与快照查询算法原理相似。

3 实验结果及分析

实验环境：CPU为Intel Pentium D 930(1 G)，系统为Windows XP Professional，生成和查询XML文档的开发环境为.NET2003中的C#。实验数据来自于TimeCenter(http:∥timecenter.cs.aau.dksoftware.htm)的职工数据库。该数据库3个文件夹共有15 004个XML文件，300 000个职工的历史和当前信息。为了验证CB+-tree时态查询的高效性，将其与B+-tree索引及DOM下的时态查询作比较，其中DOM为无索引下的查询。

3.1 实验过程

(1) 分别取5 002、10 004、15 004个XML文档进行合并，合并后大小依次为85、169、254 MB。

(2) 在合并后的3个文档上分别实现文中定义的实体轨迹查询(简称Q1)、快照查询(简称Q2)、时间段查询(简称Q3)。

3.2 查询效率分析

文档大小分别为85、169、254 MB，基于DOM的实体轨迹查询时间分别为7 804、15 719和67 490 ms，而基于B+-tree和CB+-tree的查询时间几乎为0 ms，由此可知随着XML文档的增大，基于CB+-tree的实体轨迹查询效率提高显著。

表1给出了快照查询和时间段查询性能比较表。由表1可知：XML文档越大，基于CB+-tree的查询效率比基于DOM、B+-tree的查询效率提高得越显著；查询的实体数目比较小时，效率提高得更明显；基于CB+-tree的查询效率比基于B+-tree的也有所提高。基于DOM的模型未使用索引，是把整个XML文档调入内存，基于整个文档进行遍历查询。当处理的XML文档数据量较大时，存在大量无谓的数据遍历和磁盘访问问题，其性能较差。基于B+-tree查询，减少了对XML文档的遍历，但因未对实体的tend时间及重复键值进行处理，快照查询和时间段查询需与tstart满足条件的所有关键字的tend继续比较。而CB+-tree中的MPointer和m_pointer[i]指向的链表对tend进行了从大到小的排序，查询时遇到第1个tend不满足条件的数据后，该链表后面的数据不需要继续比较，减少了大量的遍历，降低了查询时间，而且能通过实体地址准确地随机定位到实体，从而提高查询效率。

表1 快照查询和时间段查询性能比较表

4 结 语

CB+-tree索引将时态信息作为索引关键字，采用实体地址addr和长度length随机读取满足查询条件的信息，在CB+-tree的叶子节点处添加新的链表节点，对叶子节点中的关键字按照tend进行二次排序，极大地减少了查询比较次数，提高了查询的响应时间。实验结果表明，CB+-tree索引在时态查询时查询效率优于B+-tree索引，尤其是对于大容量的XML文档。

[1] MENDELZON O A, RIZZOLO F, VAISMAN A.Indexing Temporal XML Documents[C]∥VLDB.Proceedings of the 30th VLDB Conference.San Francisco:Margan Kaufmann,2004:216-227.

[2] 叶小平,陈铠原,汤庸,等.时态XML索引技术[J].计算机学报,2007,30(7):1074-1085.

[3] 汤娜,刘瑞君,陈罗武,等.XML文档中时态信息存储方法研究与比较[J].计算机科学,2008,35(5):226-228.

[4] 徐红波,姚念民,韩启龙,等.支持线段查询索引结构CB树[J].计算机工程与应用,2015,51(11):114-123.

[5] 肖蒙,王梅.SHB+树:一种面向时态数据的分段混合索引[J].计算机研究与发展,2015,52(增刊l):28-36.

[6] 叶小平,林衍崇,陈钊滢,等.时态索引Txmlsindex[J].华南师范大学学报(自然科学版),2015,47(1):116-12.

XML Temporal Query Technology Based on CB+-tree Index

MACheng1XUHaiyan2YAOBaofeng1WANGLei1ZHUHonghao1

(1.Department of Computer Science and Technology of Bengbu College, Bengbu Anhui 233000, China; 2.Nanjing Research Institute of Huawei Software Technology Limited Company, Nanjing 210008, China)

Aiming at the problem of XML temporal query, this paper uses the entity address and length to access query conditions based on CB+-tree randomly. By adding new node in the leaf node, it can sort the keyword in the leaf node according to tend for two times to reduce the query times. The experimental results show that the CB+-tree index method is better than B+-tree index in the implementation of three kinds of temporal queries, such as entity track, snapshot and time period, especially for large capacity XML documents.

CB+-tree index; XML; temporal query

2016-05-30

2014年度蚌埠学院院级自然科学研究重点项目“基于时空XML数据库存储和索引技术研究”(2014ZR03ZD)；2015年度安徽省教育厅项目“基于XML的Web信息抽取关键技术研究”(11305215KJ09)；2016年度安徽省自然科学研究重点项目“XML交互式信息检索系统关键技术研究”(KJ2016A456)

马程(1980 — )，女，安徽阜阳人，硕士，讲师，研究方向为数据挖掘、时空数据库索引。

TP311.13

A

1673-1980(2016)05-0075-03