Method and apparatus for implementing Q-trees

Details Method and apparatus for implementing Q-trees Method and apparatus for implementing Q-trees

1993-05-21

1996-03-05

Black, Thomas G.

G06F 1730

Patent

active

054974852

ABSTRACT:
A method and apparatus for increasing the speed of a search through leaf nodes of an inventive key index tree structure, known as a "Q-tree". The present invention identifies "decision-bits" within leaf node entries and uses these decision-bits to accelerate searches for a particular record or for a record adjacent to which a new record is to be inserted. A decision-bit is a particular type of distinction-bit having the smallest value and associated with a search key a greater value then the keys associated with other distinction-bits of the same value within a specified search range. Each decision-bit divides a search range into "left" and "right" parts. One of the two parts will constitute a "new" search range. A "quit-bit" having an ordinal number equal to the value of the decision-bit for the search range, is tested. If the quit-bit is "on", then the right, or greater value, part becomes the new search range. Otherwise, the left, or lesser value, part becomes the new search range. A decision-bit pointer which identifies the relative location of a "root" decision-bit is placed in a predetermined location within the prologue of each leaf node. Additional decision-bit pointers are associated with each subsequent decision-bit within the leaf node and indicate the relative location of such decision-bits with respect to the root decision-bit.

REFERENCES:
patent: 4677550 (1987-06-01), Ferguson
patent: 5121493 (1992-06-01), Ferguson
patent: 5202986 (1993-04-01), Nickel
patent: 5274805 (1993-12-01), Ferguson et al.
A. K. Chandra & D. B. Lomet "Digital B-Trees" IBM Technical Disclosure Bulletin vol. 25, No. 1, pp. 106-109, Jun. 1982.
D. Comer "The Ubiquitous B-Tree" Computing Surveys, vol. 11, No. 2, pp. 121-136, Jun. 1979.
A. Toptsis "B**-Tree: A Data Organization Method for High Storage Utilization" IEEE 1993 Int'l Conf. Computing and Info., pp. 277-281, 1993.
A. Toptsis "B***-Tree: A Family of Efficient Data Packaging Multiway Trees" IEEE 1993 Int'l Conf. Computing and Info., pp. 282-286, 1993.
Ferguson, "Bit-Tree: A Data Structure for Fast File Processing," Communications of the ACM, Jun. 1992, vol. 35, No. 6, pp. 114-120.

Affiliated with

Also associated with

Rating

Method and apparatus for implementing Q-trees does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for implementing Q-trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for implementing Q-trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1418364