EP0632364A1
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Efficient storage of object in a file system
Assignee: Microsoft Corp
•
Filing: 1994-06-28
•
Granted: —
•
Expires: 2014-06-28
Abstract
Abstract A file system provides a hierarchical approach to storage of file data. Logically contiguous bytes of file data are stored in stream data structures, and streams which hold related file data are stored in a variable sized onode data structures on disk. The variable-sized onode data structures are stored in fixed sized buckets, and the buckets are organized into a variable sized array. Thus, the file system provides a combination of variable-sized storage with fixed-sized storage to provide a very efficient approach to storing file data. In addition, indexes may be provided within the structures to allow quick access to onodes and streams.
Inventors
- 👤 Mark Zbikowski
- 👤 Brian T. Berkowitz
- 👤 Robert I. Ferguson
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-09 18:58
CPC Classifications
G; G06; G06F; G06F3/00; G06F3/06; G06F3/0601; G06F3/0602; G06F3/0604; G06F3/0628; G06F3/0638; G06F3/0643; G06F3/0668; G06F3/0671; G06F3/0673; G06F3/0674; G11; G11B; G11B20/00; G11B20/10; G11B20/12; G11B20/1217; G11B20/1252; G11B27/00; G11B27/10; G11B27/19; G11B27/28; G11B27/32; G11B27/327; G11B27/329; G11B2220/00; G11B2220/20
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
102 words
In a data processing system having secondary storage with memory space, a method of storing file data in the secondary storage, comprising the steps of: logically partitioning at least a portion of the memory space in the secondary storage into fixed-sized data structures; storing a first set of logically related file data of a first size in a first variable-sized data structure of a given type; and storing the first variable-sized data structure of the given type in which the first set of logically related file data is stored in at least one of the fixed-sized data structures in the secondary storage.
Claim 2
Dependent Claim
74 words
The method recited in claim 1, further comprising the steps of: storing a second set of logically related file data of a second size in a second variable-sized data structure of the given type; and storing the second variable-sized data structure of the given type in which the second set of logically related file data is stored in the fixed-sized data structure in which the first set of logically related file data is stored.
Claim 3
Dependent Claim
54 words
The method recited in claim 1 wherein the step of logically partitioning at least a portion of the memory space in the secondary storage into fixed-sized data structures further comprises the step of logically partitioning at least a portion of memory in the secondary storage into a variable-sized array of the fixed-sized data structures.
Claim 4
Dependent Claim
55 words
The method recited in claim 1 wherein the secondary storage is disk storage and wherein the step of logically partitioning at least a portion of the memory space in the secondary storage further comprises the step of logically partitioning at least a portion of the memory space in the disk storage into fixed-sized data structures.
Claim 5
Dependent Claim
28 words
The method recited in claim 1, further comprising the step of storing property information about the first variable-sized data structure of the given type in the secondary storage.
Claim 6
Dependent Claim
28 words
The method recited in claim 5, further comprising the step of querying the first variable-sized data structure of the given type to obtain the property information stored therein.
Claim 7
Dependent Claim
41 words
The method recited in claim 1, further comprising the step of storing an identification in the variable-sized data structure of the given type that uniquely identifies the first variable-sized data structure of the given type stored in the fixed-sized data structure.
Claim 8
Dependent Claim
85 words
A data processing system, comprising: internal memory; secondary storage; means for logically partitioning at least a portion of memory space in the secondary storage device into fixed-sized data structures; means for storing a first set of logically related file data in a first variable-sized data structure of a given type; and means for storing the first variable sized data structure in which the first set of logically related file data is stored in at least one of the fixed-sized data structures in the secondary memory.
Claim 9
Dependent Claim
74 words
A data processing system as recited in claim 8, further comprising: means for storing a second set of logically related file data in a second variable-sized data structure of the given type; and means for storing the second variable-sized data structure of the given type in which the second set of logically related file data is stored in the fixed-sized data structure in which the first set of logically related file data is stored.
Claim 10
Dependent Claim
14 words
The data processing system of claim 8 wherein the secondary storage is disk storage.
Claim 11
Dependent Claim
28 words
The data processing system of claim 8, further comprising means for storing property information about the first variable-sized data structure of the given type in the secondary storage.
Claim 12
Dependent Claim
28 words
The data processing system of claim 11, further comprising means for querying the first variable-sized data structure of the given type to obtain the property information stored therein.
Claim 13
Dependent Claim
73 words
In a data processing system having secondary storage, a method comprising the steps of: storing logically contiguous bytes of file data in variable-sized data structures of a first type; storing sets of the variable-sized data structures of the first type in which are stored related file data in a variable-sized data structure of a second type; and storing the variable-sized data structure of the second type in fixed-sized data structures in secondary storage.
Claim 14
Dependent Claim
64 words
The method recited in claim 13, further comprising the steps of: logically partitioning the memory space of the secondary storage into fixed-sized units; and associating each of the fixed-sized units with a corresponding one of fixed-sized data structures such that when data is stored in one of the fixed-sized data structures, the data is stored in the corresponding fixed-sized unit in the secondary storage.
Claim 15
Dependent Claim
76 words
The method recited in claim 14, further comprising the step of providing an array of the fixed-sized data structures for the memory space of the secondary storage and wherein the step of storing the variable-sized data structures of the second type in the fixed-sized data structures in the secondary storage further comprises the step of storing the variable-sized data structures of the second type in the fixed-sized data structures of the array in the secondary storage.
Claim 16
Dependent Claim
81 words
The method recited in claim 13 wherein the step of storing logically contiguous bytes of file data in variable-sized data structures of the first type further comprises the step of storing an identifier in each data structure of the first type to uniquely identify the logically contiguous bytes stored in the variable-sized data structure of the first type among the variable-sized data structures of the first type held in a same one of the variable-sized data structure of the second type.
Claim 17
Dependent Claim
55 words
The method recited in claim 13 wherein the secondary storage is disk storage and the step of storing the variable-sized data structures of the second type in fixed-sized data structures in secondary storage further comprises the step of storing the variable-sized data structures of the second type in fixed-sized data structures in the disk storage.
Claim 18
Dependent Claim
29 words
The method recited in claim 13, further comprising the step of storing property information in the secondary storage for each of the variable-sized data structures of the second type.
Claim 19
Dependent Claim
29 words
The method recited in claim 18, further comprising the step of querying one of the variable-sized data structures of the second type to obtain the property information contained therein.
Claim 20
Dependent Claim
71 words
A data processing system comprising: internal storage; secondary storage; means for storing logically contiguous bytes of file data in variable-sized data structures of a first type; means for storing sets of the variable-sized data structures of the first type that hold related file data in variable-sized data structures of a second type; and means for storing the variable-sized data structures of the second type in fixed-sized data structures in secondary storage.
Claim 21
Dependent Claim
67 words
The data processing system of claim 20, further comprising: means for logically partitioning the memory space of the secondary storage into fixed-sized units; and means for associating each of the fixed-sized units with a corresponding one of the fixed-sized data structures such that when data is stored in one of the fixed-sized data structures, the data is stored in the corresponding fixed-sized unit in the secondary storage.
Claim 22
Dependent Claim
85 words
In a data processing system having secondary storage, a method comprising the steps of: storing sets of logically contiguous bytes of file data in respective variable-sized data structures of a first type; storing variable-sized data structures of the first type which store related file data in a variable-sized data structure of a second type in the secondary storage; and storing a B-tree index to the variable-sized data structures of the first type in the variable-sized data structure of the second type in the secondary storage.
Claim 23
Dependent Claim
36 words
The method recited in claim 22, further comprising the step of locating logically contiguous bytes of file data in the variable-sized data structure of the second type in the secondary storage by accessing the B-tree index.
Claim 24
Dependent Claim
76 words
The method recited in claim 22 wherein the step of storing the B-tree index to the variable-sized data structures of the first type in the variable-sized data structure of the second type in the secondary storage further comprises the step of storing the B-tree index to the variable-sized data structures of the first type in the variable-sized data structure of the second type in the secondary storage as a variable-sized data structure of the first type.
Claim 25
Dependent Claim
100 words
In a data processing system having secondary storage, a method comprising the steps of: storing logically contiguous bytes of file data in variable-sized data structures of a first type; storing variable-sized data structures of a second type in the secondary storage, wherein each variable-sized data structure of the second type stores a set of the variable-sized data structures of the first type that store related file data; and in each variable-sized data structure of the second type, storing a B-tree index to the variable-sized data structures of the first type stored in the variable-sized data structure of the second type.
Claim 26
Dependent Claim
127 words
In a data processing system having secondary storage that includes memory space which holds an array of fixed-size buckets and one of the buckets holds an object, a method of allocating additional memory space in the secondary storage to fulfill growing requirements of the object comprising the steps of: determining whether the bucket that currently holds the object has sufficient free memory space to fulfill the growing requirements of the object; when the bucket that currently holds the object has sufficient free memory space, allocating additional space into the bucket to the object to fulfill the growing requirements of the object; and otherwise, finding a bucket that has sufficient memory space to fulfill the growing requirements of the object and moving the object to the found bucket.
Claim 27
Dependent Claim
60 words
The method of claim 26 wherein the step of finding a bucket that has sufficient memory space to fulfill the growing requirements of the object further comprises finding a bucket that has sufficient memory space to fulfill the growing requirements of the object that is in closest proximity in the secondary storage to the bucket that currently holds the object.
Claim 28
Dependent Claim
128 words
In a data processing system having secondary storage, a method comprising the steps of: storing files in an array of fixed-sized buckets of storage space in the secondary storage, wherein at least one of the fixed-sized buckets of storage space has more than one file stored in it; providing an identifier for each file that identifies the file among those stored in the array; storing a map in the secondary storage that maps each identifier for a file into the fixed-sized bucket in which the file is stored; locating one of the files having a selected identifier in the array by using the map to locate the fixed-sized bucket in which the file is stored and searching the fixed-sized bucket to locate the file having the selected identifier.
Claim 29
Dependent Claim
105 words
In a data processing system having secondary storage, a method comprising the steps of: storing files in array of fixed-sized buckets of storage space in the secondary storage, wherein each file has an identifier associated with it; storing a mapping structure of multiple entries in the secondary storage, said entries including at least one entry that maps another of the identifiers to one of the buckets in the array; storing in the mapping structure a free list of identifiers of cells of space in the secondary storage that are unallocated; and using the mapping structure to locate a bucket from the identifier of the bucket.
Claim 30
Dependent Claim
23 words
The method recited in claim 29, further comprising the step of using the mapping structure to locate an identifier in the free list.
Claim 31
Dependent Claim
136 words
In a data processing system having secondary storage, a method comprising the steps of: providing an array of fixed-sized buckets of storage space in the secondary storage, for storing files, each file having an identifier associated with it; providing a mapping structure of multiple entries in the secondary storage for mapping identifiers to either cells in the free list or buckets in the array; providing a free list in the mapping structure, said free list including identifiers of any free cells of space in the secondary storage; determining if the free list contains an identifier for at least one cell; and where the free list contains an identifier for at least one cell, assigning a selected identifier of a cell from the free list to a new file and storing the new file in the cell.
Claim 32
Dependent Claim
33 words
The method recited in claim 31, further comprising the step of: where the free list contains no cells, adding additional entries to the mapping structure that map new identifiers to new free cells.
Claim 33
Dependent Claim
51 words
The method recited in claim 32, further comprising the steps of: assigning one of the new identifiers associated with one of the new free cells to the new file; and storing the new file in the new free cell associated with the new identifier that is assigned to the new file.
References Cited (Backward Citations)
US5206939A
Cited
EP0488700A2
Cited
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.