Method and apparatus for storing compressed file data on a disk where each MDFAT data structure includes an extra byte

• US 5,809,295 A
• Filed: 09/26/1995
• Issued: 09/15/1998
• Est. Priority Date: 09/26/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jernigan, Richard P. IV, Stewart, Peter Blackburn, Quinn, Scott D., Straub, Eric John
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US08/506,971
• Time in Patent Office: 1,085 Days
• Field of Search: 395/430, 395/600, 395/404, 395/601, 395/602, 395/612, 395/439, 364/222.81
• US Class Current: 1/1
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0676 Magnetic disk device
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method and apparatus for storing compressed file data stored on a disk. The method includes an improved format for the Compressed Volume File (CVF), and more specifically, 10 an improved format for the MDFAT data structure stored within the CVF. The improved format includes using an additional byte for maintaining each entry in the MDFAT data structure which increases the number of sectors within the Sector Heap that can be addressed and accessed. The improved format further allows compressed clusters to be stored in fragments in various portions of vacant storage space located throughout the Sector Heap. The new format for the MDFAT data structure includes a bit that identifies whether each cluster is being stored in fragments. The method stores the locations of each of the fragments in a Fragment Pointer List located in the first sector of the first fragment.

Claims

1. A method for storing at least one cluster of file data in a plurality of fragments of non-adjacent sectors on a disk, each cluster comprising a plurality of sectors, each sector being a fixed length capable of storing a predetermined, fixed number of bytes, said method comprising the steps of:

maintaining a first data structure having an entry for each file stored on the disk, each entry identifying the cluster in which the first portion of each respective file is stored;

maintaining a second data structure having an entry for each cluster on the disk, each entry identifying another cluster in which the next portion of each respective file is stored;

maintaining a third data structure having an entry for each cluster on the disk, each entry identifying the sectors used to store the data for each respective cluster, and each entry identifying whether the data for each respective cluster is stored in fragments;

identifying the sectors used to store the data of each fragment; and

placing entries in the first, second, and third data structures in accordance with the location of data stored in each separate cluster.

2. The method of claim 1 wherein each respective entry of the third data structure comprises a first field for identifying the first sector in which the data of each respective cluster is stored.

3. The method of claim 1 wherein each respective entry of the third data structure comprises a second field for identifying whether the data of each respective cluster is stored in fragments.

4. The method of claim 1 wherein each respective entry of the third data structure comprises a third field for identifying:

the number of sectors used to store the data of each respective cluster, if a cluster is not stored in fragments;

or

the number of sectors used to store the data of the first fragment of each respective cluster, if a cluster is stored in fragments.

5. The method of claim 1 wherein each respective entry of the third data structure is not greater than five bytes in length.

6. The method of claim 2 wherein the first field of the third data structure is capable of identifying any one of over 8 million sectors.

7. The method of claim 2 wherein the first field of the third data structure is not greater than twenty-three bits in length.

8. The method of claim 3 wherein the second field of the third data structure is one bit in length.

9. The method of claim 4 wherein the third field of the third data structure is capable of identifying up to sixty-four sectors for each respective cluster.

10. The method of claim 4 wherein the third field of the third data structure is not greater than six bits in length.

11. The method of claim 1 wherein the sectors used to store each fragment are identified in a fourth data structure.

12. The method of claim 11 wherein the fourth data structure identifies the first sector of each fragment and the number of sectors used to store each fragment.

13. The method of claim 11 wherein the fourth data structure is stored in the first fragment.

14. The method of claim 11 wherein the fourth data structure is stored in the first sector of the first fragment.

15. A system for storing at least one cluster of file data in a plurality of fragments of non-adjacent sectors on a disk, each cluster comprising a plurality of sectors, each sector being a fixed length capable of storing a predetermined, fixed number of bytes, comprising:

a computer having a memory;

an operating system stored within said memory;

a disk drive operatively connected to said computer for storing data on said disk;

wherein said operating system comprises;

means for maintaining a first data structure on said disk, said first data structure having an entry for each file stored on said disk, each entry identifying the cluster in which the first portion of each respective file is stored;

means for maintaining a second data structure on said disk, said second data structure having an entry for each cluster on said disk, each entry identifying another cluster in which the next portion of each respective file is stored;

means for maintaining a third data structure on said disk, said third data structure having an entry for each cluster on said disk, each entry identifying the sectors used to store the data for each respective cluster, and each entry identifying whether the data for each respective cluster is stored in fragments;

