US5845274A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Computer program product for avoiding complete index tree traversals in sequential and almost sequential index probes
Assignee: International Business Machines Corp
•
Filing: 1995-06-06
•
Granted: 1998-12-01
•
Expires: 2015-06-06
Abstract
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.
Inventors
- 👤 Atul Chadha
- 👤 Donald J. Haderle
- 👤 Akira Shibamiya
- 👤 Robert W. Lyle
- 👤 Steven J. Watts
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 04:38
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
140 words
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. storing page descriptive information in a LAST information field and a PARENT information field of an index lookaside buffer, said LAST information field identifying the most recent leaf page accessed during an index probe and said PARENT information field identifying a parent node of the most recent leaf page accessed during an index probe; b. determining if a search key is located within the leaf page described by said LAST information field; and c. determining if said search key is located within one of the leaf pages pointed to by the parent page described in said PARENT information field.
Claim 2
Dependent Claim
140 words
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. storing page descriptive information in a LAST information field and a PARENT information field of an index lookaside buffer, said LAST information field identifying the most recent leaf page accessed during an index probe and said PARENT information field identifying a parent node of the most recent leaf page accessed during an index probe; b. determining if a search key is located within the leaf page described by said LAST information field; and c. determining if said search key is located within one of the leaf pages pointed to by the parent page described in said PARENT information field.
Claim 3
Dependent Claim
31 words
The program storage device of claim 1, wherein said LAST and PARENT information fields comprise a page number information field, a high key information field and a low key information field.
Claim 4
Dependent Claim
35 words
The program storage device of claim 2, wherein the steps of determining comprise the step of comparing said search key to the values in said low key information field and said high key information field.
Claim 5
Dependent Claim
53 words
The program storage device of claim 1, further including instructions executable by the machine to perform the step of performing a root-to-leaf traversal of the index tree to find the leaf page containing said search key if said LAST and PARENT information fields do not identify the leaf page containing the search key.
Claim 6
Dependent Claim
50 words
The program storage device of claim 4, further including instructions executable by the machine to perform the step of performing a parent-to-leaf traversal when it is determined that said search key is within one of the leaf pages pointed to by the parent page described by said PARENT information field.
Claim 7
Dependent Claim
188 words
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. storing page information in a LAST information field, a PARENT information field and a NEXT information field of an index lookaside buffer, said LAST information field identifying the most recent leaf page accessed during an index probe in a read-key or an insert-key operation, said PARENT information field identifying the parent page of the leaf page described in said LAST information field and said NEXT information field identifying the most recent leaf page accessed during an index probe in a fetch-next-key or delete-key operation; b. determining if a search key is located within the leaf page described by said LAST information field; c. determining if said search key is located within the leaf page described by said NEXT information field; and d. determining if said search key is located within one of the leaf pages pointed to by the parent page described in said PARENT information field.
Claim 8
Dependent Claim
188 words
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. storing page information in a LAST information field, a PARENT information field and a NEXT information field of an index lookaside buffer, said LAST information field identifying the most recent leaf page accessed during an index probe in a read-key or an insert-key operation, said PARENT information field identifying the parent page of the leaf page described in said LAST information field and said NEXT information field identifying the most recent leaf page accessed during an index probe in a fetch-next-key or delete-key operation; b. determining if a search key is located within the leaf page described by said LAST information field; c. determining if said search key is located within the leaf page described by said NEXT information field; and d. determining if said search key is located within one of the leaf pages pointed to by the parent page described in said PARENT information field.
Claim 9
Dependent Claim
30 words
The program storage device of claim 6, wherein said LAST, NEXT and PARENT information fields comprise a page number, high key, low key and log sequence number (LSN) information fields.
Claim 10
Dependent Claim
46 words
The program storage device of claim 7, wherein the steps of determining comprises the steps of: (1) comparing said search key to the values in said low key and high key information fields, and (2) validating the page to determine if the page has been modified.
Claim 11
Dependent Claim
56 words
The program storage device of claim 8, wherein the step of validating the page comprises the steps of: (1) comparing the LSN on the page to the LSN value in the information field, and (2) comparing the search key with the high key and low key values on the page if the LSNs do not match.
Claim 12
Dependent Claim
50 words
The program storage device of claim 6, further including instructions executable by the machine to perform the step of performing a parent-to-leaf traversal when it is determined that said search key is within one of the leaf pages pointed to by the parent page described by said PARENT information field.
Claim 13
Dependent Claim
55 words
The program storage device of claim 10, further including instructions executable by the machine to perform the step of performing a root-to-leaf traversal of the index tree to find the leaf page containing said search key if said LAST, NEXT or PARENT information fields are unable to locate the leaf page containing said search key.
Claim 14
Dependent Claim
54 words
The program storage device of claim 6, wherein said step of storing further includes the step of storing page information in additional PARENT information fields of said index lookaside buffer, said additional PARENT information fields containing page information of parent nodes multiple levels above the most recent leaf page accessed during an index probe.
Claim 15
Dependent Claim
178 words
A computer program product for use with a computer system, comprising: a computer usable medium having computer readable program code means embodied in said medium for causing the computer system to avoid root-to-leaf traversal of an index tree having leaf and parent pages, said computer readable program code means including, first computer readable program code means for causing said computer system to effect a storage of page descriptive information in a LAST information field and a PARENT information field of an index lookaside buffer, said LAST information field identifying the most recent leaf page accessed during an index probe and said PARENT information field identifying the parent page of the most recent leaf page accessed during an index probe; and second computer readable program code means for causing said computer system to effect a determination of whether a search key is located within one of the leaf pages described by said page descriptive information within said LAST information field or within one of the leaf pages pointed to by the parent page described by said PARENT information field.
Claim 16
Dependent Claim
178 words
A computer program product for use with a computer system, comprising: a computer usable medium having computer readable program code means embodied in said medium for causing the computer system to avoid root-to-leaf traversal of an index tree having leaf and parent pages, said computer readable program code means including, first computer readable program code means for causing said computer system to effect a storage of page descriptive information in a LAST information field and a PARENT information field of an index lookaside buffer, said LAST information field identifying the most recent leaf page accessed during an index probe and said PARENT information field identifying the parent page of the most recent leaf page accessed during an index probe; and second computer readable program code means for causing said computer system to effect a determination of whether a search key is located within one of the leaf pages described by said page descriptive information within said LAST information field or within one of the leaf pages pointed to by the parent page described by said PARENT information field.
Claim 17
Dependent Claim
51 words
The computer program product of claim 13, further comprising computer readable program code means for causing said computer system to effect a parent-to-leaf traversal if it is determined that said search key is within one of the leaf pages pointed to by the parent page described by said PARENT information field.
Claim 18
Dependent Claim
41 words
The computer program product of claim 14, further comprising computer readable program code means for causing said computer system to effect a root-to-leaf traversal if said LAST and PARENT information fields do not identify the leaf page containing said search key.
Claim 19
Dependent Claim
31 words
The computer program product of claim 13, wherein said LAST and PARENT information fields comprise a page number information field, a high key information field and a low key information field.
Claim 20
Dependent Claim
49 words
The computer program product of claim 16, wherein said second computer readable program code means comprises computer readable program code means for causing said computer system to effect a comparison of said search key to the values in said low key information field and said high key information field.
Claim 21
Dependent Claim
205 words
A computer program product for use with a computer system, comprising: a computer usable medium having computer readable program code means embodied in said medium for causing the computer system to avoid root-to-leaf traversal of an index tree having leaf and parent pages, said computer readable program code means including, first computer readable program code means for causing said computer system to store page descriptive information in a LAST information field, a PARENT information field and a NEXT information field of an index lookaside buffer, said LAST information field identifying the most recent leaf page accessed during an index probe in a read-key or an insert-key operation, said PARENT information field identifying the parent page of the leaf page described in said LAST information field and said NEXT information field identifying the most recent leaf page accessed during an index probe in a fetch-next-key or delete-key operation; and second computer readable program code means for causing said computer system to determine whether a search key is located within one of the leaf pages described by said LAST information field and said NEXT information field or is located within one of the leaf pages pointed to by the parent page described in said PARENT information field.
Claim 22
Dependent Claim
205 words
A computer program product for use with a computer system, comprising: a computer usable medium having computer readable program code means embodied in said medium for causing the computer system to avoid root-to-leaf traversal of an index tree having leaf and parent pages, said computer readable program code means including, first computer readable program code means for causing said computer system to store page descriptive information in a LAST information field, a PARENT information field and a NEXT information field of an index lookaside buffer, said LAST information field identifying the most recent leaf page accessed during an index probe in a read-key or an insert-key operation, said PARENT information field identifying the parent page of the leaf page described in said LAST information field and said NEXT information field identifying the most recent leaf page accessed during an index probe in a fetch-next-key or delete-key operation; and second computer readable program code means for causing said computer system to determine whether a search key is located within one of the leaf pages described by said LAST information field and said NEXT information field or is located within one of the leaf pages pointed to by the parent page described in said PARENT information field.
Claim 23
Dependent Claim
51 words
The computer program product of claim 18, further comprising computer readable program code means for causing said computer system to effect a parent-to-leaf traversal if it is determined that said search key is within one of the leaf pages pointed to by the parent page described by said PARENT information field.
Claim 24
Dependent Claim
42 words
The computer program product of claim 19, further comprising computer readable program code means for causing said computer system to effect a root-to-leaf traversal if said LAST, NEXT and PARENT information fields do not identify the leaf page containing said search key.
Claim 25
Dependent Claim
53 words
The computer program product of claim 20, further comprising computer readable program code means for causing said computer system to store further page information in additional PARENT information fields, said additional PARENT information fields containing page information of parent pages multiple levels above the most recent leaf page accessed during an index probe.
Claim 26
Dependent Claim
30 words
The computer program product of claim 18, wherein said LAST, NEXT and PARENT information fields comprise a page number, high key, low key and log sequence number (LSN) information fields.
Claim 27
Dependent Claim
77 words
The computer program product of claim 22, wherein said second computer readable program code means comprises: third computer readable program code means for causing said computer system to effect a comparison of said search key to the values in said low key information field and said high key information field; and fourth computer readable program code means for causing said computer system to effect a validation of the page to determine if the page has been modified.
Claim 28
Dependent Claim
80 words
The computer program product of claim 23, wherein said fourth computer readable program code means comprises: computer readable program code means for causing said computer system to effect a comparison of the LSN on the page to the LSN value in the information field; and computer readable program code means for causing said computer system to effect a comparison of the search key with the high key and low key values on the page if the LSN do not match.
References Cited (Backward Citations)
US4620295A
Cited
US4606002A
Cited
US4774657A
Cited
US4980823A
Cited
US4860197A
Cited
US4914569A
Cited
US5123104A
Cited
US5287499A
Cited
US5408652A
Cited
US5355473A
Cited
US5305389A
Cited
US5379422A
Cited
US5408654A
Cited
US5430870A
Cited
US5440732A
Cited
US5497485A
Cited
US5485609A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-30 | 2002-06-01 | 2002-12-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-30 | 2006-06-01 | 2006-12-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-30 | 2010-06-01 | 2010-12-01 | $7700.00 | Window Closed / Lapsed |