Method for reordering the records of a file

Abstract

Abstract THERE IS DESCRIBEDC HEREIN A METHOD FOR THE REORDERING OF A FILE WHEREBY, AFTER SUCH REORDERING, THE RECORDS CONSTITUTING THE FILE ARE ARRANGED SUCH THAT THE ORDER OF THEIR KEY VALUES IS BIASED IN A SEQUENTIAL DIRECTION. THE FILE IS THUS ADVANTAGEOUSLY PRECONDITIONED FOR BEING SORTED, PARTICULARLY BY A DISTRIBUTION SORT TECHNIQUE. THE METHOD FIRST ENTAILS THE PERFORMING OF AN INTERNAL SORT BY REPLACEMENT SELECTION ON THE FILE TO PROVIDE A PLURALITY OF STRINGS OF RECORDS, THE RECORDS CONSTITUTING THE RESPECTIVE STRINGS BEING IN ORDERED SEQUENCES, THE STRINGS BEING CONSECUTIVELY NUMBERED AS THEY ARE CREATED IN THE INTERNAL SORT, VIZ., FIRST TO MTH STRINGS. IF DESIRED, THE RECORDS IN THE STRINGS CAN BE BLOCKED, I.E., EACH BLOCK CONTAINING 1, 2, . . . , K RECORDS AS DESIRED. THE RECORDS ARE THEN WRITTEN ONTO A "DIRECT ACCESS" STORAGE DEVICE SUCH AS A DISK OR A DRUM IN A MANNER WHEREBY THE FIRST BLOCK OF THE FIRST STRING IS PLACED ON THE FIRST SECTOR OF THE FIRST TRACK OF THE STORAGE, THE SECOND BLOCK OF THE FIRST STRING IS PLACED ON THE SECOND SECTOR OF THE FIRST TRACT, ETC., THE FIRST BLOCK OF THE SECOND STRING IS PLACED ON THE SECOND SECTOR OF THE SECOND TRACK, THE FIRST BLOCK OF THE THIRD STRING IS PLACED ON THE THIRD SECTOR OF THE THIRD TRACK, ET SEQ. THUS, IF BIJ REPRESENTS THE JTH BLOCK OF THE ITH STRING, THEN THE BLOCKS ARE WRITTEN ONTO THE STORAGE DEVICE AS FOLLOWS: SECTORS TRACKS 1 2 3 N 1 B11 B12 B13 . . . B1N 2 B21 B22 . . . B2, N-1 3 B31 . . . B3 N-2 . . . . . . M BM1 . . . BM, N-M+1 . . . WITH THE RECORDS SO ARRANGED ON THE DIRECT ACCESS STORAGE DEVICE, THEY ARE READ DIAGONALLY THEREFROM, I.E., THE FIRST BLOCK OF THE FIRST STRING FOLLOWED BY THE FIRST BLOCK OF THE SECOND STRING ET SEQ., THEN THE SECOND BLOCK OF THE FIRST STRING FOLLOWED BY THE SECOND BLOCK OF THE SECOND STRING, ET SEQ., TO PRODUCE A FILE HAVING THE ORDER B11, B21, . . . . BML, B12, B22, . . . BM2, . . . , BM3, . . . , BMN WITH THE PLACING OF THE BLOCKS ON THE "DIRECT ACCESS" STORAGE DEVICE IN THIS MANNER, THE ARRANGEMENT IS EFFECTED WHEREBY THE BEGINNING OF THE NEXT BLOCK TO BE READ/WRITTEN IS ROTATIONALLY ADJACENT TO THE END OF THE LAST BLOCK WHICH WAS READ/WRITTEN WHEREBY LATENCY AND SEEK TIME ARE SIGNIFICANTLY MINIMIZED. THE RECORDERING OF THE FILE PRODUCED FROM THE READING OUT OF THE BLOCKS IN THE DIAGONAL MANNER AS DESCRIBED HEREINABOVE CAN NOW BE ADVANTAGEOUSLY UTILIZED IN A DISTRIBUTION SORT, SUCH AS OF THE TAG OR RECORD TYPES.

Inventors

No inventors recorded.

Bibliographic Details