Positional access using a b-tree
View Patent ↗A b-tree having information stored therein is utilized to facilitate positional access of elements stored in the leaves of the b-tree. The b-tree is structured such that for each non-leaf level value, a count is located to its immediate left and a value is located to its immediate right. These left and right counts indicate the number of leaf level values located in the leaves of the sub-trees to the immediate left and right of the value. The left and right counts are used to determine the path to take when descending the b-tree in search of a specific position. The counts can also be utilized to determine the total number of values in the leaf level of the b-tree.
1. 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.
2. 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;
traversed left-leaf-count elements;
wherein:
said act of comparing comprises:
determining if said predetermined position value is less than or equal to a first sum of:
a value of a left-leaf-level count element positioned adjacent and left of said encountered valued element; and
a value of a skipcount counter indicative of an accumulated value of all previously traversed right and left-leaf-level count element values, said skipcount counter being initialized to zero prior to a first traversal of a left-leaf-level count element;
if said predetermined position value is less than or equal to said first sum, selecting a sub-tree; and
if said predetermined position is greater than said first sum:
incrementing said skipcount value by a value of a most recently traversed left-leaf-level count element; and
determining if said predetermined position value is less than or equal to a second sum of:
a value of a right-leaf-level count element positioned adjacent and right of said encountered valued element; and
said skipcount value;
if said predetermined position value is less than or equal to said second sum:
incrementing said skipcount value by a value of a most recently traversed right-leaf-level count element;
traversing from left to right to a next encountered valued element; and
repeating said act of comparing starting at said act of determining if said predetermined position value is less than or equal to said second sum.
3. A computer readable medium in accordance with claim 2 , wherein said act of selecting comprises:
selecting a sub-tree indicated by a left-leaf-level count element positioned adjacent and left of said encountered valued element if said predetermined position value is less than or equal to said first sum; and
selecting a sub-tree indicated by a right-leaf-level count element positioned adjacent and right of said encountered valued element if said predetermined position value is greater than said second sum.