Slide 8.10: Keysorting (cont.)

Keysorting (Cont.)

Algorithm of a Keysort


int  KeySort( FixedRecordFile& inFile, char* outFileName ) {
  RecType obj;
  KeyRRN* KEYNODES = new KeyRRN[ inFile.NumRecs( ) ];
  // read file and load Keys
  for ( int i = 0;  i < inFile.NumRecs( );  i++ ) {
    inFile.ReadByRRN( obj, i );             // read record i
    KEYNODES[i] = KeyRRN( obj.Key( ), i );  // put key and RRN into Keys
  }
  Sort( KEYNODES, inFile.NumRecs( ) );      // sort Keys
  FixedRecordFile  outFile;        // file to hold records in key order
  outFile.Create(outFileName);            // create a new file
  // write new file in key order
  for ( int j = 0;  j < inFile.NumRecs( );  j++ ) {
    inFile.ReadByRRN( obj, KEYNODES[j].RRN );   //  read in key order
    outFile.Append  ( obj );                    // write in key order
  }
  return  1;
}

This algorithm works much the same way that a normal internal sort would work, but with two important differences:

Rather than read an entire record into a memory array, we simply read each record into a temporary buffer, extract the key, then discard it; and
When we are writing the records out in sorted order, we have to read them in a second time, since they are not all stored in memory.

Finally, a problem of keysorting is observed and a solution is proposed:

Problem: Since we have to seek to each record and read it in before writing it back out, creating the sorted file requires as many random seeks into the input file as there are records. Not only read a second time the records, but it is also in reading randomly the file.

Solution: Why bother to write the records in key order: simply write back the sorted index. If we are looking for a particular record, we do our binary search on the index file and then use the RRN stored in the index file record to find the corresponding record in the original file.