b++tree.c

这是一个利用B+ Trees数据结构存储数据的源码,全部代码用C语言写的.

/*~~~~~~~~~~~~~~~~~~~~~   build new root node   ~~~~~~~~~~~~~~~~~~~~~~~*/
void
Tree::makeNewRoot(Nptr oldRoot, Nptr newNode)
{
  setroot(getFreeNode());

  setfirstnode(getroot, oldRoot);	/* old root becomes new root's child */
  setentry(getroot, 1, getfunkey, newNode);	/* old root's sibling also */
  incentries(getroot);

  clrflag(oldRoot, isROOT);
  setflag(getroot, isROOT);
  setflag(getroot, FEWEST);
  inctreeheight;
}


/*/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*\
|	Delete data from tree						|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

/*~~~~~~~~~~~~~~~~~~~~~   top level delete call   ~~~~~~~~~~~~~~~~~~~~~*\
|
|	The recursive call for deletion carries 5 additional parameters
|	which may be needed to rebalance the B+tree when removing the key.
|	These parameters are:
|		1. immediate left neighbor of the current node
|		2. immediate right neighbor of the current node
|		3. the anchor of the current node and left neighbor
|		4. the anchor of the current node and right neighbor
|		5. the parent of the current node
|
|	All of these parameters are simple to calculate going along the
|	recursive path to the leaf nodes and the point of key deletion.
|	At that time, the algorithm determines which node manipulations
|	are most efficient, that is, cause the least rearranging of data,
|	and minimize the need for non-local key manipulation.
|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
void
Tree::Delete(keyT key)
{
  Nptr newNode;

#ifdef DEBUG
  cerr << "DELETE:  key " << key << '.' << endl;
#endif

  setfunkey(key);			/* set deletion key */
  setmergepath(NONODE);
  newNode = descendBalance(getroot, NONODE, NONODE, NONODE, NONODE, NONODE);
  if (isnode(newNode))
    collapseRoot(getroot, newNode);	/* remove root when superfluous */
}


/*~~~~~~~~~~~~~~~~~~~~~   remove old root node   ~~~~~~~~~~~~~~~~~~~~~~*/
void
Tree::collapseRoot(Nptr oldRoot, Nptr newRoot)
{

#ifdef DEBUG
  cerr << "COLLAPSE:  old " << getnodeno(oldRoot);
  cerr << ", new " << getnodeno(newRoot) << '.' << endl;
  showNode(oldRoot);
  showNode(newRoot);
#endif

  setroot(newRoot);
  setflag(newRoot, isROOT);
  putFreeNode(oldRoot);
  dectreeheight;			/* the height of the tree decreases */
}


