Supporting database indexes based on a generalized B-tree index

• US 6,219,662 B1
• Filed: 07/09/1998
• Issued: 04/17/2001
• Est. Priority Date: 07/10/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wang, Yun, Li, Ping, Dessloch, Stefan, Fuh, Gene Y. C., Mattos, Nelson Mendonca, Talmoud, Shahrokh, Lee, Daniel Tsunfang
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/112,723
• Time in Patent Office: 1,013 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/8, 707/10, 707/103, 707/104, 707/204, 707/100, 707/102, 707/206
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24553 of query operations
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method, apparatus, and article of manufacture for computer-implemented support of database indexes based on a generalized B-tree index. The index is stored in a B-tree on a data storage device connected to a computer. In particular, multiple key sources are processed using key transformation. Then, a plurality of key targets are generated based on the processed key sources.

Claims

1. A method of generating an index stored in a B-tree, which is stored on a data storage device connected to a computer, the method comprising the steps of:

processing one or more key sources using key transformation; and

generating a plurality of key targets based on the processed key sources.

2. The method of claim 1, wherein at least one of the key sources comprises an attribute.

3. The method of claim 1, wherein at least one of the key sources comprises a compound object.

4. The method of claim 1, wherein the key transformation comprises an expression.

5. The method of claim 4, wherein the expression is a built-in function.

6. The method of claim 4, wherein the expression is a user-defined function.

7. The method of claim 4, wherein the expression is a scalar function.

8. The method of claim 4, wherein the expression is a table function.

9. An apparatus for generating an index, comprising:

a computer having a data storage device connected thereto, wherein the data storage device stores an index stored in a B-tree;

one or more computer programs, performed by the computer, processing one or more key sources using key transformation and generating a plurality of key targets based on the processed key sources.

10. The apparatus of claim 9, wherein at least one of the key sources comprises an attribute.

11. The apparatus of claim 9, wherein at least one of the key sources comprises a compound object.

12. The apparatus of claim 9, wherein the key transformation comprises an expression.

13. The apparatus of claim 12, wherein the expression is a built-in function.

14. The apparatus of claim 12, wherein the expression is a user-defined function.

15. The apparatus of claim 12, wherein expression is a scalar function.

16. The apparatus of claim 12, wherein the expression is a table function.

20. The article of manufacture of claim 15, wherein the key transformation comprises an expression.

21. The article of manufacture of claim 20, wherein the expression is a built-in function.

22. The article of manufacture of claim 20, wherein the expression is a user-defined function.

23. The article of manufacture of claim 20, wherein the expression is a scalar function.

24. The article of manufacture of claim 20, wherein the expression is a table function.

17. An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instructions executable by the computer to perform method steps for generating an index stored in a B-tree, which is stored on a data storage device connected to the computer, the method comprising the steps of:

processing one or more key sources using key transformation; and

generating a plurality of key targets based on the processed key sources.

18. The article of manufacture of claim 17, wherein at least one of the key sources comprises an attribute.

19. The article of manufacture of claim 17, wherein at least one of the key sources comprises a compound object.