Tree data structure

1. A method of implementing a tree data structure comprising:

with a processor:

in the data tree structure comprising a number nodes, creating a parent and child relationship between a first node and a second node, in which the first node and second node are at the same hierarchical level of the tree data structure, the first node being a foster parent node and the second node being a foster child node; and

maintaining only one incoming pointer for each of the nodes in the tree data structure at all times;

in which the parent and child relationship created between the first node and the second node does not involve a node in a higher hierarchical level of the tree data structure.

2. The method of claim 1 , in which maintaining only one incoming pointer for each of the nodes in the tree data structure at all times comprises maintaining only one incoming pointer for each of the nodes in the tree data structure before, during, and after making a structural change to the tree data structure.

3. The method of claim 1 , further comprising:

moving, with the processor, a foster key of the foster parent node to a parent node of the foster parent node; and

moving, with the processor, a foster parent/foster child pointer from the foster parent node to the parent node.

4. The method of claim 3 , in which the foster child node is adopted as a child node of the parent node of the foster parent node if a root-to-leaf traversal encounters a foster parent, and if the thread is able to latch both parent node and the foster parent without delay.

5. The method of claim 1 , further comprising assigning, with the processor, a separator key to the first node, in which the separator key is copied from a parent node of the first node.

6. The method of claim 5 , further comprising assigning at least three keys to the foster parent node,

in which the three keys comprise two fence keys that match key values of a parent node of the foster parent node and the separator key,

in which the separator key matches a low fence key of the foster child node.

7. The method of claim 1 , in which the parent and child relationship created between the foster parent node and the foster child node comprises locking only two nodes, in which the two nodes comprise the foster parent node and the foster child node.

8. A tree data structure comprising:

a database that stores a number of records in a number of nodes of the tree data structure; and

a processor that performs a number of functions associated with the records and nodes of the tree data structure;

in which each node in the tree data structure has a single incoming pointer, and

in which the tree data structure comprises a pointer directed to a local overflow node from a node at the same hierarchical level as the local overflow node.

9. The tree data structure of claim 8 , in which each node in the tree data structure comprises a pair of fence keys.

10. The tree data structure of claim 8 , further comprising only said single incoming pointer for each of the nodes in the tree data structure existing before, during, and after making a structural change to the tree data structure.

11. The tree data structure of claim 8 , further comprising a parent/child relationship established between the local overflow node as a foster child node and the node at the same hierarchical level as a foster parent node.

12. The tree data structure of claim 11 , further comprising a foster parent/foster child pointer to point from the foster parent node to the foster child node.

13. The tree data structure of claim 12 , further comprising a foster key of the foster parent node shared with a parent node of the foster parent node;

wherein the foster parent/foster child pointer is shared from the foster parent node to the parent node.

14. The tree data structure of claim 11 , further comprising at least three keys in the foster parent node,

in which the three keys comprise two fence keys that match key values of a parent node of the foster parent node and a separator key,

in which the separator key matches a low fence key of the foster child node.

15. A computer program product for implementing a tree data structure, the computer program product comprising:

a non-transitory computer readable storage medium comprising computer usable program code embodied therewith, the computer usable program code comprising:

computer usable program code to, when executed by a processor maintain one incoming pointer for each node in the tree data structure;

computer usable program code to, when executed by a processor, create a first local overflow node at the same hierarchical level within the tree data structure as a sibling node;

computer usable program code to, when executed by a processor, assign a foster parent/foster child pointer to point from the sibling node to the first local overflow node, the sibling node and first local overflow node forming a foster parent/foster child relationship, the sibling node being a foster parent node and the first local overflow node being a foster child node; and

computer usable program code to, when executed by a processor, copy a foster key within the foster parent node as a separator key within the foster child node.

16. The computer program product of claim 15 , further comprising computer usable program code to, when executed by a processor, transfer a number of records from the foster parent node to the foster child node.

17. The computer program product of claim 16 , further comprising computer usable program code to, when executed by a processor, maintain a pair of fence keys for each node in the tree data structure.

18. The computer program product of claim 15 , further comprising:

computer usable program code to, when executed by a processor, move the foster key from the foster parent node to a parent node of the foster parent node; and

move the foster parent/foster child pointer from the foster parent node to the parent node of the foster parent node.

19. The computer program product of claim 18 , further comprising:

computer usable program code to, when executed by a processor, determines if there is an overflow of records in the parent node; and

computer usable program code to, when executed by a processor, if there is an overflow of records in the parent node, create a second local overflow node at the same hierarchical level within the tree data structure as the parent node;

computer usable program code to, when executed by a processor, assign a foster parent/foster child pointer to point from the parent node to the second local overflow node, the parent node and second local overflow node forming a foster parent/foster child relationship, the parent node being a foster parent node and the second local overflow node being a foster child node; and

computer usable program code to, when executed by a processor, copy a foster key within the foster parent node as a separator key within the foster child node.

20. The computer program product of claim 15 , further comprising:

computer usable program code to, when executed by a processor, determines if a root node has a single child node;

computer usable program code to, when executed by a processor, if the root node does have a single child node, determines if the single child node is a foster parent node of a foster child node; and

computer usable program code to, when executed by a processor, delete the root node if the single child node is not a foster parent node of a foster child node.