动态有序树存储模型与实现方法

XML作为半结构化数据模型的代表,其文档较大,存储动态有序树时需要较多空间成为其明显的缺点,对XML文档进行二进制的编码压缩可以有效地减少存储空间.提出了一种不仅可以对有序树进行空间高效存储,又可以实现有序树的动态化操作的封装包结构.此结构通过将有序树的二进制编码段分段处理的方法,减少了修改量.并通过三重定位的方法快速选定要修改的封装包.针对有序树动态化后出现的节点意义丢失的问题,提出了对树进行辅助描述的高效节点序号表,通过节点序号表可以记录每个节点的内容及意义,进而补充了二进制编码只能表示树结构的缺点.并通过建立有效的序号修改表对其进行快速高效的更新.通过设计对动态树的各种常用操作,并计算出各种操作的空间及时间复杂度,表明了通过此结构可以实现动态有序树的空间高效存储.