Computer program product for avoiding complete index tree traversals in sequential and almost sequential index probes

• US 5,845,274 A
• Filed: 06/06/1995
• Issued: 12/01/1998
• Est. Priority Date: 05/10/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lyle, Robert W., Watts, Steven J., Shibamiya, Akira, Chadha, Atul, Haderle, Donald J.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/471,509
• Time in Patent Office: 1,274 Days
• Field of Search: 395/600, 395/601, 395/602, 395/620
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99953 Recoverability

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. 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.