Method of compacting and searching a data index

• US 4,677,550 A
• Filed: 09/30/1983
• Issued: 06/30/1987
• Est. Priority Date: 09/30/1983
• Status: Expired due to Fees

• Current Assignee: Amalgamated Software of North America, Inc.
• Original Assignee: Amalgamated Software of North America, Inc.
• Inventors: Ferguson, David E.
• Primary Examiner(s): Williams, Archie E.
• Assistant Examiner(s): Lee, Thomas C.
• Application Number:
  US06/537,701
• Time in Patent Office: 1,369 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/300
• US Class Current: 1/1
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

An improved method for indexing and accessing data stored in a computer storage system, comprising a multi-way tree structure having interconnected branch nodes and leaf nodes. The leaf nodes contain a large number of distinction bits, rather than a smaller number of search keys as known in the prior art. A distinction bit is determined by comparing two selected search keys and determining the ordinal number of the first bit that is different between the two keys. The density of distinction bit entries in the leaf nodes permits shorter access times to obtain data records in a computer storage system.

Claims

1. In a computer system comprising a data processing means, a memory means, and a data storage device containing data records, each data record having a unique search key and a unique record location reference, wherein the data records are indexed by means of a multi-way tree structure initially stored in the data storage device and having at least one leaf node, each such leaf node initially having a plurality of ordered copies of certain of the search keys assigned thereto and containing associated record location references, a method of operating the data processing means for compactly storing indexing information in each leaf node, comprising the steps of:

(1) reading a selected leaf node from the data storage device and saving the leaf node in the memory means;

(2) comparing an initial search key assigned to the leaf node to a next search key assigned to the leaf node;

(3) determining a distinction bit, comprising the ordinal number of the bit position in the initial and the next search keys in which the two keys differ in value;

(4) saving the distinction bit, and the record location reference associated with said next search key, in the leaf node located in the memory means; and

(5) repeating Steps (2), (3), and (4) for a next pair of search keys assigned to the leaf node until a distinction bit is determined and the distinction bit and its associated record location reference are saved for each successive pair of search keys assigned to the leaf node.

2. In a computer system comprising a data processing means, a memory means, and a data storage device containing data records, each data record having a unique search key and a unique record location reference, wherein the data records are indexed by means of a multi-way tree structure initially stored in the data storage means and having (a) a plurality of leaf nodes, each having a unique leaf location reference and each having assigned thereto a plurality of (1) ordered distinction bits, each distinction bit comprising the ordinal number of the bit position in an ordered pair of search keys in which the two keys differ in value, the search keys corresponding to certain of said data records, and (2) record location references, each record location reference being associated with a distinction bit, and (b) at least one branch node, each such branch node having a unique branch location reference, and each branch node containing a plurality of ordered copies of certain of the search keys and associated branch location references to other branch nodes and/or leaf location references to leaf nodes, a method of operating the data processing means for locating a desired data record having a selected search key, comprising the steps of:

(1) selecting the leaf node associated with the selected search key of the desired data record from the data storage device, and saving the selected leaf node in the memory means;

(2) fetching from the selected leaf node an initial distinction bit;

(3) comparing the bit position in the selected search key corresponding to the ordinal value of the fetched distinction bit to a selected value;

(4) if the comparison of Step (3) results in equality, then;

(a) saving the record location reference associated with the fetched distinction bit;

(b) fetching a next distinction bit from the selected leaf node; and

(c) continuing at Step (3) until all distinction bits in the leaf node have been compared;

(5) if the comparison of Step (3) results in inequality, then;

(a) saving the value of the fetched distinction bit;

(b) fetching a next distinction bit from the selected leaf node;

(c) if the fetched distinction bit is greater than the saved distinction bit, then continuing at Step (5) (b);

(d) if the fetched distinction bit is not greater than the saved distinction bit, then fetching a next distinction bit from the selected leaf node and continuing at Step (3);

wherein the last saved record location reference indicates the location in the computer system of the desired data record.

5. The method of operating the data processing means of claim 4 or of claim 2, wherein the step of selecting the leaf node associated with the selected search key of the desired data record comprises the further steps of:

(1) reading the first node in the multi-way tree structure from the data storage device and saving said first node in the memory means;

(2) determining whether the read node is a branch node or a leaf node;

(3) if the read node is a leaf node, then indicating that the read leaf node is the leaf node associated with the selected search key of the desired data record;

(4) if the read node is a branch node, then comparing the selected search key to an ordered pair of search keys contained in the read node;

(a) if the selected search key is greater than or equal to the first of the pair of search keys and less than the second of the pair of search keys, then;

(i) selecting the branch location or leaf location reference associated with the first of the pair of ordered search keys;

(ii) reading a next node in the multi-way tree structure from the data storage means using the selected location reference, and saving said next node in the memory means; and

(iii) continuing at Step (2) for the read next node, until the read next node is a leaf node;

(b) otherwise, continuing at Step (4) with a next pair of ordered search keys.

8. The method of operating the data processing means of claim 4 or of claim 2, further comprising a step for accessing a desired data record having a selected search key, the accessing step further comprising the steps of:

(1) reading the data record in the data storage device at the location indicated by the last saved record location reference;

(2) comparing the selected search key to the search key of the data recrod read;

(3) if the comparison of Step (2) results in inequality, then indicating that the desired data record does not exist in the data storage device;

(4) if the comparison of Step (2) results in equality, then indicating that the data record read is the desired data record.

9. The method of operating the data processing means of claim 8, further comprising a step for indexing a desired data record in the selected leaf node when an indication is made that the desired data record does not exist in the data storage means, the indexing step further comprising the steps of:

