Loading patent…
AssigneeInternational Business Machines Corporation
InventorsAtul Chadha, Donald J. Haderle, Akira Shibamiya, Robert W. Lyle, Steven J. Watts
Estimating the term…
The present invention provides a system and method for utilizing the proximity of keys in sequential or near sequential index probes to avoid complete index tree traversal. Page information from three pages (LAST, PARENT and NEXT) are stored in separate information fields within an Index Lookaside Buffer. The LAST information field contains information on the most recent leaf page accessed during an index probe in a read key or an insert key operation, the PARENT information field contains information on the parent page of the most recently accessed leaf page described in the LAST information field, and the NEXT information field contains information on the most recent leaf page accessed during a fetch-next key or delete key operation. On a subsequent index probe, the LAST, NEXT and PARENT information fields are sequentially analyzed to determine if the search key is contained within the leaf page described by the LAST or NEXT information fields or if the search key is contained within one of the leaf pages pointed to by the parent page described by the PARENT information field. If none of the LAST, NEXT or PARENT information fields identify the leaf page containing the search key then the default root-to-leaf traversal would commence.
A program storage device readable by a machine tangibly embodying a program of instructions executable by the machine to perform method steps for avoiding a root-to-leaf traversal of an index tree having leaf and parent pages, said method steps comprising:
A program storage device readable by a machine tangibly embodying a program of instructions executable by the machine to perform method steps for avoiding a root-to-leaf traversal of an index tree having leaf and parent pages, said method steps comprising:
A computer program product for use with a computer system, comprising:
A computer program product for use with a computer system, comprising:
Dependencies are inferred from the claim text.
Drawings are temporarily unavailable. Open the PDF at USPTO
From the US filing history. Foreign family members aren’t listed.
Indexing structures: trees, e.g. B+trees
Data processing: database and file management or data structures: database or file accessing
Database or file accessing: access augmentation or optimizing
Database or file accessing: query processing, i.e. searching
Term ended 1 Dec 2015 (estimated)
USPTO file history isn’t available for this patent, so only indexed dates are shown.
1. Technical Field
The present invention relates generally to database management systems and methods for locating an index key value within a multilevel index tree. More specifically, this invention provides a method for avoiding complete index tree traversals in sequential and near sequential probes in a multilevel index tree.
2. Background Art
FIG. 1 is an illustration of a tree structured index;
FIG. 2 is an embodiment of an Index Lookaside Buffer;
FIG. 3 is a flow diagram depicting the sequential processing of information fields within the Index Lookaside Buffer;
The preferred embodiment of the invention is now described with reference to the figures where like reference numbers indicate like elements. Also in the figures, the left most digits of each reference number corresponds to the figure in which the reference number is first used.
1. Environment of the Invention
FIG. 6 illustrates an exemplary computer hardware environment in which the present invention can be implemented. In this exemplary environment, a computer system 602 is comprised of one or more processors connected to one or more electronic storage devices 604, 605, and 606, such as disk drives, on which one or more databases are stored.