Patent ID: 7657556
Filing Date: 2010-02-02
Classification: G06F,Y10S

Abstract:
1. A method implemented at least in part on a computing device for searching a balanced tree (b-tree) for a value element located at a predetermined ordinal position, each non-leaf node of said b-tree comprising leaf-level count elements accompanying valued elements, said leaf-level count elements indicative of a number of leaf-level valued elements contained in each sub-tree of said non-leaf node, said method comprising: evaluating valued elements and accompanying leaf-level count elements in a root node of said b-tree from left to right, wherein each valued element in non-leaf level nodes is a first valued element in a leaf level node and wherein, in each non-leaf level node, a cumulative count of count-elements to the left of each valued element indicates a number of valued elements in leaf level nodes to the left of each valued element; selecting a sub-tree of said root node based on said leaf-level count elements and descending to a root node of the selected sub-tree; repeating the acts of evaluating, selecting, and descending until a leaf node of said b-tree is encountered; and locating, in the leaf node, the valued element at said predetermined ordinal position in accordance with: indicating that said predetermined position value is out of range if said number is greater than said sum.