桑俊霞，陶宏才

（ 西南交通大学信息科学与技术学院，成都610031）

随着XML文件的广泛使用，对XML的研究越来越多，包括XML编码、XML查询、XML存储等。其中XML编码可以有效地支持XML查询中的结构连接操作，是判断节点间结构关系的重要依据。

目前已有的编码方案主要分为2类：区域编码和前缀编码。

区域编码[1~2]是按照结点的物理位置进行编码，编码结构为，其中start和end分别表示节点的开始位置和结束位置。区域编码是目前使用较多的XML编码方法，但其不能有效地支持文档更新，虽然通过预留编码空间等方法缓解了它对文档更新的缺憾，但仍不够灵活。前缀编码[3~4]把节点路径做为编码依据，保存了编码的路径信息，编码支持文档更新，缺点是编码较长，占用存储空间较大。文献[5]提出了PBiTree编码，并在此基础上提出了基于横向拆分和基于纵向拆分的结构连接算法，该算法采用了二叉树编码方法，但算法复杂，中间转换较多，仍不够完善。文献[6]等提出的高效查询编码方法，采用记录节点路径的方式，支持快速查询操作，但需要较多的辅助信息。

本文提出了一种基于二叉树的BTB（Binary Tree Based，BTB）编码，编码是二进制格式，可以保存节点的路径信息。由于采用的是二进制的编码形式，有效地节省了编码的存储空间，并支持文档更新。

1 编码方法

BTB编码是基于树结构的编码，编码时需要用到完全二叉树结构。

1.1 XML文档树的二叉树化

XML文档是一种半结构化数据，可以以树的形式表示，该树被称为XML文档树。一棵XML文档树如图1，其中节点S是二叉树的根节点，即XML文档树的文档节点，最低层的6个节点是叶子节点。……