bpinsert.cpp

经典c++程序的实现

// B+-tree pseudocode: insert
// function binaryle(A, n, K) returns the greatest value less than
//   or equal to K in array A of length n.
// function putinarray(A, pos, k, p) places in array A at position
//    pos the key/pointer pair k and p.
// function splitnode(rt, pos, k, p) places in node rt at recarray
//   position pos the key/pointer pair k and p.  But, in the
//   process, the node is split into two, each taking half of the
//   records, and the new node is returned.
void BP::inserthelp(BPNode* root, Record* rec, KEY& retval,
                    BPNode*& retptr) {
  KEY myretv;     // Least key in new node if current node is split
  BPNode* myretp = NULL; // Pointer to new node if curr node splits

  int currec = binaryle(root->recarray, root->numrec, K);
  if (root->isLeaf()) { // Leaf node -- set up values to insert
    myretv = rec->key;
    myretp = rec;
  }
  else { // internal node
    inserthelp(root->recarray[currec].pointer, rec, myretv, myretp);
    if (myretp == NULL) return; // Child did not split,
  }                             // no need to insert to current node

  // Now, do the insert to the current node.  Split if necessary
  int currec = binaryle(root->recarray, root->numrec, K);
  if (root->recarray[currec].key == myretv) ERROR; // Duplicate
  if (!isFull(root))
    putinarray(root->recarray, currec, myretv, myretp);
  else {
    retptr = splitnode(root, currec, myretv, myretp);
    retval = retptr->recarray[0].key;
  }
}