US6282605B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
File system for non-volatile computer memory
Assignee: MCCI CORP
•
Filing: 1999-04-26
•
Granted: 2001-08-28
•
Expires: 2019-04-26
Abstract
Abstract A memory management system for random access memories employs a novel B-tree structure to map physical memory locations to logical addresses. In the preferred arrangement each key in the tree structure contains the physical address corresponding to the logical address identifying the key and also contains the size of the data block at that address. The invention also provides a novel arrangement for updating B-trees in response to changes in the keys. The tree buckets containing modified keys are recorded in storage locations other than the locations containing the keys prior to modification. Thus, until the modification of the tree is complete, the system contains a record of the entire tree structure prior to the beginning of the modification.
Inventors
- 👤 Terrill Moore
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 04:06
CPC Classifications
G; G06; G06F; G06F3/00; G06F3/06; G06F3/0601; G06F3/0602; G06F3/0614; G06F12/00; G06F12/02; G06F12/0223; G06F12/0292; G06F16/00; G06F16/10; G06F3/0628; G06F3/0638; G06F3/0643; G06F3/0668; G06F3/0671; G06F3/0673; G06F3/0679; G06F12/023; G06F12/0238; G06F12/0246; G06F2212/00; G06F2212/20; G06F2212/202; G06F2212/2022; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99935; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
234 words
A memory system for a computer system, said memory system comprising: A. a random access memory comprising: 1. multiple erasure blocks each of which comprises multiple sectors of physical locations, an erasure block containing the minimum number of physical locations that are erasable in a single operation by the memory system; and 2. multiple sheaves, each of which comprises one or more erasure blocks; B. a B-tree file directory structure stored in a tree-storage location in said computer system and providing translations from logical input addresses to physical addresses in the random-access memory, said B-tree file directory structure including a plurality of buckets arranged in a multi-level hierarchical relationship from a root bucket to lower level buckets, each bucket containing; 1. keys each of which includes a logical address of a data block and the physical address in the random-access memory corresponding to the logical address, and 2. in each bucket above the lowest level also containing pointers to buckets in the next lower level; and C. means for modifying the B-tree file directory structure, in response to changes in said keys, by recording modified versions of the buckets affected by the key changes in storage locations other than the locations containing the buckets prior to tree modification, whereby until the modification of buckets is completed, the tree-storage locations contain the B-tree file directory structure existing prior to the beginning of the tree modification.
Claim 2
Dependent Claim
234 words
A memory system for a computer system, said memory system comprising: A. a random access memory comprising: 1. multiple erasure blocks each of which comprises multiple sectors of physical locations, an erasure block containing the minimum number of physical locations that are erasable in a single operation by the memory system; and 2. multiple sheaves, each of which comprises one or more erasure blocks; B. a B-tree file directory structure stored in a tree-storage location in said computer system and providing translations from logical input addresses to physical addresses in the random-access memory, said B-tree file directory structure including a plurality of buckets arranged in a multi-level hierarchical relationship from a root bucket to lower level buckets, each bucket containing; 1. keys each of which includes a logical address of a data block and the physical address in the random-access memory corresponding to the logical address, and 2. in each bucket above the lowest level also containing pointers to buckets in the next lower level; and C. means for modifying the B-tree file directory structure, in response to changes in said keys, by recording modified versions of the buckets affected by the key changes in storage locations other than the locations containing the buckets prior to tree modification, whereby until the modification of buckets is completed, the tree-storage locations contain the B-tree file directory structure existing prior to the beginning of the tree modification.
Claim 3
Dependent Claim
18 words
The memory system defined in claim 1 in which said tree-storage locations are in said random access memory.
Claim 4
Dependent Claim
16 words
The memory system defined in claim 2 in which random access memory is a non-volatile memory.
Claim 5
Dependent Claim
17 words
The memory system defined in claim 3 in which said random access memory is a flash memory.
Claim 6
Dependent Claim
80 words
The memory system of claim 1 : A. including a second memory; and B. in which said modifying means 1. records in said second memory the tree buckets that are modified in accordance with said key changes, the recorded buckets being further modified to reflect their locations in said second memory; and 2. subsequently re-records the modified tree buckets in said tree storage locations after further modification to reflect the locations of the modified buckets in said tree storage locations.
Claim 7
Dependent Claim
209 words
The memory system defined in claim 1 in which each sheaf includes: A. a plurality of data blocks, each data block for recording either application data of said computer system or a tree structure data; and B. a plurality of log blocks including: 1. one or more header blocks, a first header block occupying a fixed location in the sheaf, each header block containing: a. a pointer to the location of the root bucket in said tree storage locations as of the time the header block was written, b. a sequence number indicating the order in which the header block was written relative to the other header blocks in the memory system, and c. a pointer to the location of a header block in said sheaf that supersedes the header block; and 2. for each data block in the sheaf containing application data, a data log block containing: i. the logical address of the data block, and ii. the physical address of the data block in the sheaf; and 3. for each data block in the sheaf containing tree structure data, corresponding data log lock containing: a. the physical address of the data block; and b. identification of the type of tree structure data contained in the data block.
Claim 8
Dependent Claim
26 words
The memory system of claim 1 in which each of said keys includes the size of the data block at the physical address in the key.
Claim 9
Dependent Claim
18 words
The system defined in claim 4 in which the tree-storage locations are contained in said random access memory.
Claim 10
Dependent Claim
17 words
The memory system defind in claim 6 in which said random access memory is a flash memory.
Claim 11
Dependent Claim
27 words
The memory system defined in claim 8 in which each of said keys includes the size of the data block at the physical address in the key.
Claim 12
Dependent Claim
27 words
The memory system defined in claim 7 in which said random access memory is a non-volatile memory and said tree storage locations are in said non-volatile memory.
Claim 13
Dependent Claim
31 words
The memory system defined in claim 5 in which: a. said random access memory is a non-volatile random access memory; and b. said second memory is a volatile random access memory.
Claim 14
Dependent Claim
176 words
A memory system comprising for a computer system said memory system comprising: A. a random access memory comprising: 1. multiple erasure blocks each of which comprises multiple sectors of physical locations, an erasure block containing the minimum member of physical locations that are erasable in a single operation by the memory system; and 2. multiple sheaves, each of which comprises one or more erasure blocks; B. a B-tree file directory structure stored in a tree-storage location in said computer system and providing translations from logical input addresses to physical addresses in the random-access memory, said B-tree file directory structure including a plurality of buckets arranged in a multi-level hierarchical relationship from a root bucket to lower level buckets, each bucket containing; 1. keys each of which includes a logical address of a data block, the physical address in the random-access memory corresponding to the logical address, and the size of the data block at the physical address; and 2. in each bucket above the lowest level also containing pointers to buckets in the next lower level.
Claim 15
Dependent Claim
176 words
A memory system comprising for a computer system said memory system comprising: A. a random access memory comprising: 1. multiple erasure blocks each of which comprises multiple sectors of physical locations, an erasure block containing the minimum member of physical locations that are erasable in a single operation by the memory system; and 2. multiple sheaves, each of which comprises one or more erasure blocks; B. a B-tree file directory structure stored in a tree-storage location in said computer system and providing translations from logical input addresses to physical addresses in the random-access memory, said B-tree file directory structure including a plurality of buckets arranged in a multi-level hierarchical relationship from a root bucket to lower level buckets, each bucket containing; 1. keys each of which includes a logical address of a data block, the physical address in the random-access memory corresponding to the logical address, and the size of the data block at the physical address; and 2. in each bucket above the lowest level also containing pointers to buckets in the next lower level.
Claim 16
Dependent Claim
75 words
The memory system defined in claim 13 including means for modifying the B-tree file directory structure, in response to changes in said keys, by recording modified versions of the buckets affected by the key changes in storage locations other than the locations containing the buckets prior to tree modification, whereby until the modification of buckets is completed, the tree-storage locations contain the B-tree file directory structure existing prior to the beginning of the tree modification.
Claim 17
Dependent Claim
75 words
The memory system of claim 14 : A. including a second memory; and B. in which said modifying means records in said second memory buckets that are modified in accordance with said key changes, the recorded buckets being further modified to reflect their locations in said second memory; and 2. subsequently re-records the modified buckets in said tree storage locations after further modification to reflect the locations of the modified buckets in said storage locations.
Claim 18
Dependent Claim
31 words
The memory system defined in claim 15 in which: a. said random access memory is a non-volatile random access memory; and b. said second memory is a volatile random access memory.
Claim 19
Dependent Claim
209 words
The memory system defined in claim 13 in which each sheaf includes: A. a plurality of data blocks, each data block for recording either application data of said computer system or a tree structure data; and B. a plurality of log blocks including: 1. one or more header blocks, a first header block occupying a fixed location in the sheaf, each header block containing: a. a pointer to the location of the root bucket in said tree storage locations as of the time the header block was written, b. a sequence number indicating the order in which the header block was written relative to the other header blocks in the memory system, and C. a pointer to the location of a header block in said sheaf that supersedes the header block; and 2. for each data block in the sheaf containing application data, a data log block containing: i. the logical address of the data block, and ii. the physical address of the data block in the sheaf; and 3. for each data block in the sheaf containing tree structure data, corresponding data log lock containing: a. the physical address of the data block; and b. identification of the type of tree structure data contained in the data block.
References Cited (Backward Citations)
US4956774A
Cited
US5408652A
Cited
US5553303A
Cited
US5404485A
Cited
US5613105A
Cited
US5446887A
Cited
US5522068A
Cited
US5826253A
Cited
US5918224A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-08-27 | 2005-02-26 | 2005-08-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-08-27 | 2009-02-26 | 2009-08-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-08-27 | 2013-02-26 | 2013-08-28 | $7700.00 | Window Closed / Lapsed |