Data sorting method

Claim 1

A method for logically sorting data on a storage system using a computer having (1) means for reading data from and writing data to the storage system, and (2) memory means for temporarily storing data in at least one buffer, including the steps of: a. pre-sorting the original data into a plurality of data strings each comprising a plurality of substrings, including the steps of: (1) reading part of the data from the storage system into a pre-sort buffer; (2) sorting the data in the pre-sort buffer; (3) generating substring pointer fields for the sorted data in the pre-sort buffer at intervals corresponding to a determined substring length, with each substring pointer field being set to indicate the location in the storage system of the next logical substring; (4) writing the sorted data in the pre-sort buffer to the storage system as a data string; (5) repeating steps a.(1) through a.(4) for all of the original data on the storage system, thereby generating a plurality of sorted data strings, each comprising a plurality of substrings, stored on the storage system; b. merging the data in place on the storage system into a set of logically linked, sorted substrings, including the steps of: (1) allocating in the memory means at least two input buffers and one output buffer each of a length sufficient to store a substring; (2) establishing a substring storage area tracking means for indicating available storage areas on the storage system from which substrings have been previously read; (3) reading the data from a substring from respective ones of the plurality of data strings into respective ones of the input buffers; (4) merging the data of the substrings in the input buffers into sorted order and storing the sorted data in the output buffer; (5) when the output buffer is full of sorted data, writing the data in the output buffer as a new substring to the storage system in an available storage area, determined from the substring storage area tracking means, and changing the substring pointer field corresponding to the new substring to indicate the location of the next available storage area, determined from the substring storage area tracking means; (6) repeating steps b. (3) through b. (5) for all substrings of the plurality of data strings and all new substrings until all of the data therein is merged, thereby generating a set of substrings linked in sorted logical order by means of the substring pointer fields.

Claim 2

A method for logically sorting data on a storage system using a computer having (1) means for reading data from and writing data to the storage system, and (2) memory means for temporarily storing data in at least one buffer, including the steps of: a. pre-sorting the original data into a plurality of data strings each comprising a plurality of substrings, including the steps of: (1) reading part of the data from the storage system into a pre-sort buffer; (2) sorting the data in the pre-sort buffer; (3) generating substring pointer fields for the sorted data in the pre-sort buffer at intervals corresponding to a determined substring length, with each substring pointer field being set to indicate the location in the storage system of the next logical substring; (4) writing the sorted data in the pre-sort buffer to the storage system as a data string; (5) repeating steps a.(1) through a.(4) for all of the original data on the storage system, thereby generating a plurality of sorted data strings, each comprising a plurality of substrings, stored on the storage system; b. merging the data in place on the storage system into a set of logically linked, sorted substrings, including the steps of: (1) allocating in the memory means at least two input buffers and one output buffer each of a length sufficient to store a substring; (2) establishing a substring storage area tracking means for indicating available storage areas on the storage system from which substrings have been previously read; (3) reading the data from a substring from respective ones of the plurality of data strings into respective ones of the input buffers; (4) merging the data of the substrings in the input buffers into sorted order and storing the sorted data in the output buffer; (5) when the output buffer is full of sorted data, writing the data in the output buffer as a new substring to the storage system in an available storage area, determined from the substring storage area tracking means, and changing the substring pointer field corresponding to the new substring to indicate the location of the next available storage area, determined from the substring storage area tracking means; (6) repeating steps b. (3) through b. (5) for all substrings of the plurality of data strings and all new substrings until all of the data therein is merged, thereby generating a set of substrings linked in sorted logical order by means of the substring pointer fields.

Claim 9

