Increasing efficiency of indexing random-access files composed of fixed-length data blocks by embedding a file index therein

• US 6,535,869 B1
• Filed: 03/23/1999
• Issued: 03/18/2003
• Est. Priority Date: 03/23/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Housel, Barron Cornelius III
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): TRUONG, CAM Y T
• Application Number:
  US09/274,669
• Time in Patent Office: 1,456 Days
• Field of Search: 707/100, 707/8, 707/2, 707/4, 707/1-3, 707/200
• US Class Current: 707/691
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/955 Object-oriented
• 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/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A method, system, and computer-readable code for embedding a file index among the fixed-length data blocks of a random-access file to which the index pertains. In the preferred embodiment, a B-tree index is used. The nodes of the B-tree are stored using blocks of the random-access file, so that the index records are embedded among the data records to which the index pertains. This technique avoids a number of problems that result when a data file and its index are separately located. Record updates and retrievals operate more efficiently, and the data records remain synchronized with the corresponding index when file operations (e.g., close, flush) complete successfully. In an optional enhancement, synchronization is ensured when record-level operations (write, delete) complete successfully.

Claims

1. Computer readable code readable by a computer system in a computing environment for increasing efficiency of indexing random-access files, the computer readable code embodied on computer readable media and comprising:

a subprocess for storing data records in a random-access file, said file comprising a control area and a plurality of fixed-length blocks, wherein each of said data records is stored as one or more of said fixed-length blocks;

a subprocess for creating an embedded index for said file, wherein said index is stored as one or more of said fixed-length blocks which are distinct from fixed-length blocks used to store said data records;

a subprocess for updating said index; and

a subprocess for using said index to retrieve a selected one of said stored data records;

wherein said subprocess for updating is invoked each time said subprocess for storing completes successfully, and wherein said subprocess for updating further comprises;

a subprocess for computing a key value for said data records;

a subprocess for storing said computed key value in a key object;

a subprocess for storing an address where said data record was stored in said key object; and

a subprocess for inserting said key object into said index; and

further comprising a subprocess for deleting said stored data record from said file if said subprocess for inserting encounters an error.

2. Computer readable code for increasing efficiency of indexing random-access files according to claim 1, further comprising:

a subprocess for allocating an index control area for said index within said control area of said random-access file; and

a subprocess for storing an address of said index in said index control area.

3. Computer readable code for increasing efficiency of indexing random-access files according to claim 1, wherein said subprocess for using said index further comprises:

a subprocess for comparing selected ones of said inserted key objects to a record key of said selected record;

a subprocess for returning a not-found indication when none of said selected key objects contains said record key; and

a subprocess for reading said selected record from said random-access file using said stored address in a matching one of said selected key objects when said matching one contains said record key.

4. Computer readable code for increasing efficiency of indexing random-access files according to claim 1, further comprising a subprocess for deleting a particular record from said random-access file, wherein said subprocess for deleting further comprises:

a subprocess for removing an associated key object from said index; and

a subprocess for deallocating one or more blocks associated with said particular record.

5. Computer readable code for increasing efficiency of indexing random-access files according to claim 4, further comprising:

a subprocess for creating a first delete-prepare record to store information related to said subprocess for deallocating;

a subprocess for creating a second delete-prepare record to store information related to said subprocess for removing;

a subprocess for storing said first and second delete-prepare records in a persistent prepare store;

a subprocess for resetting said prepare store when said subprocess for deallocating and said subprocess for removing complete successfully; and

a subprocess for restoring said file when a file error occurs.

6. Computer readable code for increasing efficiency of indexing random-access files according to claim 1, wherein said index is a tree-structured index.

7. Computer readable code for increasing efficiency of indexing random-access files according to claim 6, wherein said tree-structured index is a B-Tree index.

8. Computer readable code for increasing efficiency of indexing random-access files according to claim 1, further comprising:

a subprocess for creating a first write-prepare record to store information related to said subprocess for storing;

a subprocess for creating a second write-prepare record to store information related to said subprocess for updating;

a subprocess for storing said first and second write-prepare records in a persistent prepare store;

a subprocess for resetting said prepare store when said subprocess for storing and said subprocess for updating complete successfully; and

a subprocess for restoring said file when a file error occurs.

9. A system for increasing efficiency of indexing random-access files in a computing environment, comprising:

a random-access file, said file comprising a control area and a plurality of fixed-length blocks;

means for storing data records in said file, wherein each of said data records is stored as one or more of said fixed-length blocks;

means for creating an embedded index for said file, wherein said index is stored as one or more of said fixed-length blocks which are distinct from fixed-length blocks used to store said data records;

means for updating said index; and

