基于CB＋－tree的时态XML索引动态更新方法*

马程，徐海燕

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

基于CB＋－tree的时态XML索引动态更新方法*

马程1，徐海燕2

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

针对时态XML更新问题，使用了CB＋－tree索引时态XML文档和文档添加冗余空间存储，借助时态信息索引、实体地址索引双重索引和文档冗余存储方式高效地实现文档的局部更新。实验结果表明，将实体时态信息和地址索引分离，并为文档添加冗余空间，减少了XML文档更新时间，其效率明显提高。

B＋－tree索引；动态更新；时态XML

随着XML数据的大量涌现，有效实现其存储、索引和查询一直是XML相关技术领域研究的热点，但XML文档的更新始终是XML数据操作的一个难点。目前国内外对时态XML的研究还处于起步阶段，其索引方面有了一些研究成果。例如，Alberto O.Mendelzon提出了一种TempIndex［1］索引机制，它包含三种结构：时态模式、时态深度表、cp和cp＋value表。叶小平等人［2］提出了一种时态XML查询数据模型TXQDM，在模型中引入TXQDM结点间时态连通概念，构建了结点间的一种等价关系，通过研究结点分类和等价类中结点间时态包含产生的拟序结构，从而建立了时态XML索引数据模型TXIDM。陈丽冰等人［3］基于扩展的XPath模型，构建了一种时间连通性的等价关系，并且在该关系的等价类基础上建立索引。通常XML文档部分内容更新时，大量移动数据非常耗时。针对文档更新，文章提出了CB＋－tree实体地址索引和文档增加冗余空间存储，该方法在动态实现文档的局部更新时效率较高。

1 相关技术概述

1.1 时态XML文档

XML文档可以被建模成基于XPath有序、具有边标记的结点层次图形结构［4］。为实现自身查询，以这种结构为基础，建立XML查询数据模型。时态查询XML数据模型，即在常规模型上添加时态信息［5］。

1.2 CB＋－tree原理

CB＋－tree（Changing B＋－tree）是改进B＋－tree的平衡树，根节点处至少有两个子节点，包含m个关键字的中间节点，m＋1个指针Pi（每个指针指向下层子节点）。CB＋－tree不同于B＋－tree，叶子节点新增三种指针：

（1）第一种指针，用于指向同一层次节点，有前向指针和后向指针，叶子节点间形成一个双向链表。

（2）第二种指针，用于指向处理重复键值的查询链表，每个叶子节点包含一个指针数组m_pointers［m］。如插入的键值与叶子节点中的某个键值相同时，就在其后面分配一个链表，用来存储刚插进来的新键值，插入时按照tend从大到小的顺序进行。

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

2 时态XML索引结构及文档存储方式

采用职工数据库作为实验数据集，CB＋－tree索引的关键字的结构是（id，tend，tstart，addr，length，filename）；id为实体号，tend和tstart分别设置为实体的事务结束和开始时刻，addr为实体在文档中的偏移地址，length为实体的信息长度，filename为实体的路径。

2.1 TCB＋－tree和ACB＋－tree

在CB＋－tree中间节点和叶子节点的关键字中，都包含上文提到的所有信息。根据CB＋－tree的特性，仅需从到达叶子节点的MPointer和m_pointer［m］中取出其实体的地址信息，利用文档实体的addr和length，即可随机调出全部信息，而中间节点包含的addr、length和filename，会造成索引空间的浪费。

为了解决这一缺陷，提出了建立TCB＋－tree（Temporal CB＋－tree）和ACB＋－tree（Address CB＋－tree）的双重索引，其核心仍是CB＋－tree。TCB＋－tree索引实体的时态信息，ACB＋－tree索引实体的地址信息。TCB＋－tree的关键字结构为（id，tstart，tend），tstart作为索引关键字；ACB＋－tree的索引关键字为id，其叶子节点的m_pointer［m］中链表数据字段为（id，addr，length，filename）。

2.2 添加冗余的文档存储方式

在存储时态XML文档时，为了充分利用存储空间，通常对多个实体进行连续存储，但这种存储方式很难实现文档的局部更新，尤其是对体积较大的文档。比如：在某个实体中添加或删除信息时，该实体后面所有内容都要向后移动重新写入，非常耗时。为减少移动频率，存储每个实体后紧接着写入一些冗余空白，然后再存储下一个实体的信息，如图3所示。存储方式修改后，ACB＋－tree链表中的数据需增加新的字段blankspace，更新为（id，addr，length，blankpspace，filename）。blank