A method for generating a key index multi-node tree structure for data on a storage system using a computer having (1) means for reading data from and writing data to the storage system, and (2) memory means for temporarily storing data in at least one buffer, including the steps of: a. pre-sorting the original data into a plurality of data strings each comprising a plurality of substrings, including the steps of: (1) reading part of the data from the storage system into a pre-sort buffer; (2) sorting the data in the pre-sort buffer; (3) generating substring pointer fields for the sorted data in the pre-sort buffer at intervals corresponding to a determined substring length, with each substring pointer field being set to indicate the location in the storage system of the next logical substring; (4) writing the sorted data in the pre-sort buffer to the storage system as a data string; (5) repeating steps a. (1) through a. (4) for all of the original data on the storage system, thereby generating a plurality of sorted data strings, each comprising a plurality of substrings, stored on the storage system; b. merging the data in place on the storage system into a set of logically linked, sorted substrings, including the steps of: (1) allocating in the memory means at least two input buffers and one output buffer each of a length sufficient to store a substring; (2) establishing a substring storage area tracking means for indicating available storage areas on the storage system from which substrings have been previously read; (3) reading the data from a substring from respective ones of the plurality of data strings into respective ones of the input buffers; (4) merging the data of the substrings in the input buffers into sorted order and storing the sorted data in the output buffer; (5) when the output buffer is full of sorted data, writing the data in the output buffer as a new substring to the storage system in an available storage area, determined from the substring storage area tracking means, and changing the substring pointer field corresponding to the new substring to indicate the location of the next available storage area, determined from the substring storage area tracking means; (6) repeating steps b. (3) through b. (5) for all substrings of the plurality of data strings and all new substrings until all of the data therein is merged, thereby generating a set of substrings linked in sorted logical order by means of the substring pointer fields; c. generating a key index multi-node tree structure for the data in the sorted set of substrings stored on the storage system, including the steps of: (1) establishing at least a first level branch node table for temporarily storing location reference information indicative of the location of selected data in the storage system; (2) reading into a tree index buffer the data from at least one node of data in the storage system, a node initially comprising at least one substring of the set of linked substrings; (3) generating a location reference for a selected portion of the data in the tree index buffer and storing the location reference in the first level of the branch node table; (4) when the first level branch node table is full, writing the contents of the branch node table to the storage system as a generated node of the tree structure; (5) repeating steps c. (2) through c. (4) for all nodes in the storage system containing linked substrings, wherein the nodes are read in sorted order; (6) repeating steps c. (2) through c. (4) for all generated nodes of the tree structure until a single root node for the tree structure is written to the storage system.

Claim 10

A method for generating a key index multi-node tree structure for data on a storage system using a computer having (1) means for reading data from and writing data to the storage system, and (2) memory means for temporarily storing data in at least one buffer, including the steps of: a. pre-sorting the original data into a plurality of data strings each comprising a plurality of substrings, including the steps of: (1) reading part of the data from the storage system into a pre-sort buffer; (2) sorting the data in the pre-sort buffer; (3) generating substring pointer fields for the sorted data in the pre-sort buffer at intervals corresponding to a determined substring length, with each substring pointer field being set to indicate the location in the storage system of the next logical substring; (4) writing the sorted data in the pre-sort buffer to the storage system as a data string; (5) repeating steps a. (1) through a. (4) for all of the original data on the storage system, thereby generating a plurality of sorted data strings, each comprising a plurality of substrings, stored on the storage system; b. merging the data in place on the storage system into a set of logically linked, sorted substrings, including the steps of: (1) allocating in the memory means at least two input buffers and one output buffer each of a length sufficient to store a substring; (2) establishing a substring storage area tracking means for indicating available storage areas on the storage system from which substrings have been previously read; (3) reading the data from a substring from respective ones of the plurality of data strings into respective ones of the input buffers; (4) merging the data of the substrings in the input buffers into sorted order and storing the sorted data in the output buffer; (5) when the output buffer is full of sorted data, writing the data in the output buffer as a new substring to the storage system in an available storage area, determined from the substring storage area tracking means, and changing the substring pointer field corresponding to the new substring to indicate the location of the next available storage area, determined from the substring storage area tracking means; (6) repeating steps b. (3) through b. (5) for all substrings of the plurality of data strings and all new substrings until all of the data therein is merged, thereby generating a set of substrings linked in sorted logical order by means of the substring pointer fields; c. generating a key index multi-node tree structure for the data in the sorted set of substrings stored on the storage system, including the steps of: (1) establishing at least a first level branch node table for temporarily storing location reference information indicative of the location of selected data in the storage system; (2) reading into a tree index buffer the data from at least one node of data in the storage system, a node initially comprising at least one substring of the set of linked substrings; (3) generating a location reference for a selected portion of the data in the tree index buffer and storing the location reference in the first level of the branch node table; (4) when the first level branch node table is full, writing the contents of the branch node table to the storage system as a generated node of the tree structure; (5) repeating steps c. (2) through c. (4) for all nodes in the storage system containing linked substrings, wherein the nodes are read in sorted order; (6) repeating steps c. (2) through c. (4) for all generated nodes of the tree structure until a single root node for the tree structure is written to the storage system.

Claim 18

