Key-accessed file organization

• US 4,611,272 A
• Filed: 02/03/1983
• Issued: 09/09/1986
• Est. Priority Date: 02/03/1983
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lomet, David B.
• Primary Examiner(s): Thomas, James D.
• Assistant Examiner(s): Munteanu, Florin
• Application Number:
  US06/463,469
• Time in Patent Office: 1,314 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/300, 360/49
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A key-accessed (indexed) file is organized such that the file structure consists only of two levels, an index level and a data level. Both levels are permanently stored on a page-organized secondary storage medium that supports random accessing of the pages. The index level is designed to have a fixed and specifiable number of pages and is stored entirely in the computer'"'"'s memory when the file is in use. The fixed size of the index is made possible by having each index entry reference a data node with a growing (or shrinking) number of data pages as the file changes in size. Avoiding the accessing of more than one of the data pages referenced by an index entry is accomplished by means of an address computation that utilizes bits of the search argument.

Claims

1. A method for establishing and maintaining a key-accessed file management organization and procedure in a computer system which includes a primary and secondary memory, said method comprising:

providing a data level including a set of blocks of pages stored in the secondary memory;

providing an index level stored in the primary memory when the file is in use;

said index level including a set of index entries, each of which includes a starting address indicating the location on the secondary memory where a block of contiguous pages begins; and

a size field indicating the number of pages in said block of pages having said starting address;

said method further comprising maintaining the file by;

changing the number of pages in said blocks as the size of the file changes,

specifying said size in the size field as the logarithm, base two, of the number of pages referenced by said index entry, and

changing the size field in any index entry in which the number of pages in the referenced block is changed.

2. A method for establishing and maintaining a key-accessed file management organization and procedure in a computer system which includes a primary and secondary memory, said method comprising:

providing a data level including a set of blocks of pages stored in the secondary memory;

providing an index level stored in the primary memory when the file is in use;

said index level including a set of index entries, each of which includes a starting address indicating the location on the secondary memory where a block of contiguous pages begins; and

a size field indicating the number of pages in said block of pages having said starting address;

said method further comprising maintaining the file by;

changing the number of pages in said blocks as the size of the file changes, and concurrently changing the number in the size field in the index level entry for each respective block to reflect the change in the number of pages.

said entries in the index level being initially organized by the method of;

generating a unique key which is a function of a file record to be accessed in memory, said keys comprising at least a portion of an address in said index level;

distributing the keys uniformly over their address space by a first function h(key); and

redistributing the keys exponentially over the same address space by second function.

3. A method for establishing and maintaining a key-accessed file management organization as in claim 2 wherein said generating step includes:

choosing the first function, h(key), from a class of universal hashing functions; and

choosing the second function to be 2^h(key) -1.

4. A method for establishing and maintaining a key-accessed file management organization and procedure in a computer system which includes a primary and secondary memory, said method comprising:

providing a data level including a set of original blocks of pages stored in the secondary memory;

providing an index level stored in the primary memory when the file is in use;

said index level including a set of index entries, each of which includes a starting address indicating the location on the secondary memory where a block of contiguous pages begins; and

a size field indicating the number of pages in said block of pages having said starting address;

said method further comprising maintaining the file by;

changing the number of pages in said blocks as the size of the file changes, and concurrently changing the number in the size field in the index level entry for each respective block to reflect the change in the number of pages, including increasing the amount of data storage space available on said secondary memory comprising the step of;

allocating a second block of pages in said data level referenced by an index entry to effectively double the size of an original block of pages.

5. A method as in claim 4 further comprising the steps of:

changing the value of the size field indicating the size of said block associated with said index entry to a value which is a function of the number of pages in said second block; and

changing the starting address associated with said index entry to refer to the location in said secondary memory containing the first page in said second block of pages.

6. A method as in claim 4, including the step of decreasing the amount of data storage space available on said secondary memory comprising:

de-allocating pages of an original block of pages to form a second block of pages in said data level referenced by said index entry to effectively reduce the size of said original block of pages by one half.

7. A method as in claim 6 further comprising the steps of:

changing the value of the size field indicating the size of said block associated with said index entry to a value which is a function of the number of pages in said second block; and

changing the starting address associated with said index entry to refer to the location in said secondary memory containing a first page in said second block of pages.

8. A three phase method for establishing, maintaining and searching a key-accessed file management organization in a computer system which includes a primary and secondary memory, said establishing phase comprising:

providing a data level including a set of blocks of pages stored in the secondary memory;

providing an index level stored in the primary memory when the file is in use;

said level including a set of index entries, each of which includes a starting address indicating the location on the secondary memory where a block of contiguous pages begin; and

a size field indicating the number of pages in said block of pages having said starting address;

said maintaining phase comprising;

changing the number of pages in said blocks as the size of the file changes;

said searching phase for searching said file comprising the steps of;

finding the index entry associated with a selected key by utilizing said key as an address argument in said index level memory; and

computing, based on an address and a size associated with said index entry, the address of the page, among the block of pages addressed, in which data associated with said key is found;

wherein each block of pages has 2^m pages, where m is an integer which may be different for different blocks, and wherein said step of computing comprises the steps of;

selecting n predetermined bits of said key, where n is the logarithm, base two, of the number of pages in the block referenced by said entry; and

9. adding said n bits to the address associated with said index entry, thereby generating the address of the page in which data associated with the key is found.

11. A method as in claim 9 wherein:

each said overflow page is associated with a contiguous sub-block of pages, with each page of the block being in a unique sub-block.

12. A method as in claim 9 for accessing more data than can be contained in said at least one overflow page comprising the steps of:

(a) associating said overflow page with a contiguous sub-block of pages;

(b) associating another overflow page with a second contiguous sub-block of pages;

(c) with each page being in a unique sub-block;

(d) inserting into said overflow page the address of said other overflow page as part of an index entry which identifies the pages associated with overflow data contained in said other overflow page.

13. A method as in claim 11 for accessing more data than can be contained in said overflow pages comprising the steps of:

recursively applying steps (a), (b), (c) and (d) as overflow pages themselves overflow, thereby resulting in a tree of overflow pages.

10. A three phase method for establishing, maintaining and accessing a key-accessed file management organization and procedure ina computer system which includes a primary and secondary memory, said establishing phase comprising:

providing a data level including a set of blocks of pages stored in the secondary memory;

providing an index level stored in the primary memory when the file is in use;

said index level including a set of index entries, each of which includes a starting address indicating the location on the secondary memory where a block of contiguous pages begins; and

a size field indicating the number of pages in said block of pages having said starting address;

said maintaining phase including;

changing the nuxler of pages in said blocks as the size of the file changes;

said accessing phase including accessing more data than can be contained in a single page comprising the steps of;

associating at least one overflow page with said block of pages; and

placing the address of said at least one overflow page at a predetermined location in said pages.