/*/*~~~~~~~~~~~~~~~   recurse down and balance back up   ~~~~~~~~~~~~~~~~*/
Nptr
Tree::descendBalance(Nptr curr, Nptr left, Nptr right, Nptr lAnc, Nptr rAnc, Nptr parent)
{
  Nptr	newMe, myLeft, myRight, lAnchor, rAnchor, newNode;
  int	slot, notleft, notright, fewleft, fewright, test;

  if (!isfew(curr))
    setmergepath(NONODE);
  else if (getmergepath == NONODE)
    setmergepath(curr);		/* mark which nodes may need rebalancing */

  slot = getSlot(curr);
  newNode = getnode(curr, slot);
  if (isinternal(curr)) {	/* set up next recursion call's parameters */
    if (slot == 0) {
      myLeft = isntnode(left) ? NONODE : getlastnode(left);
      lAnchor = lAnc;
    }
    else {
      myLeft = getnode(curr, slot - 1);
      lAnchor = curr;
    }
    if (slot == numentries(curr)) {
      myRight = isntnode(right) ? NONODE : getfirstnode(right);
      rAnchor = rAnc;
    }
    else {
      myRight = getnode(curr, slot + 1);
      rAnchor = curr;
    }
    newMe = descendBalance(newNode, myLeft, myRight, lAnchor, rAnchor, curr);
  }
  else if ((slot > 0) && !comparekeys(getfunkey, getkey(curr, slot)))
    newMe = newNode;		/* a key to be deleted is found */
  else {
    newMe = NONODE;		/* no deletion possible, key not found */
    setmergepath(NONODE);
  }

/*~~~~~~~~~~~~~~~~   rebalancing tree after deletion   ~~~~~~~~~~~~~~~~*\
|
|	The simplest B+tree rebalancing consists of the following rules.
|
|	If a node underflows:
|	CASE 1 check if it is the root, and collapse it if it is,
|	CASE 2 otherwise, check if both of its neighbors are minimum
|	    sized and merge the underflowing node with one of them,
|	CASE 3 otherwise shift surplus entries to the underflowing node.
|
|	The choice of which neighbor to use is optional.  However, the
|	rebalancing rules that follow also ensure whenever possible
|	that the merges and shifts which do occur use a neighbor whose
|	anchor is the parent of the underflowing node.
|
|	Cases 3, 4, 5 below are more an optimization than a requirement,
|	and can be omitted, with a change of the action value in case 6,
|	which actually corresponds to the third case described above.
|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

/*			/* begin deletion, working upwards from leaves */

  if (newMe != NONODE)	/* this node removal doesn't consider duplicates */
    removeEntry(curr, slot + (newMe != newNode));	/* removes one of two */

#ifdef DEBUG
  cerr << "DELETE:  slot " << slot << ", node " << getnodeno(newMe)
								<< '.' << endl;
  showNode(curr);
#endif

  if (getmergepath == NONODE)
    newNode = NONODE;
  else {		/* tree rebalancing rules for node merges and shifts */
    notleft = isntnode(left);
    notright = isntnode(right);
    fewleft = isfew(left);		/* only used when defined */
    fewright = isfew(right);

			/* CASE 1:  prepare root node (curr) for removal */
    if (notleft && notright) {
      test = isleaf(curr);		/* check if B+tree has become empty */
      newNode = test ? NONODE : getfirstnode(curr);
    }
			/* CASE 2:  the merging of two nodes is a must */
    else if ((notleft || fewleft) && (notright || fewright)) {
      test = !(lAnc == parent);
      newNode = test ? merge(curr, right, rAnc) : merge(left, curr, lAnc);
    }
			/* CASE 3: choose the better of a merge or a shift */
    else if (!notleft && fewleft && !notright && !fewright) {
      test = !(rAnc == parent) && (curr == getmergepath);
      newNode = test ? merge(left, curr, lAnc) : shift(curr, right, rAnc);
    }
			/* CASE 4: also choose between a merge or a shift */
    else if (!notleft && !fewleft && !notright && fewright) {
      test = !(lAnc == parent) && (curr == getmergepath);
      newNode = test ? merge(curr, right, rAnc) : shift(left, curr, lAnc);
    }
			/* CASE 5: choose the more effective of two shifts */
    else if (lAnc == rAnc) { 		/* => both anchors are the parent */
      test = (numentries(left) <= numentries(right));
      newNode = test ? shift(curr, right, rAnc) : shift(left, curr, lAnc);
    }
			/* CASE 6: choose the shift with more local effect */
    else {				/* if omitting cases 3,4,5 use below */
      test = (lAnc == parent);		/* test = (!notleft && !fewleft); */
      newNode = test ? shift(left, curr, lAnc) : shift(curr, right, rAnc);
    }
  }

  return newNode;
}


/*/*~~~~~~~~~~~~~~~   remove key and pointer from node   ~~~~~~~~~~~~~~~~*/
void
Tree::removeEntry(Nptr curr, int slot)
{
  int x;

  putFreeNode(getnode(curr, slot));	/* return deleted node to free list */
  for (x = slot; x < numentries(curr); x++)
    pullentry(curr, x, 1);		/* adjust node with removed key */
  decentries(curr);
  clrflag(curr, isFULL);		/* keep flag information up to date */
  if (isroot(curr)) {
    if (numentries(curr) == 1)
      setflag(curr, FEWEST);
  }
  else if (numentries(curr) == getminfanout(curr))
    setflag(curr, FEWEST);
}


/*~~~~~~   merge a node pair & set emptied node up for removal   ~~~~~~*/
Nptr
Tree::merge(Nptr left, Nptr right, Nptr anchor)
{
  int	x, y, z;

#ifdef DEBUG
  cerr << "MERGE:  left " << getnodeno(left);
  cerr << ", right " << getnodeno(right) << '.' << endl;
  showNode(left);
  showNode(right);
#endif

  if (isinternal(left)) {
    incentries(left);			/* copy key separating the nodes */
    setfunkey(getkey(right, 1));	/* defined but maybe just deleted */
    z = getSlot(anchor);		/* needs the just calculated key */
    setfunkey(getkey(anchor, z));	/* set slot to delete in anchor */
    setentry(left, numentries(left), getfunkey, getfirstnode(right));
  }
  else
    setnextnode(left, getnextnode(right));
  for (x = numentries(left) + 1, y = 1; y <= numentries(right); x++, y++) {
    incentries(left);
    xferentry(right, y, left, x);	/* transfer entries to left node */
  }
  if (numentries(left) > getminfanout(left))
    clrflag(left, FEWEST);
  if (numentries(left) == getfanout)
    setflag(left, isFULL);

  if (getmergepath == left || getmergepath == right)
    setmergepath(NONODE);		/* indicate rebalancing is complete */

  return right;
}


