近年来,XML在网络应用上日益发展,尤其是电子商务、web服务等—系列应用理念的进一步发展,XML类型的数据便成为了数据表示和交换的主流形式。作为半结构化数据的表示模型XML从提出到现在只不过几年时间,已经显现出其强大而广泛的应用前景。最近几年,在各领域中XML都得到了广泛应用,逐渐被用来作为信息表现和交换的标准,这使得与XML数据相关的领域成为研究热点。由于查询是数据库最为频繁的操作,所以,理所当然的,如何提高XML数据查询的效率成为主要的研究方向之一。目前Native XML数据库的查询求解有以下三种算法：基于XML索引的导航遍历算法；基于XML文档编码的结构链接算法；基于XML文档序列标示的序列匹配算法等。在以上算法中,利用结点编码进行结构连接的算法是主流技术之一。提出XML文档编码就是为了降低查询处理的成本,提高查询求解的效率。对于一个查询(路径表达式),一个较为简单的方法是自顶向下遍历XML文档树中的结点来匹配路径表达式。但是,如果为XML文档树中嵌入有效的编码方案,就能很快检测出XML文档树中的任意两个结点之间的结构关系。本文在深入研究现已提出的编码方案的基础上,结合了前缀编码和区间编码的优点,利用了子树划分的思想,首先,提出了一种基于矩阵划分的XML文档树编码MBL,该编码方案包括三部分,进行编码前,要先对树进行矩阵划分,以便得到矩阵编码,剩余的两部分编码分别是矩阵块内的前缀编码和覆盖子树块得区间编码。该编码基本是定长的,所以,编码长度不会随着结点的插入增长。该方案对某些情况下的插入代价基本为零。本文还基于MBL编码设计了相应的存储策略,针对可能出现的存储溢出问题给出了子树分裂算法；基于MBL编码自身的特点设计了索引机制,该索引结构的记录之间不需要相互保存对方的地址,提高了记录间的独立性,有效降低了更新代价。这样,即使结点的记录地址发生了改变,也不需要对索引进行修改,降低了索引的维护代价。分析了基于此编码的祖先／后裔关系的判断,通过分析得出采用该编码方案,可以在常数时间内给出任意两结点间祖先／后裔关系的判断。并给出了计算结点间相隔层次的公式,改进了包含关系的结构连接算法。最后,本文进行了一系列实验,实验结果表明本文基于矩阵划分的XML文档树编码方案及存储策略和结构连接算法的良好性能。