Author:                         Brian Murphy, Ian Pushee
Date:                           04/07/2001
Version:                        2.0
CS Class:                       CS4432
Programming Language:           C
OS/Hardware dependencies:       Unix


The index file is set up in the following way:

<int: node size><int: attr value><int: attr size><int: root node>
<int: insert #><Index 1>...<Index M>

(No newline separetes these fields)

From now on node size will be referred to as n.

Each <Index ...> contains the following

<bool: node type><int: fill><int: back pointer>
n*<char*: value>(n=1)*<int: pointer>

(No newline separetes these fields)

The information for the header and for each of the nodes is stored in 
structs called index_desc and node, respectively.  Other information
besides that is also stored in each struct.  The index struct also 
includes a pointer to the root node, the offset of the first index, 
and some other useful info for our program.

Originally, we had planned on bulk loading the database, but the task
was slightly overbearing, especially considering all the other 
functions that needed to be created as well.  For this bulk loading
task, a key struct was created that would hold the value and a record 
pointer.  We then would quicksort this struct by the key, and bulk load
it.  Since bulk loading was not used, neither is the qsort, or the key
struct.  They are both unnecessary.   Instead, the CreateIndex
reads a line from the database, and creates the value and pointer 
associated with it.  We begin by filling the root, and splitting from
there.

We assumed it would be easier to traverse the pointers and nodes if we 
created a back pointer, a pointer that pointed to ones parent node.  This
seemed most useful in the splitting of nodes, and the updating of
parent nodes.

InsertRecord and InsertRecordIntoIndex are not linked implicitly.  To update
an index file, one must specifically call InsertRecordIntoIndex.  This is
in accordance with the documentation spec provided by the prof.  It makes
sense that it is set up this way.

The graphical printing of the tree is in the following format (this example
assumes a full tree and a node size of 2):
Left Most Root Value
Left Most 2nd Level Value
Left Most 3rd Level Leaf
Right 3rd Level Leaf

Middle 2nd Level Value
Left 3rd Level Leaf
Right 3rd Level Leaf

Right 2nd Level Value
Left 3rd Level Leaf
Right 3rd Level Leaf

Middle Root Value
...

Where each "Right" value is considered >=.

4 cases are chosen over the same database.  
Case 1: Ranking with nodesize 3
Case 2: Primary key ID with nodesize 4
Case 3: Primary key ID with nodesize 2
Case 4: Ranking with nodesize 4

Not that for case 3 and 4, the amount of values is incremented.  This is due
to inserting the record "01234&Bane&It All Comes Down&1990&14" into the database
after the print indexes of the first two cases.  The trees all print out
symmetrically.

