Method for sorting and storing data employing dynamic sort tree reconfiguration in volatile memory

• US 6,385,612 B1
• Filed: 10/11/1996
• Issued: 05/07/2002
• Est. Priority Date: 05/02/1994
• Status: Expired due to Fees

• Current Assignee: Compaq Computer Corporation (HP Inc.)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Troisi, James Henry
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/730,468
• Time in Patent Office: 2,034 Days
• Field of Search: 395/607, 707/7
• US Class Current: 707/752
• CPC Class Codes: G06F 2207/222 Binary data tree
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

In a computer system, data records stored in nonvolatile memory are read into a volatile memory and operated on in a sorting operation. A tournament-type sort is applied, with the tree size dynamically reconfigured within the volatile memory as a function of the number of data records to be sorted. The memory space occupied is reduced by the reconfigured tree and sort speed is augmented.

Claims

1. A method of sorting and storing data in a computer system, the computer system including a Central Processor Unit (CPU), nonvolatile memory accessible by the CPU, and working memory associated with the CPU, the nonvolatile memory including a plurality of data records stored therein, comprising the steps of:

reading said data records from said nonvolatile memory and storing them in said volatile working memory;

assigning a unique data record identifier to each data record in said volatile memory;

creating and initializing a sort tree in said volatile memory, said sort tree including a plurality of nodes allocated to locations in said volatile memory, said nodes including a plurality of exterior nodes, a plurality of interior nodes, and a root node;

initializing said sort tree in combination with entry of said data record identifiers into said sort tree so as to add nodes to the sort tree in accordance with a number of data records added, so that the sort tree is initialized to the extent that it is only large enough to hold the data records entered;

sorting said data record identifiers by comparing said data record identifiers throughout said sort tree to said root node; and

reading said data records from said volatile memory and storing them in said nonvolatile memory in the order of said sorted record identifiers.

2. A method as set out in claim 1, wherein said data record identifiers include a sorting key indicating a characteristic of the record desired to be sorted and a pointer identifying a unique volatile memory location for each record and wherein said step of sorting comprises sorting based on comparing sorting key values.

3. A method as set out in claim 1 wherein said creating and initializing step comprises:

serially initializing exterior nodes and serially introducing said data record identifiers into said external nodes as the data record identifiers are entered, the first of said data record identifiers being introduced into the first created external node and subsequent data record identifiers being associated with consecutive created external nodes;

initializing internal nodes directly above said exterior nodes;

associating initialization values with said internal nodes; and

assigning a node to point to the root node which is redefined as exterior nodes are added.

4. A method as set out in claim 1, wherein said initialized sort tree height is determined by said initializing step.

5. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for causing sorting of data records, the computer program product comprising;

computer readable program code devices configured to cause a computer to effect reading said data records from a nonvolatile memory and store storing them in said volatile working memory;

computer readable program code devices configured to cause a computer to effect assigning a unique data record identifier to each data record in said volatile memory;

computer readable program code devices configured to cause a computer to effect creating a sort tree in said volatile memory, said sort tree including a plurality of nodes allocated to locations in said volatile memory, said nodes including a plurality of exterior nodes, a plurality of interior nodes, and a root node, said nodes being initialized in combination with entry of said data record identifiers into said sort tree so as to add nodes to the sort tree as data records are added;

computer readable program code devices configured to cause a computer to effect sorting said data record identifiers by comparing said data record identifiers through said sort tree to said root node; and

computer readable program code devices configured to cause a computer to effect reading said data records from said volatile memory and storing them in said nonvolatile memory in the order of said sorted record identifiers.

6. A computer program product as set out in claim 5, wherein said code is formed thereon as magnetic flux reversals.

7. A computer program product as set out in claim 5, wherein said code is formed thereon as changes in optical reflectivity of the medium.