Patent ID: 7016904
Filing Date: 2006-03-21
Classification: G06F,Y10S

Abstract:
1. A computer implemented method of inserting data segments into a sorted tree structure, comprising: providing a data structure separate from the sorted tree structure, the data structure having: a head representing a first pointer to a first leaf node of the sorted tree structure; a tail representing a second pointer to a second leaf node of the sorted tree structure; and a body, physically adjacent to the head and to the tail, having a set of pointers pointing to contiguous empty nodes of the sorted tree structure; the providing of the data structure including: examining the first leaf node of the sorted tree structure associated with the head of the data structure; identifying a first leaf node index associated with the head; copying contents of the first leaf node index from the head to the tail of the data structure; determining a direction in which the data structure is traversing the sorted tree structure; updating indices within the sorted tree structure according to an order based upon the direction in which the data structure is traversing the sorted tree structure; deleting contents of the head when inserting a data segment into the sorted tree structure such that empty spaces are evenly distributed among non-empty leaf nodes; redistributing the empty spaces among the non-empty leaf nodes by employing the data structure, wherein the redistributing empty spaces maintains a consistent lookup operation on the sorted tree structure.