Method and apparatus for implementing Q-trees

In a computer system including a data processor and a data storage system containing data records, each record having at least a unique search key and a unique location, wherein the records are indexed by means of a Q-tree structure having at least one leaf node, each leaf node having a plurality of entries assigned to the leaf node, at least some of the entries having at least an associated record location reference, and a distinction-bit which in at least one of the entries is a decision-bit that locates a quit-bit in a search key, a method of operating the data processor for searching selected leaf nodes for indexing information, comprising the steps of:

• (a) defining a search range within a selected leaf node;
• (b) locating a root decision-bit of the selected leaf node;
• (c) reading the decision-bit;
• (d) reading a quit-bit of the search key being sought and testing whether the quit-bit is a first predetermined value;
• (e) defining a next search comprising those entries associated with search keys having values not less than the search key associated with the entry containing the last read root decision-bit if the quit-bit is equal to the first predetermined value;
• and
• (f) defining a next search comprising those entries associated with search keys having values not greater than the search key associated with the entry containing the last read root decision-bit if the quit-bit is not equal to the first predetermined value.

In a computer system including a data processor and a data storage system containing data records, each record having at least a unique search key and a unique location, wherein the records are indexed by means of a bit tree structure having at least one leaf node, each leaf node having a plurality of entries assigned to the leaf node, at least some of the entries having at least a right decision-bit pointer, a left decision-bit pointer, an associated record location reference, and a distinction-bit which in at least some of the entries is decision-bit that locates a quit-bit in a search key, the leaf node further including a prologue having a pointer to a first decision-bit and the location of the first and last distinction-bits of the leaf node, a method of operating the data processor for searching selected leaf nodes for indexing information, comprising the steps of:

• (a) defining a search range having a left extremity and a right extremity within a selected leaf node;
• (b) reading a pointer to the root decision-bit of the selected leaf node;
• (c) reading the decision-bit at the location indicated by the pointer;
• (d) reading a quit-bit of the search key indicated by the last read decision bit and testing whether the quit-bit is set;
• (e) if the quit-bit is set, then reading a right decision-bit pointer from the entry containing the last read decision-bit to determine the location of a next decision-bit, otherwise skipping to step (j);
• (f) comparing the last read right decision-bit pointer with the right extremity of the search range;
• (g) if the last read right decision-bit pointer is less than the right extremity of the current search range, then;
• (1) updating the left extremity with the address of the entry contain ing the last read decision-bit;
• (2) reading the decision-bit located by the last read right decision bit pointer;
• and
• (3) returning to step (d);
• (h) reading the record key associated with the entry located by the right extremity;
• (i) if the record key associated with the entry located by the right extremity is equal to the search key, then indicating that the record key is a match for the search key and ending the search, otherwise, skipping to (m);
• (j) reading the left decision-bit pointer from the entry containing the last read decision-bit to determine the location of the next decision-bit;
• (k) comparing the last read left decision-bit pointer with the left extremity of the search range;
• (l) if the left decision-bit is greater than the left extremity of the current search range, then:
• (1) updating the right extremity with the location of the last read decision-bit;
• (2) reading the decision-bit located by the last read left decision-bit pointer;
• and
• (3) returning to step (d)
• (m) reading the record key associated with the entry located by the left extremity;
• (n) if the record key associated with the entry located by the left extremity is equal to the search key, then indicating that the record key is a match for the search key and ending the search;
• (o) reading the record key associated with the last read decision-bit and comparing the record key with the search key;
• (p) if the search key is greater than the record key, then inserting the record associated with the search key to the right of that record key and ending the search;
• (q) if the search key is less than the record key, then inserting the record associated with the search key to the left of that record key and ending the search;
• and
• (r) if the search key is equal to the record key, then indicating that the record key is a match for the search key and ending the search.

