Patent ID: 7505960

Claim:
In a computing system that supports indexing on a dynamically sorted list of recorded data items, a method of efficiently determining an index value for a recorded data item within a data array using a secondary key, while minimizing the number of index value updates needed based on modifications of the plurality of recorded data items, by using a combination of a lookup table and binary tree, the method comprising: receiving a request to access a data element within a data array that sorts a list of data elements using indices, wherein each data element within the list includes at least one field that is considered a secondary key in that the list of data elements within the data array are arranged in random order relative to their corresponding secondary key field; receiving a secondary key corresponding to the data element; using a lookup table data structure to determine a node placement within a binary tree data structure corresponding to the secondary key, wherein each node of the binary tree data structure comprises a node count value indicative of itself added to its number of descendant nodes; and based on the node placement within the binary tree, dynamically calculating an index value for the data element used in accessing at least a portion thereof, wherein the index value is an offset into the data array relative to the other indices, and wherein dynamically calculating the index value comprises: (1) taking the node count value of the particular node at the placement found in the lookup table data structure: (2) subtracting out any descendents to nodes right of the particular node in the binary tree data structure; (3) subtracting out one count for the particular node itself; and (4) adding any ancestors to a true left of the particular node.