×

Method and apparatus for loading data into a cube forest data structure

  • US 6,334,125 B1
  • Filed: 11/17/1998
  • Issued: 12/25/2001
  • Est. Priority Date: 11/17/1998
  • Status: Expired due to Fees
First Claim
Patent Images

1. A device for updating a cube forest F, which is a collection of indices I1, . . . , In having a plurality of templates T1, . . . , Tn, each of which template is a tree having a plurality of spines with a plurality of nodes, and the plurality of nodes of the tree represent aggregate values to be updated with a single tuple, comprising:

  • a) means for forming a catenated key for an index, as determined by a sequence of template nodes on a spine of the index;

    b) means for descending the index using a B-tree search algorithm and for searching for the catenated key, including;

    (i) means for searching, at every node that the descent touches, for an effective leaf that is tagged by a subkey of the catenated key;

    (ii) means for updating, if such an effective leaf is found, any aggregates at the effective leaf;

    (iii) means for updating recursively any subindices at the effective leaf; and

    (iv) means for marking the subkey as processed;

    c) means for inserting, after the descent, if there is an unprocessed subkey, the catenated key into the index;

    d) means for creating a plurality of effective leaves for all unprocessed subkeys and inserting them into the node;

    e) means for restructuring, if the node becomes too full after inserting, the index using a B-tree restructuring algorithms; and

    f) means for moving, after each restructuring step, effective leaves as necessary to ensure that the effective leaf location invariant is preserved.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×