US5748952A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for avoiding complete index tree traversals in sequential and almost sequential index probes
Assignee: International Business Machines Corp
•
Filing: 1995-05-10
•
Granted: 1998-05-05
•
Expires: 2015-05-10
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-10-29 12:06
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: 30
Claim 1
Independent Claim
122 words
A method for avoiding a root-to-leaf traversal of an index tree having leaf and parent pages, the method comprising the steps of: (a) storing page descriptive information in a LAST information field and a PARENT information field in 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
Independent Claim
122 words
A method for avoiding a root-to-leaf traversal of an index tree having leaf and parent pages, the method comprising the steps of: (a) storing page descriptive information in a LAST information field and a PARENT information field in 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
29 words
The method 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
33 words
The method 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
44 words
The method of claim 1, further comprising 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
41 words
The method of claim 4, further comprising 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
Independent Claim
170 words
A method for avoiding a root-to-leaf traversal of an index tree having leaf and parent pages, the method comprising the steps of: (a) storing page information in a LAST information field, a PARENT information field and a NEXT information field in 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
Independent Claim
170 words
A method for avoiding a root-to-leaf traversal of an index tree having leaf and parent pages, the method comprising the steps of: (a) storing page information in a LAST information field, a PARENT information field and a NEXT information field in 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
28 words
The method 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
44 words
The method 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
54 words
The method 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
41 words
The method of claim 6, further comprising 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
46 words
The method of claim 10, further comprising the steps 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
48 words
The method of claim 6, wherein said step of storing further stores 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
282 words
In a database management system utilizing tree structured indexes, a method for avoiding root-to-leaf index tree traversals of an index tree having leaf and parent pages, the method comprising the steps of: (a) storing page descriptive information in an index lookaside buffer (ILB), each said ILB corresponding to one index tree, said ILB comprising: (1) a LAST information field indicating the most recent leaf page accessed during an index probe in a read key or insert key operation, (2) a PARENT information field indicating the parent page of the leaf page described in said LAST information field, and (3) a NEXT information field indicating the most recent leaf page accessed during a fetch-next key or delete key operation, each of said LAST, PARENT, and NEXT information fields further comprising an empty flag, page number, high key, low key and log sequence number (LSN) information fields; (b) determining if a lookaside key is activated after a read key, add key or delete key operation; (c) determining if a search key is located within the leaf page described by said LAST information field; (d) determining if said search key is located within the leaf page described by said NEXT information field; (e) determining if said search key is within one of the leaf pages pointed to by the parent page described in said PARENT information field; (f) updating selected ones of said LAST, NEXT and PARENT information fields of said ILB and storing said updated ILB; and (g) 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 16
Dependent Claim
282 words
In a database management system utilizing tree structured indexes, a method for avoiding root-to-leaf index tree traversals of an index tree having leaf and parent pages, the method comprising the steps of: (a) storing page descriptive information in an index lookaside buffer (ILB), each said ILB corresponding to one index tree, said ILB comprising: (1) a LAST information field indicating the most recent leaf page accessed during an index probe in a read key or insert key operation, (2) a PARENT information field indicating the parent page of the leaf page described in said LAST information field, and (3) a NEXT information field indicating the most recent leaf page accessed during a fetch-next key or delete key operation, each of said LAST, PARENT, and NEXT information fields further comprising an empty flag, page number, high key, low key and log sequence number (LSN) information fields; (b) determining if a lookaside key is activated after a read key, add key or delete key operation; (c) determining if a search key is located within the leaf page described by said LAST information field; (d) determining if said search key is located within the leaf page described by said NEXT information field; (e) determining if said search key is within one of the leaf pages pointed to by the parent page described in said PARENT information field; (f) updating selected ones of said LAST, NEXT and PARENT information fields of said ILB and storing said updated ILB; and (g) 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 17
Dependent Claim
68 words
The method of claim 13, wherein the steps of determining further comprise the steps of: (1) comparing said search key to the values in said low key and high key information fields to determine whether said search key is between said low key and high key values, (2) validating the page to determine if the page type has been changed or if the page contents have been modified.
Claim 18
Dependent Claim
54 words
The method of claim 14, wherein the step of validating the page comprises the steps of: (1) comparing the LSN on the page to the value in the LSN information field, and (2) comparing said search key with the high key and low key values on the page if the LSNs do not match.
Claim 19
Dependent Claim
22 words
The method of claim 13, further comprising the step of reading said empty flag information field to determine if any information exists.
Claim 20
Dependent Claim
56 words
The method of claim 13, further comprising the step of traversing the index tree from the parent page to the leaf page in which said search key is located 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 21
Dependent Claim
18 words
The method of claim 13, wherein said ILB further comprises a token information field uniquely identifying the index.
Claim 22
Independent Claim
120 words
A system for avoiding root-to-leaf traversal of an index tree having leaf and parent pages, the system comprising: means for storing page descriptive information in a LAST information field and a PARENT information field in 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 means for determining if 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 23
Independent Claim
120 words
A system for avoiding root-to-leaf traversal of an index tree having leaf and parent pages, the system comprising: means for storing page descriptive information in a LAST information field and a PARENT information field in 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 means for determining if 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 24
Dependent Claim
40 words
The system of claim 19, further comprising means for performing 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 25
Dependent Claim
30 words
The system of claim 19, further comprising means for performing a root-to-leaf traversal if said LAST and PARENT information fields do not identify the leaf page containing said search key.
Claim 26
Dependent Claim
40 words
The system of claim 21, further comprising means for performing 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 27
Independent Claim
152 words
A system for avoiding root-to-leaf traversal of an index tree having leaf and parent pages, the system comprising: means for storing page descriptive information in a LAST information field, a PARENT information field and a NEXT information field in 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; means for determining if 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 28
Independent Claim
152 words
A system for avoiding root-to-leaf traversal of an index tree having leaf and parent pages, the system comprising: means for storing page descriptive information in a LAST information field, a PARENT information field and a NEXT information field in 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; means for determining if 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 29
Dependent Claim
31 words
The system of claim 23, further comprising means for performing a root-to-leaf traversal if said LAST, NEXT and PARENT information fields do not identify the leaf page containing said search key.
Claim 30
Dependent Claim
48 words
The system of claim 23, wherein said means for storing further stores page information in additional PARENT information fields of said index lookaside buffer, said additional PARENT information fields containing page information of parent pages multiple levels above the most recent leaf page accessed during an index probe.
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-05-04 | 2001-11-03 | 2002-05-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-04 | 2005-11-03 | 2006-05-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-04 | 2009-11-03 | 2010-05-05 | $7700.00 | Window Closed / Lapsed |