Patent
1995-05-10
1998-05-05
Black, Thomas G.
395602, 395601, 395603, 395611, G06F 1730
Patent
active
057489521
ABSTRACT:
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.
REFERENCES:
patent: 4606002 (1986-08-01), Waisman et al.
patent: 4620295 (1986-10-01), Alken, Jr.
patent: 4774657 (1988-09-01), Anderson et al.
patent: 4860197 (1989-08-01), Langendorf et al.
patent: 4914569 (1990-04-01), Levine et al.
patent: 4980823 (1990-12-01), Liu
patent: 5123104 (1992-06-01), Levine et al.
patent: 5287499 (1994-02-01), Nemes
patent: 5305389 (1994-04-01), Palmer
patent: 5355473 (1994-10-01), Au
patent: 5379422 (1995-01-01), Antoshenkov
patent: 5408652 (1995-04-01), Hayashi et al.
patent: 5408654 (1995-04-01), Barry
patent: 5430870 (1995-07-01), Stanton et al.
patent: 5440732 (1995-08-01), Lomet et al.
patent: 5485609 (1996-01-01), Vitter et al.
patent: 5497485 (1996-03-01), Ferguson et al.
Chadha Atul
Haderle Donald J.
Lyle Robert W.
Shibamiya Akira
Watts Steven J.
Black Thomas G.
Corrielus Jean M.
International Business Machines - Corporation
Johnson, Esq. Prentiss W.
LandOfFree
System and method for avoiding complete index tree traversals in does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for avoiding complete index tree traversals in, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for avoiding complete index tree traversals in will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-69089