Patent ID: 7493352

Claim:
A method of inserting a new node into a hierarchically-organized data structure, the hierarchically-organized data structure comprising at least a first node at a first level and a plurality of second nodes at a second level, the second nodes being child nodes of the first node, an order being defined among the second nodes, each of the nodes having a data item associated therewith, the first node having a first position identifier which comprises a value selected from a space of ordered discrete values, the second nodes having second position identifiers, each of the second position identifiers comprising the first value and a second value selected from a first subset of the space of ordered discrete values, the first subset consisting of non-adjacent values in the space of ordered discrete values, the second values assigned to each of the second nodes being respective of the order, the method comprising the steps of: receiving the new node and an indication of a position in the hierarchically-organized data structure into which the new node is to be inserted, said position being located between first and second ones of the second nodes with respect to the order; assigning the new node a third position identifier which comprises: said first value; a third value selected from a second subset of the space of ordered discrete values, the second subset consisting of the difference between the space of ordered discrete values and the first subset, said third value being located between the second values associated with said first and second ones of said second nodes with respect to the order; and a fourth value selected from the first subset; and storing in a relational database a row comprising: said third position identifier; and a data item associated with the new node, wherein the relational database comprises: a row corresponding to the first node comprising the first position identifier and data associated with the first node; and for each of the second position identifiers, a row comprising the second position identifier and data associated with the second position identifier.