Storage Model and Implementation of the Dynamic Ordered Tree

XML, as the representative of the semi-structured data model, has a large number of documentation. It needs more space in storage of ordered sequential trees. That is one of its obvious shortcomings. One of the methods of reducing the storage space is using binary encoding to compress XML’s documentation. A packet structure is proposed, which can not only store the ordered tree space-efficiently, but also realize its dynamic operation. This structure can reduce the amount of modification by separating the binary coded segments of the ordered tree. It can select the modified package rapidly by the triple positioning. For the missing of nodes’ significance after the dynamic operation of the ordered tree, the efficient node number table is presented, which describes the tree indirectly. And it can record the contents and significance of each node by this structure. It also can make up for the short coming that the binary encoding can only express the tree structure. And by establishing an effective ordinal modification table, the table is updated efficiently. It is proved that this structure can realize the space efficient storage of the ordered tree by designing a variety of common operations of the ordered tree and by calculating the various operations of the space and time complexity.