In a computer system comprising a data processor and a data storage system containing data records, each record having at least a unique search key and a unique location, wherein the records are indexed by means of a multi-way tree structure having at least one leaf node, each leaf node having a plurality of entries assigned to the leaf node, at least some of the entries having at least an associated record location reference, and a distinction-bit which in at least one of the entries is a decision-bit that locates a quit-bit in a search key, the leaf node further including a prologue having a left extremity field, a right extremity field, and a quit-index including a pointer associated with at least one decision-bit within the entries to the leaf node, a method of operating the data processor for searching selected leaf nodes for indexing information, comprising the steps of:

• (a) reading values from a left and right extremity field and loading the read values into a left and right extremity variable respectively;
• (b) reading a first entry to the quit-index from the prologue of the selected leaf node;
• (c) locating the first decision-bit using the first entry to the quit-index and reading the first decision-bit;
• (d) reading the quit-bit of a search key associated with a record being sought, the quit-bit of the search key being indicated by the last read decision-bit;
• (e) testing whether the quit-bit is in a first logical state;
• (f) if the quit-bit is in the first logical state, then updating the left extremity variable with the location of the leaf node entry containing the last read decision-bit, otherwise skipping to step (j);
• (g) if the last read entry to the quit-index is not at the end of the quit-index, then reading from the quit-index the next right quit-index entry to determine the location of the next decision-bit, otherwise sequentially searching each leaf node entry starting at the location indicated by the value of one extremity variable and ending at the location indicated by the other extremity variable and ending;
• (h) fetching the next decision-bit;
• (i) repeating step (d);
• (j) if the quit-bit is not in the first logical state, then updating the right extremity variable with the location of the leaf node entry containing the last read decision-bit;
• (k) if the last read entry to the quit-index is not at the end of the quit-index, then reading from the quit-index the next left quit-index entry to determine the location of the next decision-bit, otherwise sequentially searching each leaf node entry starting at the location indicated by the value of one extremity variable and ending at the location indicated by the other extremity variable and ending;
• (l) fetching the next decision-bit;
• (m) repeating step (d).

In a computer system comprising a data processor and a data storage system containing data records, wherein the records are indexed by means of a tree structure having at least one leaf node, each leaf node having a plurality of entries assigned to the leaf node, each entry having a record location reference in the range of "1" to "x" which occupies "a" relative locations within the entry, a distinction-bit having a value greater than "y" which occupies "b" relative locations, and less than three decision-bit pointers, each of which occupy "c" relative locations, the first relative location of each decision-bit pointer having a value not greater than "z", where "z" is not less than "y", a method for locating the relative location of the beginning of an entry to the left of, and adjacent to, an entry that begins at a known relative location "N+8", including the steps of:

• (a) comparing the value stored at relative location N+4 to "z";
• (b) comparing the value stored at relative location N+3 through N+5 to "x", if the value at N+4 is not less than "z", otherwise going to step (e);
• (c) searching sequentially from left to right starting at left extremity of the search range for the relative location of the beginning of each entry until the beginning of the entry to the left of, and adjacent to the entry beginning at relative location "N+8" is found, if the value stored at relative location N+3 through N+5 is not greater than "x", otherwise;
• (d) determining that the relative location of the entry to the left of, and adjacent to, the entry beginning at relative location "N+8" is "N+4";
• (e) comparing the value stored at relative location N+3 through N+5 to "x", if the value at N+4 is less than "z";
• (f) determining that the relative location of the entry to the left of, and adjacent to, the entry beginning at relative location "N+8" is "N", otherwise;
• (g) comparing the value stored at relative location N+2 to "y";
• (h) determining that the relative location of the entry to the left of, and adjacent to, the entry beginning at relative location "N+8" is "N", otherwise;
• (i) comparing the value stored at relative location N+2 to the value stored at relative location N+8;
• (j) determining that the relative location of the entry to the left of, and adjacent to, the entry beginning at relative location "N+8" is "N", otherwise;
• (k) comparing the value stored at relative location N+1 through N+3 to "x";
• (l) determining that the relative location of the entry to the left of, and adjacent to, the entry beginning at relative location "N+8" is "N+2", otherwise performing step (c).