A method for physically sorting data on a storage system using a computer having (1) means for reading data from and writing data to the storage system, and (2) memory means for temporarily storing data in at least one buffer, including the steps of: a. pre-sorting the original data into a plurality of data strings each comprising a plurality of substrings, including the steps of: (1) reading part of the data from the storage system into a pre-sort buffer; (2) sorting the data in the pre-sort buffer; (3) generating substring pointer fields for the sorted data in the pre-sort buffer at intervals corresponding to a determined substring length, with each substring pointer field being set to indicate the location in the storage system of the next logical substring; (4) writing the sorted data in the pre-sort buffer to the storage system as a data string; (5) repeating steps a. (1) through a. (4) for all of the original data on the storage system, thereby generating a plurality of sorted data strings, each comprising a plurality of substrings, stored on the storage system; b. merging the data in place on the storage system into a set of logically linked, sorted substrings, including the steps of: (1) allocating in the memory means at least two input buffers and one output buffer each of a length sufficient to store a substring; (2) establishing a substring storage area tracking means for indicating available storage areas on the storage system from which substrings have been previously read; (3) reading the data from a substring from respective ones of the plurality of data strings into respective ones of the input buffers; (4) merging the data of the substrings in the input buffers into sorted order and storing the sorted data in the output buffer; (5) when the output buffer is full of sorted data, writing the data in the output buffer as a new substring to the storage system in an available storage area, determined from the substring storage area tracking means, and changing the substring pointer field corresponding to the new substring to indicate the location of the next available storage area, determined from the substring storage area tracking means; (6) repeating steps b. (3) through b. (5) for all substrings of the plurality of data strings and all new substrings until all of the data therein is merged, thereby generating a set of substrings linked in sorted logical order by means of the substring pointer fields; c. physically sorting the set of linked substrings, including the steps of: (1) reading into the memory means a substring of the set of linked substrings; (2) reading into the memory means a next substring in the location indicated by the value of the substring pointer field of the previous substring; (3) writing the previous substring in the location indicated by the value of the substring pointer field of such substring; (4) repeating steps c. (2) and c. (3) for such next substring, and for each subsequent substring of the set of linked substrings, thereby generating a set of substrings in physically sorted order.

Claim 19

A method for physically sorting data on a storage system using a computer having (1) means for reading data from and writing data to the storage system, and (2) memory means for temporarily storing data in at least one buffer, including the steps of: a. pre-sorting the original data into a plurality of data strings each comprising a plurality of substrings, including the steps of: (1) reading part of the data from the storage system into a pre-sort buffer; (2) sorting the data in the pre-sort buffer; (3) generating substring pointer fields for the sorted data in the pre-sort buffer at intervals corresponding to a determined substring length, with each substring pointer field being set to indicate the location in the storage system of the next logical substring; (4) writing the sorted data in the pre-sort buffer to the storage system as a data string; (5) repeating steps a. (1) through a. (4) for all of the original data on the storage system, thereby generating a plurality of sorted data strings, each comprising a plurality of substrings, stored on the storage system; b. merging the data in place on the storage system into a set of logically linked, sorted substrings, including the steps of: (1) allocating in the memory means at least two input buffers and one output buffer each of a length sufficient to store a substring; (2) establishing a substring storage area tracking means for indicating available storage areas on the storage system from which substrings have been previously read; (3) reading the data from a substring from respective ones of the plurality of data strings into respective ones of the input buffers; (4) merging the data of the substrings in the input buffers into sorted order and storing the sorted data in the output buffer; (5) when the output buffer is full of sorted data, writing the data in the output buffer as a new substring to the storage system in an available storage area, determined from the substring storage area tracking means, and changing the substring pointer field corresponding to the new substring to indicate the location of the next available storage area, determined from the substring storage area tracking means; (6) repeating steps b. (3) through b. (5) for all substrings of the plurality of data strings and all new substrings until all of the data therein is merged, thereby generating a set of substrings linked in sorted logical order by means of the substring pointer fields; c. physically sorting the set of linked substrings, including the steps of: (1) reading into the memory means a substring of the set of linked substrings; (2) reading into the memory means a next substring in the location indicated by the value of the substring pointer field of the previous substring; (3) writing the previous substring in the location indicated by the value of the substring pointer field of such substring; (4) repeating steps c. (2) and c. (3) for such next substring, and for each subsequent substring of the set of linked substrings, thereby generating a set of substrings in physically sorted order.