EP0117906A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Key-accessed file organization
Assignee: International Business Machines Corp
•
Filing: 1983-11-24
•
Granted: —
•
Expires: 2003-11-24
Abstract
Abstract This invention is the organizing of a key-accessed (indexed) file 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 support 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.
Inventors
- 👤 David Bruce Lomet
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-04 05:42
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9014; G06F16/9017
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
87 words
A key-accessed file in a computer system which includes a primary (computer) and secondary (disk) memory, said file comprising: a data level including a set of blocks of pages stored in the secondary memory; an index level (BEH Index) stored in the primary memory when the file is in use;and said index level including a set of index entries, each of which references, respectively, one of said blocks of pages, with the number of pages in said blocks being changeable as the size of the file changes.
Claim 2
Dependent Claim
87 words
A key-accessed file in a computer system which includes a primary (computer) and secondary (disk) memory, said file comprising: a data level including a set of blocks of pages stored in the secondary memory; an index level (BEH Index) stored in the primary memory when the file is in use;and said index level including a set of index entries, each of which references, respectively, one of said blocks of pages, with the number of pages in said blocks being changeable as the size of the file changes.
Claim 3
Dependent Claim
48 words
A key-accessed file as in claim 1 wherein each of said index entries has associated with it: an address indicating the location on the secondary memory where a block of contiguous pages begins;and a size indicating the number of pages in said block of pages having said address.
Claim 4
Dependent Claim
25 words
A key-accessed file as in claim 2 wherein said size specifies the logarithm, base two, of the number of pages referenced by said index entry.
Claim 5
Dependent Claim
46 words
A key-accessed file as in claim 1 wherein the keys in the index level are initially organized by the method of: distributing the keys uniformly over their address space by a first function;and redistributing the keys exponentially over the same address space by a second function.
Claim 6
Dependent Claim
29 words
A key-accessed file as in claim 4 wherein: the first function, h, is chosen from a class of universal hashing functions;and the second function is 2 h (key) -1:
Claim 7
Dependent Claim
51 words
In the key-accessed file of claim 1, a method of increasing/decreasing 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 said index entry which is twice/half the size of said block of pages.
Claim 8
Dependent Claim
58 words
A method as in claim 6 further comprising the steps of. setting the value of the size associated with said index entry to the number of pages in said second block;and changing the 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.
Claim 9
Dependent Claim
56 words
In the key-accessed file of claim 1, a method of searching said file comprising the steps of: finding the index entry associated with a selected key;and computing, based on an address and a size associated with said index entry, the page, among the block of pages addressed, in which data associated with said key is found.
Claim 10
Dependent Claim
90 words
A method as in claim 8 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 bits of said key, where n is the logarithm, base two, of the number of pages in the block referenced by said entry;and 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.
Claim 11
Dependent Claim
74 words
In a key-accessed file as in claim 1, a method of 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 selectively placing the address of said at least one overflow page in said pages, each said overflow page being associated with a contiguous sub-block of pages, with each page of the block being in a unique sub-block.
Claim 12
Dependent Claim
91 words
A method as in claim 10 for accessing more data than can be contained in said first overflow page comprising the steps of: (a) associating the first overflow page with a contiguous sub-block of pages; (b) associating a second overflow page with a second contiguous sub-block of pages; (c) with each page being in a unique sub-block; (d) inserting into said first overflow page the address of said second overflow page as part of an index entry which identifies the pages associated with overflow data contained in said second overflow page.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.