Sort process

Abstract

Abstract A DISTRIBUTION SHORT PROCESS IS PROVIDED WHICH RESULTS IN THE DISTRIBUTION OF THE RECORDS OF A FILE INTO A PLURALITY OF BUCKETS SUCH THAT, THE DISTRIBUTED RECORDS CAN BE RECOVERED IN SEQUENTIAL ORDER OF KEY VALUE IN A ONE SORT PASS. IN THE PROCESS, THE TAGS OF THE RECORDS ARE FIRST SORTED INTO SEQUENTIAL ORDER BY KEY VALUE (A TAG INCLUDING A RECORD''S KEY AND ITS ADDRESS IN THE FILE). THE ADDRESS PORTIONS OF THE TAGS AS THEY ARE ARRANGED IN THE TAG SORT ARE THEN SORTED INTO A SET OF NUMBERED SUBSTRINGS BY A MODIFICATION OF A CONVENTIONAL INTERNAL SORT METHOD SUCH AS REPLACEMENT SELECTION. THE SUBSTRINGS THEN ARE MERGED INTO A FINAL STRING. IN THE MERGE, THE STRING NUMBER IS ADDED TO THE TAG, AND THE KEY AND ADDRESS PORTION MAY BE DELETED TO LEAVE A LIST OF STRING NUMBERS WHICH LIE IN THE SAME ORDER AS THE RECORDS IN THE FILE. A DISTRIBUTION SORT IS THEN PERFORMED ON THE RECORDS BY DISTRIBUTING THEM INTO A QUANTITY OF BUCKETS EQUAL TO THE QUANTITY OF SUBSTRINGS PRODUCED IN THE INTERNAL SORT OF THE ADDRESSES, THE BUCKETS BEING NUMBERED TO CORRESPOND TO THE NUMBERING OF THE SUBSTRINGS. THE DISTRIBUTION SORT IS DESIGNED SUCH THAT THE RECORDS DISTRIBUTED TO A GIVEN BUCKET ARE THOSE WHOSE ADDRESSES ARE IN THE SUBSTRING WHICH HAS THE SAME NUMBER AS THE BUCKET. THE BUCKETS ARE ARRANGED IN SEQUENTIAL ORDER OF NUMERICAL VALVE. AT THE COMPLETION OF THE DISTRIBUTION SORT, A SINGLE SORT PASS OF THE DISTRIBUTED RECORDS PRODUCES A STRING OF RECORDS ARRANGED N SEQUENTIAL ORDER OF KEY VALVE. THE DISTRIBUTION PHASE CAN EITHER BE SINGLEOR MULTI-PASS. THE INVENTION CONTEMPLATES AN ARRANGEMENT WHERE THE BUCKETS CAN BE VISITED CYCLICALLY FOR DISTRIBUTIONS OF RECORDS THEREINTO OR THEY CAN BE SELECTED FOR VISITATION IN ACCORDANCE WITH CHOSED CRITERIA. THE INVENTION ENABLES THE USE OF BUCKETS WHOSE SIZE IS ON AN AVERAGE TWICE AS LARGE AS THE MAIN STORE AND MAKES POSSIBLE ADVANTAGEOUS MINIMIZATION OF SEEK AND LATENCY TIMES.

Inventors

No inventors recorded.

Bibliographic Details