/*/*~~~~~   shift entries in a node pair & adjust anchor key value   ~~~~*/
Nptr
Tree::shift(Nptr left, Nptr right, Nptr anchor)
{
  int	i, x, y, z;

#ifdef DEBUG
  cerr << "SHIFT:  left " << getnodeno(left);
  cerr << ", right " << getnodeno(right) << '.' << endl;
  showNode(left);
  showNode(right);
#endif

  i = isinternal(left);
  if (numentries(left) < numentries(right)) {	/* shift entries to left */
    y = (numentries(right) - numentries(left)) >> 1;
    x = numentries(left) + y;
    setfunkey(getkey(right, y + 1 - i));	/* set new anchor key value */
    z = getSlot(anchor);			/* find slot in anchor node */
    if (i) {					/* move out old anchor value */
      decentries(right);			/* adjust for shifting anchor */
      incentries(left);
      setentry(left, numentries(left), getkey(anchor, z), getfirstnode(right));
      setfirstnode(right, getnode(right, y + 1 - i));
    }
    clrflag(right, isFULL);
    setkey(anchor, z, getfunkey);		/* set new anchor value */
    for (z = y, y -= i; y > 0; y--, x--) {
      decentries(right);			/* adjust entry count */
      incentries(left);
      xferentry(right, y, left, x);		/* transfer entries over */
    }

    for (x = 1; x <= numentries(right); x++)	/* adjust reduced node */
      pullentry(right, x, z);
  }
  else {					/* shift entries to right */
    y = (numentries(left) - numentries(right)) >> 1;
    x = numentries(left) - y + 1;

    for (z = numentries(right); z > 0; z--)	/* adjust increased node */
      pushentry(right, z, y);

    setfunkey(getkey(left, x));			/* set new anchor key value */
    z = getSlot(anchor) + 1;
    if (i) {
      decentries(left);
      incentries(right);
      setentry(right, y, getkey(anchor, z), getfirstnode(right));
      setfirstnode(right, getnode(left, x));
    }
    clrflag(left, isFULL);
    setkey(anchor, z, getfunkey);
    for (x = numentries(left) + i, y -= i; y > 0; y--, x--) {
      decentries(left);
      incentries(right);
      xferentry(left, x, right, y);		/* transfer entries over */
    }
  }
  if (numentries(left) == getminfanout(left))	/* adjust node flags */
    setflag(left, FEWEST);
  else
    clrflag(left, FEWEST);			/* never happens in 2-3+trees */
  if (numentries(right) == getminfanout(right))
    setflag(right, FEWEST);
  else
    clrflag(right, FEWEST);			/* never happens in 2-3+trees */
  setmergepath(NONODE);

#ifdef DEBUG
  showNode(left);
  showNode(right);
#endif

  return NONODE;
}


/*/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*\
|	Empty Node Utilities						|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

/*~~~~~~~~~~~~~~~~~~~~   Set up pool of free nodes   ~~~~~~~~~~~~~~~~~~*/
void
Tree::initFreeNodePool(int quantity)
{
  int	i;
  Nptr	n;

  setpoolsize(quantity);
  setnodearray(new Node [quantity]);	/* node memory block */
  setfirstfreenode(nodearrayhead);	/* start a list of free nodes */
  for (n = getfirstfreenode, i = 0; i < quantity; n++, i++) {
    clearflags(n);
    clearentries(n);
    setnextnode(n, n + 1);		/* insert node into free node list */
  }
  setnextnode(--n, NONODE);		/* indicates end of free node list */
}


/*~~~~~~~~~~~~~   take a free B+tree node from the pool   ~~~~~~~~~~~~~*/
Nptr
Tree::getFreeNode()
{
  Nptr newNode = getfirstfreenode;

  if (newNode != NONODE) {
    setfirstfreenode(getnextnode(newNode));	/* adjust free node list */
    setnextnode(newNode, NONODE);		/* remove node from list */
  }
  else {
    cerr << "Out of tree nodes." << endl;	/* can't recover from this */
    exit(0);
  }
  return newNode;
}


