btree.c

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

/***********************************************************************\
|									|
|	B+tree function implementation					|
|									|
|									|
|	Jan Jannink	created 5/27/94		revised 6/16/95		|
|									|
\***********************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include "btree.h"

/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*\
|	Implementation Hiding Macro Definitions				|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
			/* low level definition of Nptr value usage */
#ifdef POINTER
   #define nAdr(b) (b)->X
   #define nodearrayhead B->tree
#else
   #define nAdr(b) B->tree[(b)].X
   #define nodearrayhead 0
#endif

			/* access keys and pointers in a node */
#define getkey(j, q) nAdr(j).e[(q)].key
#define getnode(j, q) nAdr(j).e[(q)].downNode
#define setkey(j, q, v) (nAdr(j).e[(q)].key = (v))
#define setnode(j, q, v) (nAdr(j).e[(q)].downNode = (v))

			/* access node flag values */
#define setflag(j, v) (nAdr(j).i.info.flags |= (v))
#define clrflag(j, v) (nAdr(j).i.info.flags &= ~(v))
#define getflags(j) nAdr(j).i.info.flags
#define clearflags(j) (nAdr(j).i.info.flags = (short) MAGIC)

			/* check that a node is in fact a node */
#define isnode(j) (((j) != NONODE) && ((nAdr(j).i.info.flags & MASK) == MAGIC))
#define isntnode(j) ((j) == NONODE)

			/* test individual flag values */
#define isinternal(j) ((nAdr(j).i.info.flags & isLEAF) == 0)
#define isleaf(j) ((nAdr(j).i.info.flags & isLEAF) == isLEAF)
#define isroot(j) ((nAdr(j).i.info.flags & isROOT) == isROOT)
#define isfull(j) ((nAdr(j).i.info.flags & isFULL) == isFULL)
#define isfew(j) ((nAdr(j).i.info.flags & FEWEST) == FEWEST)
  
			/* manage number of keys in a node */
#define numentries(j) nAdr(j).i.info.pairs
#define clearentries(j) (nAdr(j).i.info.pairs = 0)
#define incentries(j) (nAdr(j).i.info.pairs++)
#define decentries(j) (nAdr(j).i.info.pairs--)

			/* manage first/last node pointers in internal nodes */
#define setfirstnode(j, v) (nAdr(j).i.firstNode = (v))
#define getfirstnode(j) nAdr(j).i.firstNode
#define getlastnode(j) nAdr(j).e[nAdr(j).i.info.pairs].downNode

			/* manage pointers to next nodes in leaf nodes */
#define setnextnode(j, v) (nAdr(j).l.nextNode = (v))
#define getnextnode(j) nAdr(j).l.nextNode

			/* shift/transfer entries for insertion/deletion */
#define pushentry(j, q, v) (nAdr(j).e[(q) + (v)] = nAdr(j).e[(q)])
#define pullentry(j, q, v) (nAdr(j).e[(q)] = nAdr(j).e[(q) + (v)])
#define xferentry(j, q, v, z) (nAdr(v).e[(z)] = nAdr(j).e[(q)])
#define setentry(j, q, v, z) (nAdr(j).e[(q)].key = (v), nAdr(j).e[(q)].downNode = (z))

			/* access key and data values for B+tree methods */
			/* pass values to getSlot(), descend...() */
#define getfunkey B->theKey
#define getfundata B->theData
#define setfunkey(v) (B->theKey = (v))
#define setfundata(v) (B->theData = (v))

			/* define number of B+tree nodes for free node pool */
#define getpoolsize B->poolsize
#define setpoolsize(v) (B->poolsize = (v))

			/* access memory region containing B+tree nodes */
#define getnodearray B->tree
#define setnodearray(v) (B->tree = (Node *)(v))

			/* locations from which tree access begins */
#define getroot B->root
#define setroot(v) (B->root = (v))
#define getleaf B->leaf
#define setleaf(v) (B->leaf = (v))

			/* define max/min number of pointers per node */
#define getfanout B->fanout
#define setfanout(v) (B->fanout = (v) - 1)
#define getminfanout(j) ((nAdr(j).i.info.flags & isLEAF) ? B->fanout - B->minfanout: B->minfanout)
#define setminfanout(v) (B->minfanout = (v) - 1)

			/* manage B+tree height */
#define inittreeheight (B->height = 0)
#define inctreeheight B->height++
#define dectreeheight B->height--
#define gettreeheight B->height

			/* access pool of free nodes */
#define getfirstfreenode B->pool
#define setfirstfreenode(v) (B->pool = (v))

			/* handle split/merge points during insert/delete */
#define getsplitpath B->branch.split
#define setsplitpath(v) (B->branch.split = (v))
#define getmergepath B->branch.merge
#define setmergepath(v) (B->branch.merge = (v))

			/* exploit function to compare two B+tree keys */
#define comparekeys (*B->keycmp)
#define setcomparekeys(v) (B->keycmp = (v))

			/* location containing B+tree class variables */
#define setbplustree(v) (B = (Tree *)(v))

			/* representation independent node numbering */
#define getnodenumber(v) ((v) - nodearrayhead)


/*/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*\
|	Sample Key Comparison Function					|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

int compareKeys(keyT key1, keyT key2)
{
  return key1 - key2;		/* this is the case when keys are integer */
}


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

/*~~~~~~~~~~~~~~~~~~~~~~   private functions   ~~~~~~~~~~~~~~~~~~~~~~~~*/
void initFreeNodePool(Tree *B, int quantity);
Nptr getFreeNode(Tree *B);
void putFreeNode(Tree *B, Nptr self);