space用于记录实体信息后冗余空白的大小，用户可根据需要设置

从混合烃组分的MMP实验结果得到以下认识:混合体系组分中芳香烃为主的方案的MMP最大、环烷烃为主的方案的MMP次之、烷烃为主的方案的MMP最小，这与单组分烃类的实验结果相符;与单一组分主要区别在于，混合烃组分/CO2的MMP均小于相同碳数的单组分/CO 2的MMP，这主要是混合组分中不同分子作用力综合作用的结果。

blackspace大小，随着实体信息的变化，其blankspace也相应更新。

图3 添加冗余的文档存储方式

3 更新操作

XML文档的更新包括文档的全文更新和局部更新两种形式。文章仅讨论文档的局部更新问题。实体元素的更新，主要包含元素的插入、删除和内容的修改。时态XML文档的局部更新，主要涉及到tend或tstart的变化，而父、子元素的tend和tstart具有相关性，导致实体在TCB＋－tree中的关键字信息可能需要更新，同时，实体的addr、length可能也需要更新。若是添加冗余后的更新，还需要更新blankspace。元素的更新、删除与插入原理相通，选取元素的插入操作进行效率比对分析。

3.1 基于DOM的插入

基于DOM的插入需要把整个文档先调入内存，用树形结构来存储XML文档。向实体id插入新的元素，即需要通过遍历找到相应id的子树，然后为该子树添加新的节点。该插入过程非常耗时，一是大体积文档的调入和解析非常耗时；二是需要通过遍历，才能查找到正确的插入位置。

3.2 未添加冗余空白前的插入

基于TCB＋－tree、ACB＋－tree双重索引，未添加冗余空白前的插入过程为：插入新实体，以实体id为关键字，使用ACB＋－tree索引查询，查询到id时，读取对应链表中数据（id，addr，length，filename），根据addr获取该实体的全部信息，并将其作为一个XML文档进行解析，使用XML操作中的插入函数进行插入。如果实体变化，把更新后的实体信息重新写入文档，其后的实体也全部后移、重新写入，导致需要更新所有后移实体在ACB＋－tree索引中的addr。若实体元素的插入，引起了父节点的tend、tstart或二者同时变化，还需更新TCB＋－tree。TCB＋－tree是以tstart为关键字建立的索引，根据id号查询，则需遍历整个文档，故借助辅助结构（id，oldtstart，newtstart，oldtend，newtend）记录实体更新前后的tend和tstart，采用oldstart作为搜索关键字，在TCB＋－tree中找出该实体的时态信息位置，再删除原节点，插入新节点。

3.3 添加冗余空白的插入

（1）根据输入的待插入元素的实体号id，调用ACB＋－tree的Search算法。如果未查找id，则返回false；如果查找到了，则根据该关键字中的addr和length字段，获取该实体信息的XML文档片段tempXML。

（2）调用XmlDocument的LoadXml方法，解析该XML片段，再调用DOM相应函数，将新元素信息插入。

（3）插入后，对比插入前length与当前实体信息newlength，获取addlength＝newlength－length。

（4）根据实体号id，在ACB＋－tree中查询该关键字对应的叶子节点；查询到该实体关键字后，将addlength与其blankspace比较。如果addlength大于blankspace，设置blankspace为0，记录下超出冗余空间的长度newaddrlength＝addlength－blankspace，将id的length更新为length＋newaddrlength。通过id对应的叶子节点m_pNextNode指针，循环访问后面所有的叶子节点，并将该实体后所有实体的addr改为addr＋newaddlength。如果addlength小于blankspace，可以直接插入新的内容，将实体的blankspace更新为blankspaceaddlength即可，同时将该实体索引关键字对应的length改为length＋addlength。

（5）插入新元素后，若其tend或tstart属性引起父节点tend或tstart更新，需根据父节点原tstart值，在TCB＋－tree中查询出该实体索引关键字位置，删除该关键字，再重新插入tend或tstart更新后的关键字。如果未引起父节点的tend或tstart更新，则不需要更新TCB＋－tree索引。

（6）根据id的addr起始地址，将新的XML文档内容重新写入XML文档中。返回true。

4 实验分析

实验环境：CPU为Intel Pentium D 930（1G），系统为Windows XP Professional，生成和查询XML文档的开发环境为.NET2005中的C＃，实验数据来自于TimeCenter的职工数据库。该数据库三个文件夹共15 004个XML文件，300 000个职工的历史和当前信息。