means for identifying the sectors used to store the data of each fragment; and

means for placing entries in said first, second, and third data structures in accordance with the location of data stored in each respective cluster.

16. The system of claim 15 wherein each respective entry of said third data structure comprises a first field for identifying the first sector in which the data of each respective cluster is stored.

17. The system of claim 15 wherein each respective entry of said third data structure comprises a second field for identifying whether the data of each respective cluster is stored in fragments.

18. The system of claim 15 wherein each respective entry of the third data structure comprises a third field for identifying:

the number of sectors used to store the data of each respective cluster, if a cluster is not stored in fragments;

or

the number of sectors used to store the data of the first fragment of each respective cluster, if a cluster is stored in fragments.

19. The system of claim 15 wherein each entry of said third data structure is not greater than five bytes in length.

20. The system of claim 16 wherein said first field of said third data structure is capable of identifying any one of over 8 million sectors.

21. The system of claim 16 wherein said first field of said third data structure is not greater than twenty-three bits in length.

22. The system of claim 17 wherein said second field of said third data structure is one bit in length.

23. The system of claim 18 wherein said third field of said third data structure is capable of identifying up to sixty-four sectors for each respective cluster.

24. The system of claim 18 wherein said third field of said third data structure is not greater than six bits in length.

25. The system of claim 15 wherein the sectors used to store each said fragment are identified in a fourth data structure.

26. The system of claim 25 wherein said fourth data structure identifies the first sector of each said fragment and the number of sectors used to store each said fragment.

27. The system of claim 25 wherein said fourth data structure is stored in the first fragment.

28. The system of claim 25 wherein said fourth data structure is stored in the first sector of said first fragment.

29. The system of claim 25 wherein said operating system identifies the sectors used to store each said fragment by reading said fourth data structure prior to accessing any of said fragments.

30. The system of claim 25 wherein said operating system accesses said fragments in a sequence based on the location of each said fragment on said disk.

31. A computer-readable medium on which is stored a program for storing at least one cluster of file data in a plurality of fragments of non-adjacent sectors on a disk, each cluster comprising a plurality of sectors, each sector being a fixed length capable of storing a predetermined, fixed number of bytes, the program comprising instructions which, when executed by the computer, perform the steps of:

maintaining a first data structure having an entry for each file stored on the disk, each entry identifying the cluster in which the first portion of each respective file is stored;

maintaining a second data structure having an entry for each cluster on the disk, each entry identifying another cluster in which the next portion of each respective file is stored;

maintaining a third data structure having an entry for each cluster on the disk, each entry identifying the sectors used to store the data for each respective cluster, and each entry identifying whether the data for each respective cluster is stored in fragments;

identifying the sectors used to store the data of each fragment; and

placing entries in the first, second, and third data structures in accordance with the location of data stored in each separate cluster.

32. The medium of claim 31 wherein each respective entry of the third data structure comprises a first field for identifying the first sector in which the data of each respective cluster is stored.

33. The medium of claim 31 wherein each respective entry of the third data structure comprises a second field for identifying whether the data of each respective cluster is stored in fragments.

34. The medium of claim 31 wherein each respective entry of the third data structure comprises a third field for identifying:

the number of sectors used to store the data of each respective cluster, if a cluster is not stored in fragments;

or

the number of sectors used to store the data of the first fragment of each respective cluster, if a cluster is stored in fragments.

35. The medium of claim 31 wherein each respective entry of the third data structure is not greater than five bytes in length.

36. The medium of claim 32 wherein the first field of the third data structure is capable of identifying any one of over eight million sectors.

37. The medium of claim 32 wherein the first field of the third data structure is not greater than twenty-three bits in length.

38. The medium of claim 33 wherein the second field of the third data structure is one bit in length.

39. The medium of claim 34 wherein the third field of the third data structure is capable of identifying up to sixty-four sectors for each respective cluster.

40. The medium of claim 34 wherein the third field of the third data structure is not greater than six bits in length.

41. The medium of claim 31 wherein the sectors used to store each fragment are identified in a fourth data structure.

42. The medium of claim 41 wherein the fourth data structure identifies the first sector of each fragment and the number of sectors used to store each fragment.

43. The medium of claim 41 wherein the fourth data structure is stored in the first fragment.

44. The medium of claim 41 wherein the fourth data structure is stored in the first sector of the first fragment.