btree.c

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

#ifdef DEBUG
    else if (comp > diff)
      findslot = ERROR;		/* inconsistent ordering of keys */
#endif

    else
      findslot = UPPER;		/* key must be above in node ordering */
  }
  return findslot;
}


/*/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*\
|	Insert new data into tree					|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

/*~~~~~~~~~~~~~~~~~~~~~~   private functions   ~~~~~~~~~~~~~~~~~~~~~~~~*/
Nptr getDataNode(Tree *B, keyT key);
Nptr descendSplit(Tree *B, Nptr curr);
void insertEntry(Tree *B, Nptr node, int slot, Nptr sibling, Nptr downPtr);
void placeEntry(Tree *B, Nptr node, int slot, Nptr downPtr);
Nptr split(Tree *B, Nptr node);
void makeNewRoot(Tree *B, Nptr oldRoot, Nptr newNode);

/*~~~~~~~~~~~~~~~~~~~~~   top level insert call   ~~~~~~~~~~~~~~~~~~~~~*/
void insert(Tree *B, keyT key)
{
  Nptr newNode;

#ifdef DEBUG
  fprintf(stderr, "INSERT:  key %d.\n", key);
#endif

  setfunkey(key);			/* set insertion key */
  setfundata("data");			/* a node containing data */
  setsplitpath(NONODE);
  newNode = descendSplit(B, getroot);	/* insertion point search from root */
  if (newNode != getsplitpath)		/* indicates the root node has split */
    makeNewRoot(B, getroot, newNode);
}


/*~~~~~~~~~~~~~~~~   recurse down and split back up   ~~~~~~~~~~~~~~~~~*/
Nptr descendSplit(Tree *B, Nptr curr)
{
  Nptr	newMe, newNode;
  int	slot;

  if (!isfull(curr))
    setsplitpath(NONODE);
  else if (getsplitpath == NONODE)
    setsplitpath(curr);			/* indicates where nodes must split */

  slot = getSlot(B, curr);		/* is null only if the root is empty */
  if (isinternal(curr))			/* continue recursion to leaves */
    newMe = descendSplit(B, getnode(curr, slot));
  else if ((slot > 0) && !comparekeys(getfunkey, getkey(curr, slot))) {
    newMe = NONODE;			/* this code discards duplicates */
    setsplitpath(NONODE); 
  }
  else
    newMe = getDataNode(B, getfunkey);	/* an insertion takes place */

  newNode = NONODE;			/* assume no node splitting necessary */

  if (newMe != NONODE) {		/* insert only where necessary */
    if (getsplitpath != NONODE)
      newNode = split(B, curr);		/* a sibling node is prepared */
    insertEntry(B, curr, slot, newNode, newMe);
  }

  return newNode; 
}

/*/*~~~~~~~~~~~~~~   determine location of inserted key   ~~~~~~~~~~~~~~~*/
void insertEntry(Tree *B, Nptr newNode, int slot, Nptr sibling, Nptr downPtr)
{
  int split, i, j, k, x, y;

  if (sibling == NONODE) {		/* no split occurred */
    placeEntry(B, newNode, slot + 1, downPtr);
    clrflag(newNode, FEWEST);
  }
  else {				/* split entries between the two */
    i = isinternal(newNode);		/* adjustment values */
    split = i ? getfanout - getminfanout(newNode): getminfanout(newNode);
    j = (slot != split);
    k = (slot >= split);

    for (x = split + k + j * i, y = 1; x <= getfanout; x++, y++) {
      xferentry(newNode, x, sibling, y);	/* copy entries to sibling */
      decentries(newNode);
      incentries(sibling);
    }
    if (numentries(sibling) == getfanout)
      setflag(sibling, isFULL);		/* only ever happens in 2-3+trees */

    if (i) {				/* set first pointer of internal node */
      if (j) {
        setfirstnode(sibling, getnode(newNode, split + k));
        decentries(newNode);
      }
      else
        setfirstnode(sibling, downPtr);
    }

    if (j) {				/* insert new entry into correct spot */
      x = getkey(newNode, split + k);
      if (k)
	placeEntry(B, sibling, slot - split + 1 - i, downPtr);
      else
	placeEntry(B, newNode, slot + 1, downPtr);
      setfunkey(x);			/* set key separating nodes */
    }
    else if (!i)
      placeEntry(B, sibling, 1, downPtr);

    clrflag(newNode, isFULL);		/* adjust node flags */
    if (numentries(newNode) == getminfanout(newNode))
      setflag(newNode, FEWEST);		/* never happens in even size nodes */
    if (numentries(sibling) > getminfanout(sibling))
      clrflag(sibling, FEWEST);

#ifdef DEBUG
  fprintf(stderr, "INSERT:  slot %d, node %d.\n", slot, getnodenumber(downPtr));
  showNode(B, newNode);
  showNode(B, sibling);
#endif

  }
}

/*/*~~~~~~~~~~~   place key into appropriate node & slot   ~~~~~~~~~~~~~~*/
void placeEntry(Tree *B, Nptr newNode, int slot, Nptr downPtr)
{
  int x;

  for (x = numentries(newNode); x >= slot; x--)	/* make room for new entry */
    pushentry(newNode, x, 1);
  setentry(newNode, slot, getfunkey, downPtr);	/* place it in correct slot */

  incentries(newNode);				/* adjust entry counter */
  if (numentries(newNode) == getfanout)
    setflag(newNode, isFULL);
}


/*~~~~~~~~~~~~~~~~   split full node and set flags   ~~~~~~~~~~~~~~~~~~*/
Nptr split(Tree *B, Nptr newNode)
{
  Nptr sibling;

  sibling = getFreeNode(B);

  setflag(sibling, FEWEST);			/* set up node flags */

  if (isleaf(newNode)) {
    setflag(sibling, isLEAF);
    setnextnode(sibling, getnextnode(newNode));	/* adjust leaf pointers */
    setnextnode(newNode, sibling);
  }
  if (getsplitpath == newNode)
    setsplitpath(NONODE);			/* no more splitting needed */

  return sibling;
}


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

  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						|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

/*~~~~~~~~~~~~~~~~~~~~~~   private functions   ~~~~~~~~~~~~~~~~~~~~~~~~*/
Nptr descendBalance(Tree *B, Nptr curr, Nptr left, Nptr right, Nptr lAnc, Nptr rAnc, Nptr parent);
void collapseRoot(Tree *B, Nptr oldRoot, Nptr newRoot);
void removeEntry(Tree *B, Nptr curr, int slot);
Nptr merge(Tree *B, Nptr left, Nptr right, Nptr anchor);
Nptr shift(Tree *B, Nptr left, Nptr right, Nptr anchor);

/*~~~~~~~~~~~~~~~~~~~~~   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 delete(Tree *B, keyT key)
{
  Nptr newNode;

#ifdef DEBUG
  fprintf(stderr, "DELETE:  key %d.\n", key);
#endif

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


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

#ifdef DEBUG
  fprintf(stderr, "COLLAPSE:  old %d, new %d.\n", getnodenumber(oldRoot), getnodenumber(newRoot));
  showNode(B, oldRoot);
  showNode(B, newRoot);
#endif

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


/*/*~~~~~~~~~~~~~~~   recurse down and balance back up   ~~~~~~~~~~~~~~~~*/
Nptr descendBalance(Tree *B, 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(B, 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(B, 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 */