Patent ID: 7120637

Claim:
A computer readable medium comprising at least one of volatile and non-volatile storage having computer program code stored thereon for directing a computer processor to locate an element located at a predetermined position of a balanced tree (b-tree), said program code comprising: a traverse b-tree code segment for causing said computer processor to traverse elements in a root node of said b-tree from left to right; a compare code segment for causing said computer processor to, at each encountered element having a value (valued element), compare a value of said predetermined position with a value indicated by a left-leaf-count element and a value indicated by a right-leaf-count element; a select code segment for causing said computer processor to select a sub-tree of said b-tree in accordance with results of said act of comparing; a traverse sub-tree code segment for causing said computer processor to traverse elements in a root node of said selected from left to right; a repeat code segment for causing said computer processor to repeat the acts of comparing, selecting, and traversing elements in a root node of a selected sub-tree, until said leaf level of said b-tree is encountered; and a locate code segment for causing said computer processor to locate said predetermined position of said element in said leaf level of said b-tree in accordance with: said value of said predetermined position; and traversed left-leaf-count elements; a determine code segment for causing said computer processor to determine if said value of said predetermined position is greater than a sum of all left-leaf-level count element values in said root node of said b-tree and all right-leaf-level count element values in said root node of said b-tree; and an indicate code segment for causing said computer processor to indicate that said predetermined position value is out of range if said value-of said predetermined position is greater than said sum.