Patent ID: 7599949

Claim:
A computer-implemented method for inserting an ascending sequence of records into a tree structure having multiple nodes, comprising: a) receiving, with a processor, a record included in the ascending sequence of records; b) locating, with the processor, a node of the multiple nodes that includes an insertion point for the record, wherein the located node includes first, second and third sequentially-ordered records, wherein the first, second and third sequentially-ordered records are adjacent records within the located node, and wherein the insertion point lies between the first and second sequentially-ordered records; c) determining, with the processor, that the located node has insufficient storage space to store the record; d) based on the determination of insufficient storage space, determining whether dividing the located node at the insertion point will lower a load factor with the processor, wherein the load factor is a metric that measures overall usage of storage space within the tree structure; e) dividing, in response to determining that dividing the located node at the insertion point will lower the load factor of the tree structure, the located node into two nodes at a point between the second and third sequentially ordered records with the processor; f) storing, after the division of the located node into the two nodes, the first sequentially-ordered record, the record to be inserted and the second sequentially-ordered record on a first one of the two nodes resulting from the division of the located node with the processor to increase the load factor of the tree structure for ascending sequences of records; and g) storing the third sequentially-ordered record on a second one of the two nodes resulting from the division.