means for using said index to retrieve a selected one of said stored data records;

wherein said means for updating is invoked each time said means for storing completes successfully, and wherein said means for updating further comprises;

means for computing a key value for said data record;

means for storing said computed key value in a key object;

means for storing an address where said data record was stored in said key object; and

means for inserting said key object into said index; and

further comprising means for deleting said stored data record from said file if said means for inserting encounters an error.

10. The system for increasing efficiency of indexing random-access files according to claim 9, further comprising:

means for allocating an index control area for said index within said control area of said random-access file; and

means for storing an address of said index in said index control area.

11. The system for increasing efficiency of indexing random-access files according to claim 9, wherein said means for using said index further comprises:

means for comparing selected ones of said inserted key objects to a record key of said selected record;

means for returning a not-found indication when none of said selected key objects contains said record key; and

means for reading said selected record from said random-access file using said stored address in a matching one of said selected key objects when said matching one contains said record key.

12. The system for increasing efficiency of indexing random-access files according to claim 9, further comprising means for deleting a particular record from said random-access file, wherein said means for deleting further comprises:

means for removing an associated key object from said index; and

means for deallocating one or more blocks associated with said particular record.

13. The system for increasing efficiency of indexing random-access files according to claim 12, further comprising:

means for creating a first delete-prepare record to store information related to said means for deallocating;

means for creating a second delete-prepare record to store information related to said means for removing;

means for storing said first and second delete-prepare records in a persistent prepare store;

means for resetting said prepare store when said means for deallocating and said means for removing complete successfully; and

means for restoring said file when a file error occurs.

14. The system for increasing efficiency of indexing random-access files according to claim 9, wherein said index is a tree-structured index.

15. The system for increasing efficiency of indexing random-access files according to claim 14, wherein said tree-structured index is a B-Tree index.

16. The system for increasing efficiency of indexing random-access files according to claim 9, further comprising:

means for creating a first write-prepare record to store information related to said means for storing;

means for creating a second write-prepare record to store information related to said means for updating;

means for storing said first and second write-prepare records in a persistent prepare store;

means for resetting said prepare store when said means for storing and said means for updating complete successfully; and

means for restoring said file when a file error occurs.

17. A method for increasing efficiency of indexing random-access files in a computing environment, comprising the steps of:

storing data records in a random-access file, said file comprising a control area and a plurality of fixed-length block, wherein each of said data records is stored as one or more of said fixed-length blocks;

creating an embedded index for said file, wherein said index is stored as one or more of said fixed-length blocks which are distinct from fixed-length blocks used to store said data records;

updating said index; and

using said index to retrieve a selected one of said stored data records;

wherein said updating step is invoked each time said storing step completes successfully, and wherein said updating step further comprises the steps of;

computing a key value for said data record;

storing said computed key value in a key object;

storing an address where said data record was stored in said key object; and

inserting said key object into said index; and

further comprising the step of deleting said stored data record from said file if said inserting step encounters an error.

18. The method for increasing efficiency of indexing random-access files according to claim 17, further comprising the steps of:

allocating an index control area for said index within said control area of said random-access file; and

storing an address of said index in said index control area.

19. The method for increasing efficiency of indexing random-access files according to claim 17, wherein said using said index step further comprises the steps of:

comparing selected ones of said inserted key objects to a record key of said selected record;

returning a not-found indication when none of said selected key objects contains said record key; and

reading said selected record from said random-access file using said stored address in a matching one of said selected key objects when said matching one contains said record key.

20. The method for increasing efficiency of indexing random-access files according to claim 17, further comprising the step of deleting a particular record from said random-access file, wherein said deleting step further comprises the steps of:

removing an associated key object from said index; and

deallocating one or more blocks associated with said particular record.

21. The method for increasing efficiency of indexing random-access files according to claim 20, further comprising the steps of:

creating a first delete-prepare record to store information related to said deallocating step;

creating a second delete-prepare record to store information related to said removing step;

storing said first and second delete-prepare records in a persistent prepare store;

resetting said prepare store when said deallocating step and said removing step complete successfully; and

restoring said file when a file error occurs.

22. The method for increasing efficiency of indexing random-access files according to claim 17, wherein said index is a tree-structured index.

23. The method for increasing efficiency of indexing random-access files according to claim 22, wherein said tree-structured index is a B-Tree index.

24. The method for increasing efficiency of indexing random-access files according to claim 17, further comprising the steps of:

creating a first write-prepare record to store information related to said storing step;

creating a second write-prepare record to store information related to said updating step;

storing said first and second write-prepare records in a persistent prepare store;

resetting said prepare store when said storing step and said updating step complete successfully; and

restoring said file when a file error occurs.