XML,又称可扩展标记语言,已经实质上成为了Internet上的数据传输标准。由于使用的越来越广泛,如何对这些数据进行有效的存储、查询,已成为当今学术界研究的一个热门课题。而结构连接方法无疑是XML数据查询的核心操作。为了有效的支持结构查询,目前已经提出了XML数据的各种编码方案。全局区间编码方案能够很好的支持结点结构关系的判断,因而在结构连接中被普遍使用。虽然如此,但采用全局区间编码方案的XML文档的更新效率却很差,需要对整个文档进行重新编码。相对的,采用局部区间编码可以很好的解决文档的更新问题,但它不能直接支持对结点的结构关系的判断,无法被结构连接算法所采用。作为两者的结合,前缀编码既能支持结构连接,又有较好的文档更新效率,是一种有前途的编码方案。为了进一步提高文档更新效率,对经典的前缀编码Dewey编码进行了改进,得出了扩展的Dewey编码Ext-Dewey。采用Ext-Dewey编码的XML文档树在进行更新操作时,完全不需要对树中其它结点进行重新编码,效率很高。更进一步,设计了基于Ext-Dewey编码的结构连接算法,并且在匹配父-子关系的算法中,不使用经典算法中常用的栈来保存中间结果,减少了空间开销。针对区间编码,实现了一种优化算法,其不需要使用任何索引结构,就能在某些情况下避免不必要的连接操作,提高算法效率。最后,将此优化策略用于基于Ext-Dewey编码的连接算法上。实验数据表明,基于Ext-Dewey编码的连接算法是正确的,并且优化后的算法较未优化前性能有普遍的提高。