/*~~~~~~~~~~~~~~~~~~~   Set up B+tree structure   ~~~~~~~~~~~~~~~~~~~~~*/
Tree *initBtree(unsigned int poolsz, unsigned int fan, KeyCmp keyCmp)
{
  Tree *B;

  setbplustree(malloc(sizeof(Tree)));
  setfanout(fan);
  setminfanout((fan + 1) >> 1);
  initFreeNodePool(B, poolsz);

  setleaf(getFreeNode(B));		/* set up the first leaf node */
  setroot(getleaf);			/* the root is initially the leaf */
  setflag(getroot, isLEAF);
  setflag(getroot, isROOT);
  setflag(getroot, FEWEST);
  inittreeheight;

  setfunkey(0);
  setfundata("0");
  setcomparekeys(keyCmp);

#ifdef DEBUG
  fprintf(stderr, "INIT:  B+tree of fanout %d.\n", fan);
  showBtree(B);
  showNode(B, getroot);
#endif

  return B;
}

/*~~~~~~~~~~~~~~~~~~~   Clean up B+tree structure   ~~~~~~~~~~~~~~~~~~~*/
void freeBtree(Tree *B)
{
#ifdef DEBUG
  fprintf(stderr, "FREE:  B+tree at %10p.\n", (void *) B);
#endif

  free((void *) getnodearray);
  free((void *) B);
}


/*/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*\
|	Find location for data						|
\*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/

/*~~~~~~~~~~~~~~~~~~~~~~   private functions   ~~~~~~~~~~~~~~~~~~~~~~~~*/
Nptr descendToLeaf(Tree *B, Nptr curr);
int getSlot(Tree *B, Nptr curr);
int findKey(Tree *B, Nptr curr, int lo, int hi);
int bestMatch(Tree *B, Nptr curr, int slot);

/*~~~~~~~~~~~~~~~~~~~~~   top level search call   ~~~~~~~~~~~~~~~~~~~~~*/
Nptr search(Tree *B, keyT key)
{
  Nptr	findNode;

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

  setfunkey(key);			/* set search key */
  findNode = descendToLeaf(B, getroot);	/* start search from root node */

#ifdef DEBUG
  fprintf(stderr, "SEARCH:  found on page %d.\n", getnodenumber(findNode));
#endif

  return findNode;
}

/*~~~~~~~~~~~~~~~~~~~~~   `recurse' down B+tree   ~~~~~~~~~~~~~~~~~~~~~*/
Nptr descendToLeaf(Tree *B, Nptr curr)
{
  int	slot;
  Nptr	findNode;

  for (slot = getSlot(B, curr); isinternal(curr); slot = getSlot(B, curr))
    curr = getnode(curr, slot);
  if ((slot > 0) && !comparekeys(getfunkey, getkey(curr, slot)))
    findNode = curr;			/* correct key value found */
  else
    findNode = NONODE;			/* key value not in tree */

  return findNode;
}

/*~~~~~~~~~~~~~~~~~~~   find slot for search key   ~~~~~~~~~~~~~~~~~~~~*/
int getSlot(Tree *B, Nptr curr)
{
  int slot, entries;

  entries = numentries(curr);		/* need this if root is ever empty */
  slot = !entries ? 0 : findKey(B, curr, 1, entries);

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

  return slot;
}


/*/*~~~~~~~~~~~~~~~~~~~   recursive binary search   ~~~~~~~~~~~~~~~~~~~~~*/
int findKey(Tree *B, Nptr curr, int lo, int hi)
{
  int mid, findslot;

#ifdef DEBUG
  fprintf(stderr, "GETSLOT:  lo %d, hi %d.\n", lo, hi);
  showNode(B, curr);
#endif

  if (hi == lo) {
    findslot = bestMatch(B, curr, lo);		/* recursion base case */

#ifdef DEBUG
    if (findslot == ERROR)
      fprintf(stderr, "Bad key ordering on node %d\n", getnodenumber(curr));
#endif

  }
  else {
    mid = (lo + hi) >> 1;
    switch (findslot = bestMatch(B, curr, mid)) {
    case LOWER:				/* check lower half of range */
      findslot = findKey(B, curr, lo, mid - 1);		/* never in 2-3+trees */
    break;
    case UPPER:				/* check upper half of range */
      findslot = findKey(B, curr, mid + 1, hi);
    break;

#ifdef DEBUG
    case ERROR:
      fprintf(stderr, "Bad key ordering on node %d\n", getnodenumber(curr));
#endif

    }
  }
  return findslot;
}


/*/*~~~~~~~~~~~   comparison of key with a target key slot   ~~~~~~~~~~~~*/
int bestMatch(Tree *B, Nptr curr, int slot)
{
  int diff, comp, findslot;

  diff = comparekeys(getfunkey, getkey(curr, slot));    /*in "insert", "getkey" get root's e[1].key*/
  if (diff < 0) {		/* also check previous slot */
    if ((slot == 1) ||
		((comp = comparekeys(getfunkey, getkey(curr, slot - 1))) >= 0))
      findslot = slot - 1;

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

    else
      findslot = LOWER;		/* key must be below in node ordering */
  }
  else {			/* or check following slot */
    if ((slot == numentries(curr)) ||
		((comp = comparekeys(getfunkey, getkey(curr, slot + 1))) < 0))
      findslot = slot;
    else if (comp == 0)
      findslot = slot + 1;