Method for sorting and storing data employing dynamic sort tree reconfiguration in volatile memory
AssigneeTandem Computers Incorporated
InventorJames H. Troisi
Life of this patent
Estimating the term…
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.
Claims16
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 volatile 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, each said identifier including a memory pointer and a key value;
- 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 arranged in a hierarchical configuration, said initializing step including:
- associating initialization values with said exterior nodes;
- and
- assigning a loser attribute to each of said interior nodes, said loser attribute associating an exterior node with said interior node and a remaining exterior node being associated with said root node;
- serially introducing said data record identifiers into said exterior nodes of said initialized sort tree, the first of said data record identifiers being introduced into the exterior node associated with said root node and subsequent data record identifiers being associated with consecutive adjacent exterior nodes;
- after the last of the data record identifiers has been introduced to said sort tree, redefining the sort tree so as to eliminate one or more of said exterior or interior nodes not containing a data record identifier;
- sorting said data record identifiers by comparing said key values through said sort tree to said root node, extracting said data record identifiers from said root node and storing the data record identifiers, including the associated memory pointers, in an order in said volatile memory determined by the order they are extracted from the root node;
- and
- reading said data records from said volatile memory in accordance with the sorted memory pointers and storing them in said nonvolatile memory in the order of said sorted key values.
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 volatile 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;
- 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 arranged in a hierarchical configuration, said initializing step including:
- associating first predetermined values with said exterior nodes;
- and
- assigning a loser attribute to each of said interior nodes, said loser attribute associating an exterior node with said interior node and a remaining exterior node being associated with said root node;
- serially introducing said data record identifiers into said exterior nodes of said initialized sort tree, the first of said data record identifiers being introduced into the exterior node associated with said root node and subsequent data record identifiers being associated with consecutive adjacent exterior nodes, wherein said first predetermined values are serially removed from said tree as said data record identifiers are introduced to said tree;
- after the last of the data record identifiers has been introduced to said sorting tree, redefining the tree by eliminating a portion of the nodes not containing data record identifiers, removing all remaining first predetermined values and replacing them with second predetermined values;
- sorting said data record identifiers by comparing said data record identifiers through said sort tree to said root node, extracting said data record identifiers from said root node and storing the data record identifiers in an order in said volatile memory determined by the order they are extracted from the 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.
Dependencies are inferred from the claim text.