/*~~~~~~~~~~~~   return a deleted B+tree node to the pool   ~~~~~~~~~~~*/
void
Tree::putFreeNode(Nptr self)
{
  clearflags(self);
  clearentries(self);
  setnextnode(self, getfirstfreenode);		/* add node to list */
  setfirstfreenode(self);			/* set it to be list head */
}


/*~~~~~~   fill a free data node with a key and associated data   ~~~~~*/
Nptr
Tree::getDataNode(keyT key)			/* can add data parameter */
{
  Nptr	newNode = getFreeNode();
  keyT	*value;

  value = (keyT *) &nAdr(newNode).d;
  *value = key;					/* can add code to fill node */

  return newNode;
}


/*/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*\
|	B+tree Printing Utilities					|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

#ifdef DEBUG
/*~~~~~~~~~~~~~~~~~~~~~~   B+tree node printer   ~~~~~~~~~~~~~~~~~~~~~~*/
void
Tree::showNode(Nptr n)
{
  int x;

  cerr << "-  --  --  --  --  --  --  --  --  --  --  --  -" << endl;
  cerr << "| node " << setw(6) << getnodeno(n) << "                 ";
  cerr << "  magic    " << hex << (getflags(n) & MASK) << "  |" << dec << endl;
  cerr << "-  --  --  --  --  --  --  --  --  --  --  --  -" << endl;
  cerr << "| flags   " << isfew(n) << isfull(n) << isroot(n) << isleaf(n) << ' ';
  cerr << "| keys = " << setw(5) << numentries(n) << ' ';
  cerr << "| node = " << setw(6) << getnodeno(getfirstnode(n)) << "  |" << endl;
  for (x = 1; x <= numentries(n); x++) {
    cerr << "| entry " << setw(6) << x << ' ';
    cerr << "| key = " << setw(6) << (getkey(n, x) & 0xFFFF) << ' ';
    cerr << "| node = " << setw(6) << getnodeno(getnode(n, x)) << "  |" << endl;
  }
  cerr << "-  --  --  --  --  --  --  --  --  --  --  --  -" << endl;
}

/*~~~~~~~~~~~~~~~~~   B+tree class variable printer   ~~~~~~~~~~~~~~~~~*/
void
Tree::showBtree()
{
  cerr << "-  --  --  --  --  --  -" << endl;
  cerr << "|  B+tree  " << setw(10) << (void *) this << "  |" << endl;
  cerr << "-  --  --  --  --  --  -" << endl;
  cerr << "|  root        " << setw(6) << getnodeno(getroot) << "  |" << endl;
  cerr << "|  leaf        " << setw(6) << getnodeno(getleaf) << "  |" << endl;
  cerr << "|  fanout         " << setw(3) << getfanout + 1 << "  |" << endl;
  cerr << "|  minfanout      " << setw(3) << getminfanout(getroot) + 1 << "  |" << endl;
  cerr << "|  height         " << setw(3) << gettreeheight << "  |" << endl;
  cerr << "|  freenode    " << setw(6) << getnodeno(getfirstfreenode) << "  |" << endl;
  cerr << "|  theKey      " << setw(6) << getfunkey << "  |" << endl;
  cerr << "|  theData     " << setw(6) << getfundata << "  |" << endl;
  cerr << "-  --  --  --  --  --  -" << endl;
}
#endif

/*~~~~~~~~~~~~~~~~~~~~~~   B+tree data printer   ~~~~~~~~~~~~~~~~~~~~~~*/
void
Tree::listBtreeValues(Nptr n, int num)
{
  int slot, prev = -1;

  for (slot = 1; (n != NONODE) && num && numentries(n); num--) {
    if (getkey(n, slot) <= prev) cerr << "BOMB";
    prev = getkey(n, slot);
    cerr << setw(8) << prev << (num & 7 ? ' ' : '\n');
    if (++slot > numentries(n))
      n = getnextnode(n), slot = 1;
  }
  cerr << '\n' << endl;
}

/*~~~~~~~~~~~~~~~~~~~   entire B+tree data printer   ~~~~~~~~~~~~~~~~~~*/
void
Tree::listAllBtreeValues()
{
  listBtreeValues(getleaf, ERROR);
}