(1) storing the desired data record in the data storage device;

(2) determining the distinction bit for the selected search key, comprising the ordinal number of the bit position in the selected search key and the search key of the data record read in which the two keys differ in value;

(3) comparing the selected search key to the search key of the data record read;

(4) if the selected search key is greater than the key of the data record read, then;

(a) locating in the leaf node, on one side of the distinction bit for the data record read, a distinction bit that is less than the distinction bit for the selected search key; and

(b) inserting the distinction bit for the selected search key and the record location reference of the stored data record into the leaf node adjacent to the located distinction bit, and between the lcoated distinction bit and the distinction bit for the data record read;

(5) if the selected search key is not greater than the key of the data record read, then;

(a) locating in the leaf node, on the second side of the distinction bit for the data record read, a distinction bit that is less than the distinction bit for the selected search key; and

(b) inserting the distinction bit for the selected search key and the record location reference of the stored data record into the leaf node adjacent to the located distinction bit, and between the located distinction bit and the distinction bit for the data record read.

10. The method of operating the data processing means of claim 9, further comprising the step of storing the modified leaf node in the data storage device.

3. In a computer system comprising a data processing means, a memory means, and a data storage device containing data records, each data record having a unique search key and a unique record location reference, wherein the data records are indexed by means of a multi-way tree structure initially stored in the data storage device and having (a) a plurality of leaf nodes each initially having a plurality of ordered copies of certain of the search keys assiged thereto and containing associated record location references, each leaf node having a unique leaf location reference, and (b) at least one branch node, each such branch node having a unique branch location reference, and each branch node containing a plurality of ordered copies of certain of the search keys and associated branch location references to other branch nodes and/or leaf location references to leaf nodes, a method of operating the data processing means for compactly storing indexing information in each leaf node for enabling rapid searching of said data records, comprising the steps of:

(1) reading a selected leaf node from the data storage device and saving the leaf node in the memory means;

(2) comparing an initial search key assigned to the leaf node to a next search key assigned to the leaf node;

(3) determining a distinction bit, comprising the ordinal number of the bit position in the initial and the next search keys in which the two keys differ in value;

(4) saving the distinction bit, and the record location reference associated with said next search key, in the leaf node located in the memory means in a position corresponding to the ordering of said next search key assigned to that leaf node; and

(5) repeating Steps (2), (3), and (4) for a next pair of search keys assigned to the leaf node until a distinction bit is determined and the distinction bit and its associated record location reference are saved for each successive pair of search keys assigned to the leaf node.

4. The method of operating the data processing means of claim 3, further comprising a step of locating a desired data record having a selected search key, the locating step further comprising the steps of:

(1) selecting the leaf node associated with the selected search key of the desired data record from the data storage device, and saving the selected leaf node in the memory means;

(2) fetching from the selected leaf node an initial distinction bit;

(3) comparing the bit position in the selected search key corresponding to the ordinal value of the fetched distinction bit to a selected value;

(4) if the comparison of Step (3) results in equality, then;

(a) saving the record location reference associated with the fetched distinction bit;

(b) fetching a next distinction bit from the selected leaf node; and

(c) continuing at Step (3) until all distinction bits in the leaf node have been compared;

(5) if the comparison of Step (3) results in inequality, then;

(a) saving the value of the fetched distinction bit;

(b) fetching a next distinction bit from the selected leaf node;

(c) if the fetched distinction bit is greater than the saved distinction bit, then continuing at Step (5) (b);

(d) if the fetched distinction bit is not greater than the saved distinction bit, then fetching a next distinction bit from the selected leaf node and continuing at Step (3);

wherein the last saved record location reference indicates the location in the computer system of the desired data record.

6. The method of operating the data processing means of claim 5, further comprising a step for splitting a read next node into two new nodes, the splitting step further comprising the steps of:

(1) after reading a node, determining whether the node is full;

(2) if the node is not full, then continuing with Step (2) of claim 5;

(3) if the node is full, then determining whether the node is a leaf node or a branch node;

(a) if the node is a leaf node, then;

(i) locating a distinction bit approximately in the middle of the node;

(ii) reading from the data storage device the data record corresponding to the record location reference associated with the located distinction bit;

(iii) saving the search key of the read data record;

(b) if the node is a branch node, then;

(i) locating a search key approximately in the middle of the node;

(ii) saving the located search key;

(4) storing in the data storage device as a first new node all of the information in the read node located on one side of the position of the located middle distinction bit or search key;

(5) saving the location reference of the first new node;

(6) storing in the data storage device as a second new node all of the information in the read node located on the other side of the position of the located distinction bit or search key; and

(7) storing the saved search key and the saved location reference of the first new node.

7. The method of operating the data processing means of claim 6, wherein the step for storing the saved search key and location reference comprises the further steps of:

(1) determining whether the read node has a prior node;

(2) if the read node does not have a prior node, then;

(a) creating a new prior node in the memory means;

(b) saving the location reference of the read node in the new prior node;

(c) saving the saved location reference in the new prior node;

(d) saving the saved search key between the saved location references; and

(e) storing the new prior node in the data storage device;

(3) if the read node has a prior node, then;

(a) reading the prior node from the data storage device and saving the prior node in the memory means;

(b) comparing the saved search key to an ordered pair of search keys contained in the prior node;

(c) if the saved search key is greater than or equal to the first of a pair of search keys and less than the second of the pair of search keys, then;

(i) inserting the saved search key and the saved location reference between (A) the location reference associated with the first of the pair of search keys and (B) the second of the pair of search keys; and

(ii) storing the read prior node in the data storage device;

(d) otherwise, continuing at Step (3)(b) with a next pair of ordered search keys.