4.1 实验过程

首先，对源数据进行冗余消除。如果子节点的tend、tstart属性与父节点的属性值相同，子节点不再存储与父节点相同的时间属性，消除冗余；其次，分别取5 002、10 004个XML文档合并，合并后大小依次为86 MB、169 MB；最后，在合并后的两个文档内分别实现向100个实体中插入，实体号随机产生。

4.2 实验数据

基于TCB＋－tree和ACB＋－tree的双重索引，分析冗余大小对更新时间的影响，其实验结果见表1。

表1 冗余大小对更新时间的影响

由表1可知，冗余空白大于插入内容的条件下，冗余的大小对更新时间的效率影响不大。

基于TCB＋－tree、ACB＋－tree双重索引在图示中使用CB＋－tree来标识。由于冗余空白的更新时间很小，而基于DOM的更新时间远比用索引的更新时间大，为在图中清晰显示添加冗余空白的更新时间，实验中采取DOM更新花费时间的十分之一作为比较标准。基于CB＋－tree、B＋－tree、DOM三种方法，分别对原始文档中插入实体（即未添加冗余空白）和添加冗余空白的插入进行实验，其更新时间如图4、图5所示。对采用B＋－tree、CB＋－tree方式对添加冗余前后的更新时间进行对比，其结果如图6所示。

图4 三种方式对原始文档插入比较

图5 三种方式添加冗余空白的插入比较

图6 B＋－tree、CB＋－tree方式冗余前后对比

由图4可知，在原始文档中插入实体基于CB＋－tree和B＋－tree的更新效率比基于DOM明显提高，而且文档越大效率提高越明显，且基于CB＋－tree双重索引的更新效率比基于B＋－tree的更新效率也有提高，但是基于CB＋－tree和B＋－tree的更新时间并不理想。由图5可知，使用冗余存储方式，基于CB＋－tree的更新效率远远高于基于B＋－tree和DOM的更新。由图6可知，添加冗余后基于CB＋－tree和B＋－tree索引对时态XML文档更新的效率提高显著，但基于CB＋－tree和冗余空白的更新效率更高。

5 总结和展望

文章提出了时态和地址信息分开索引的双重索引，TCB＋－tree以tstart作为索引关键字方便时态查询，如果时态信息没有变化，则不需要更新TCB＋－tree；ACB＋－tree以id作为索引关键字，便于通过id号查询地址信息。同时，添加冗余空白减少文档更新时频繁移动重新写入的操作。实验证明，采用双重索引和添加冗余空白减少了文档更新时间，提高了文档和索引更新的效率。

［1］Mendelzon A O，Rizzolo F，Vaisman A.Indexing Temporal XML Documents［C］//VLDB.Proceedings 2004 VLDB Conference 2004.San Francisco：Margan Kaufmann Publishers，2004：216－227.

［2］叶小平，陈铠原，汤庸，等.时态XML索引技术［J］.计算机学报，2007，30（7）：1074－1085.

［3］陈丽冰，吉永杰，邓楚燕.一种基于扩展时态XML模型的索引技术［J］.微型计算机信息，2006，22（5）：301－303.

［4］郭欢，叶小平，汤庸，等.基于时态编码和线序划分的时态XML索引［J］.软件学报，2012，23（8）：2042－2057.

［5］叶小平，林衍崇，陈钊滢，等.时态XML索引Txmlsindex［J］.华南师范大学学报（自然科学版），2015，47（1）：116－120.

Dynamic Update Based on CB＋－tree Temporal XML Index

MA Cheng1，XU Haiyan2
（1.Computer Department，Bengbu College，Bengbu 233000，China；2.Nanjing Research Institute of Huawei Software Technology Limited Company，Nanjing 210008，China）

Focused on the problem of temporal XML update，this paper uses CB＋－tree to index temporal XML，double indexes of temporal attributes and entities address，document redundancy storage to implement local document update efficiently.Experimental results show that the time of update XML document is reduced and the efficiency is improved obviously through Separating entity temporal information and address，adding redundancy space for document.

B＋－tree index；Dynamic update；Temporal XML

TP311.13

A

2095－2562（2016）01－0044－04

（责任编辑：黄容）

2015－11－20；

2016－01－10

2014年度蚌埠学院院级自然科学研究重点项目（2014ZR03zd）；2016年度安徽省自然科学研究重点项目（KJ2016A456）

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