JPS63116232A - Method of memorizing and retrieving data using computer - Google Patents

Abstract

(57) [Abstract] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed description of the invention]

FIELD OF APPLICATION This invention relates to methods for storing and retrieving data using computers, and more particularly to hierarchical file systems. BACKGROUND OF THE INVENTION In computer systems, information is typically
Signals and signals are stored in storage devices such as magnetic tapes, disks, and semiconductor devices. Advances in storage device technology have increased storage capacity, allowing devices to store more information than ever before. When information is stored on a device, it is cataloged so that the same information can be retrieved at a later time when desired. Each data body is usually given a unique code name to distinguish it from other data bodies. To search for a certain body of data, the code name given to that data is used,
In other words, the device searches for the code name and, when it finds it, retrieves the desired data. As is well known in the art, each independent body of data is called a t-file, and the cataloging of these files on a device is called a file. A code name has a pointer that indicates the storage area where the data body is stored. A number of code names and their pointers form a catalog system. A mass storage device is used. In some cases, such devices can contain millions of bits.
You can memorize information about things, but this allows you to memorize hundreds of things.
Thousands or even millions of files can be created. Searching through these files in order to locate a particular file is a waste of time. What is needed is a complete storage file system that can quickly locate and retrieve desired stored files. Furthermore, with the advent of personal computers (PCs) and small office computers, due to their physical size, it is desirable that filing systems be implemented with just one line in a program and be fully effective. SUMMARY OF THE INVENTION The present invention relates to a method for providing a hierarchical file system. A hierarchical file system has an inventory of data stored in such locations within a memory device. Typically, one inventory configuration constitutes one memory volume. The inventory structure of the hierarchical file system is an inverted tree structure, with a starting directory tV serving as the root directory. Other directories and files are its child segments. A number of child-level branches extend down to form a hierarchical organization of the inventory. The inventory structure contains information on the location where current data is stored. This file cataloging system forms a B-tree structure. Inventory information is stored in leaf nodes of the B tree. Non-leaf nodes (index nodes) of the B@ tree contain information that allows searching for specific inventory information using the code name or key of the associated file. Keys are used not only to represent and catalog various files within the cataloging system, but also to organize and refine catalogs within B-tree nodes. A key ranks high in a sequence of accesses. Furthermore, the B tree grows in a left-handed rotation manner, and this left-handed growth is done by inserting new file inventory information from the right side, thereby maintaining the balance of the tree. When data for a file is stored, additions, deletions, and modifications typically result in non-contiguous data storage within the memory device. Each contiguous segment of a file is known as a file extent. A record of the physical location of extents within a particular file is stored in one or more extent records. Hierarchical file systems use a single file extent list to map various extents within a memory device. In the present invention, the first extent record of a file is stored in the catalog structure, but more extent records are stored in a split file extent list.This file extent list is also stored in a split file extent list. Embodiments of the Invention The present invention relates to a method for storing and retrieving information using a hierarchical file system. For the purpose of a general understanding, a number of specific details are set forth in advance; however, it will be apparent to one skilled in the art that the present invention may be practiced without such specific details. On the other hand, in order not to obscure the invention unnecessarily, well-known methods will not be described in detail. In FIG. A uniform file system 10 is shown for ease of understanding.For ease of understanding, a directory IJ H folder is shown pictographically, and a file is shown as a sheet of paper with one bent corner.This pictorial representation: This is appropriate because the act of putting a paper into a folder corresponds to the act of registering a file in a directory.In the prior art system 10, a single directory 11 exists, and this directory stores the location information of files 12-15. Yes1.
ing. Each of the files 12 to 15 contains data specifying the stored information. In system 10, which is an example of the prior art, in order to access file 15, 1. However, when a large number of files are registered in the directory 11, such a sequential search ends up taking an enormous amount of time. In the hypothetical example of system 10, directory 11 stores the pointer addresses of four files 12 through 15, but in a sequential manner directory 11 will continue to store the addresses of subsequent files. Figure 2 shows the hierarchical file system (HFS) of the present invention.
This example hierarchical file system showing the configuration of 1
6 has a root directory 17 and files 21-24. Hierarchical file system 16 also includes directories 18-2o. Each directory can contain files and can also have other directories (such as directory 18 having directory 20). Each directory is itself a branch node and has O to 7 sub-branch nodes. Each directory has information that allows branching to occur. Usable data is stored in files 21-24. Since each file is a terminal node, it is not necessary to store further branch information. Instead, each file stores usable data. Tsu-! , Mudireku) IJs 17 to 20 store branch information, and files 21 to 24 store data. Since the hierarchical file system 16 accesses the files 21 to 24 in a hierarchical structure, there is no need to sequentially search for files. Assume that in the embodiment of FIG. 2, access to data stored in file 23 is requested. According to the search in directory 17, there are two possible paths to find the address of file 23. One path from directory 17 leads to directory 18, and the other path leads to directory 19. The desired path ends on the way to directory 18, where it again splits into two paths. File 23 from directory 18
The desired route leading to is now available. Although this embodiment is overly simplified with a small number of files illustrated, it will be appreciated that file search time is saved even if a large number of files are arranged. Furthermore, for example, if data in file 22 is desired, a path from directory 18 leads to directory 20, but there are two paths from directory 20. A preferred path from directory 20 to file 22 is then selected. The HF516 has a special configuration in Figure 2, but you can create as many branch levels as you like below the root directory 17.
Similarly, you can branch as many times as you want from a specific directory. However, considering that all data is stored in the display files 21-24 located at the end nodes of the HFS 16, this should not be the case. In fact, the catalog structure of this embodiment includes cataloged location information of a hierarchical file system 16 configuration. The inventory entries for files 21-24 have a pointer M that indicates the location, and this pointer locates the location in the storage area where the data is actually stored. (Description regarding B-tree) The hierarchical file system CI (FS) of the present invention operates using two B-tree structures of this embodiment, namely, an inventory B-tree and a file extent B-tree. The B-tree structure is well known in the prior art, and was published in 1973 by Donald E. Knuss in 1 Computer Programming Technology Journal: Volume 3 (Classification and Search), Part 6.
．． 4 (pages 471 to 479).The nodes of the B tree have records, and each record can contain arbitrary information, pointers or data, and An example of a B-tree is shown in Fig. 3. The basic feature of the B-tree 31 is that data is stored only in leaf nodes 35 to 3B. Internal nodes 32-34, also known as index nodes, have pointers to other eids, and these nodes serve as indexes and for accessing data records stored within leaf nodes 35-38. Each record 39 has a key 40 and an information segment 41. Since the record is stored within each node, the key is superior. - The example B tree 31 in Figure 3 has a temporary key. These were inserted to show the structure of the tree and the relationship between index nodes 32 to 34 and leaf nodes 35 to 38. Leaf node 35 has key elements 48 and 50. The first key of any node is also shown as the key of its higher level node.Therefore, the first key of leaf node 35, key 48, is also shown as the key of index node 33. The key 53, which is the first key of the leaf node 36, is the index node 3
3 as the second key. Also, since key 48 is the first key of index node 33, it is again shown as the key of index 32. This pattern is repeated at each leaf node 35-38 and each interval index node 32-34 of the B-tree configuration. Although only three levels and only two keys per node are shown in Figure 3, any number of keys per node, and likewise any number of levels, may be selected for a particular B-tree configuration. obtain. Third
The B tree configuration 31 displayed in the figure is only a provisional example for illustrative purposes. Once a data record is selected, the key of the desired record is presented. The search begins at the root node, which is also the index node. The search is performed until a record with the largest key less than the searched key is found. Assume in the example shown in FIG. 3 that data with key 59 is selected. The search begins at the root node 32, where the key 56, which is the largest key υ smaller than the key being searched for, is selected. The pointer of key 56 selects index node 34 and the search continues at this node. Again, key 5G is selected because it is the largest key smaller than the searched key itself (the next key 63 is larger than the searched key). Key 5 in index node 34
Pointer 6 selects leaf node 3T. Another search is performed within the leaf node 37 to determine the key 59 to be searched. Once the searched key 59 is found, the associated information (data) is used. Certain pointers within any index record lead to other nodes lower in the B-tree 31. For example, node 32 is connected to node 34. This process continues up to the leaf nodes, where the records are searched until the desired key is found. If the searched key does not exist, that is, a key greater than the searched key is found, or all records in the leaf node have been searched, the search ends. The key can be indicated in numerical order, alpha-bella) +19, or a mixed alphabetic and numerical order. FIG. 4 shows the configuration of arbitrary nodes of the B-tree of the present invention. Each node 42 has a node display segment 43, a record segment 44, a record branch segment 46, and may have a free space segment 45. Each node 42 begins with a node representation segment. N.D.
NREC 85B contains the current record number within the node. NDTYPE54 indicates whether the node type is a leaf node or an index node. NDHEIGHT
57 indicates the height of a node in a tree structure in which the height of the primary node is selected such that the index node is level 1 and the index node above it is level 2. NDBLINK5
2 and NDFLINK 5t are used with the nodes of the B-tree and act as a conduit to quickly transmit through the records of such nodes at a given level. At each node, NDBLINK 52 has a pointer to the previous mate and NDFLINK 51 has a pointer to the next node of the same node. In FIG. 3, NDBLINK of node 36 points to node 35, and NDFLINK of node 36 points to node 37. Therefore, NDBLINK 52 and NDFLINK51
is a means of finding neighboring nodes without the first inversion backing up the B-tree. Record segment 44 has B, inland records, each record having its key and pointer or data. The example shown in FIG. 4 has two records, 60 and 61. Records within any node can have different lengths. Therefore, a branch point is required to start each record. The record segment begins to directly follow the node display segment 43. The record is located before the free space segment 45, which is basically the unused space of the node. Therefore, a free space segment cannot be located in several places. The record branch segment 46 at the end of a node has branch information for records 60 and 61. Branch 68 has branch information for record 60, and branch 6T has branch information for records 60 and 61. It has branch information of record 61. Branch 66 has branch information that determines free space 62. In this way, record branch segment 4
6 is constructed from one end up into the free space segment 45, while the record segment 44 is constructed down from the opposite side into the free space segment 45. If node 42 is an index node, records 60 and 61 each contain key and pointer information. Also, N
DFLINK51 and NDBLINK52 have adjacent index nodes connected to pointers. If node 42 is a leaf node, records 60 and 61 each contain key and data information. NDFLINK51
and NDBLINK 52 also finds the leaf node that links to the pointer. Also, although node 42 is in a special format, the format may be easily modified to contain other types of information. Also in this embodiment, the data information in the leaf nodes of the HFS Catalog B tree is used to find the position #t in memory where useful data is stored. FIG. 5 is an enlarged view of the B# tree configuration implemented in this embodiment. Node 70, which is connected to node 42 in FIG. 4, holds a pointer following two lower nodes T1 and 73, which can be index nodes or leaf nodes. Although only two nodes 71 and 73 are displayed at the lower level, any number of nodes can be lined up at this lower level. Also, in this hypothetical example, nodes 71 and 73 are only partially filled. In order to maintain the balance of the B-tree, records are uniformly arranged and stored in a hierarchical structure. If records are not stored uniformly, an unbalanced tree will have each node or many nodes superimposed on only one branch. This embodiment utilizes left circulation and left split techniques to move records from one node to another to maintain a balanced tree. A left circular operation is used when transmitting records to other nodes. In this case, the record of node T3 is transmitted to the adjacent node 71 on the left as indicated by arrow 77 by left circulation. The record of node 73 is circulated and node γ
When another node is needed, such as when node 1 cannot process the record from node 73, a left-split operation inserts node 72 to the left of node 73 between nodes 71 and 13. As indicated by arrow 78, node 72 links node 71 and node 73 when inserted. When node 72 is inserted, appropriate pointer association will be established with the index node TO, as well as with the adjacent association pointers of nodes γ1 and 73. By continuously transmitting data to the left and inserting new data at the right end, the balance of the B-tree is maintained. Since the hierarchical file system of the present invention has upper nodes arranged in a rightward direction, it is possible to maintain balance even when rotation and division are performed in a leftward direction. It is also recognized that it is possible to perform a right-side split and right-circulation operation, that is, a balanced insertion that utilizes both right and left directions. Although this embodiment aims to maintain an efficient balanced B-tree, any B-tree configuration can be used, including unbalanced B-trees. (Inventory Tree Structure) FIG. 6 illustrates the execution of the inventory function in this embodiment. Configuration 90 has a root directory 91 named ``Volume 1''. Each directory in this embodiment is assigned a specific numerical identification known as a directory identification name (DirID). Root directory 91 of catalog 90 The Dir ID of is 2. The root directory 91 has directory 92 and file 9.
It has three branches that are divided into 3 and 94 branches. The name of the directory 92 is ``1 Folder'', and the name is Djr ID.
It is 1d29. Also, the directory 92 is file/l/
It has two branches splitting into 95 and 96. The names of files 93-96 are respectively %A in this example.
s, @B'', SC'', and 10''. The directory and file structure is based on the hierarchical file system (HFS) structure described above in FIG. The entire inventory structure 90 is stored as data records in leaf nodes, such as the B-tree of FIGS. 3 and 4, referred to as the inventory B-tree. Although the inventory component is a tree, it is not itself a B-tree. The features of configuration 90 are stored in a ready-to-use state at seven nodes in a B-tree. Inventory configuration 90 cannot be confused with the B tree described above. Inventory 90 and the B tree structure are two separate and distinct structures. The hierarchical structure of inventory 90 is implemented as a B@tree structure, and the structure is stored as data records in the leaf nodes of the B-tree similar to FIGS. 3 and 4. Hierarchical inventory structure 90 is stored in device 1α shown in memory map 9γ of FIG. Inventory map 97 has three possible types of records, which are directory records 100. File record 101
, and route record 102. Each record 100-102 has a key 103 and an information segment 104 as described in the explanation of the leaf nodes of the B-tree above. Each record's key 103 has a number 105 and a name 106. Keys 103 of directory records such as 91 and 92
has a directory name 106 and a directory identification name (Dlr ID) number 105 of the parent directory. The information segment 104 of each directory record, such as directories 91 and 92, has a directory identification number 107. The directory 92 has a directory identification number 29 and a name 1 Folder. In the configuration 90, the directory 92 is
Since record 92 has 10 children, %2# is assigned to the parent directory identification number of record 92. directory record 9
1 has a directory identification number 2, and its name is ``1 volume''. Since directory 91 is the root directory, it was given the parent directory identification number 111, but the number 1 indicates the foundation of the file system itself. Any of the file records 93-96 also has a key 113 and an information segment 114, with the key 113 having the parent directory identification number and its name. In the information segment 114 of file records 93 to 96, information on the location where usable file data is stored is stored, as well as the respective file number.
has storage location information of usable data. File record 94 with name 1B'' and %
File record 93 with the name A# both have a parent directory identification number of 12''.A file with a parent directory R alias number of 2 has a parent directory identification number of 2. have %
It is significant that the file with the name %C# is a direct child of the directory named "groom".
File 96 with the name ``Folder ID'' has a parent whose directory identification number is %29#, which means that the child of directory 29 named ``Folder 1'' with directory identification number 29 is the file C. and D. Therefore, when looking at the directory of any file or record key 103, it can be seen from the stored information that the name of a certain record and the directory identification number of its parent node are the same value. A route directory 102 is provided for each directory to provide relationships between different branches. The route record key has a directory identification number and a zero name, which is equivalent to having no name at all. According to the example shown in FIG. 6, the directory Hayabusa folder' and files C and D are communicated by the path record 108. Key 11 of route record 108
1 is given only the directory identification number of the directory 1 folder.Route record 108
In the information segment 112 of the folder, the directory identifier number of the parent of the folder and the name of the directory "1 field" are given. File C with the directory identifier number 29 of 6R is the immediate parent and has the directory identifier number 29. When attempting to associate with directory 92, route record 108 is %2 of directory 92.
The parent directory 920 name (folder) is used along with the directory identification number #. Similarly, route record 109 uses the name (volume) of directory 91 along with the directory identification number of parent directory 91, which has three child records 92-94. By linking directory records 91-92 and file records 93-96 with path records 108-109 for each directory, inventory structure 90 communicates with the hierarchical file system, as shown in structure 97 of FIG. Similarly, the storage location information of stored usable data is in directory records 91 to 9.
It is stored in 2. By executing the program of the inventory structure 90 using the B tree structure, the information of the hierarchical structure of structure f: 90 is stored in the leaf nodes of the B tree described above. For example, when file C is accessed by a computer, the system will perform a search of the B tree configuration. To explain the catalog example 90 shown in FIG. 6, first, when file name C is specified, a search route for this search must be specified. The path is given by the names of all directories on the path from the root record to the file, i.e. 1 volume ", followed by Hayabusa folder" and finally %C". The search is It begins by finding a directory record called ``1 Volume'' in the Inventory B tree. Since the name is volume 1 and is the root, its parent's directory identification number is 1. Searching the catalog B tree is performed for directory record 1 volume whose key is 1, that is, directory record 9.
1 can be found. The information segment then gives the directory identification number 2 for this directory. A search is then performed in the B-tree for "1 folder" whose key is 2 and which is directory record 92, and the information segment gives the directory distinguished name number 29 for this directory. is 2
This is done to find data record C which is number 9. This is a search for file records 95, whose information segments contain information about the physical location of the data contained in the desired file. Note that the file search execution specifications of the above embodiment can be started by the directory identification number of any directory on the path from the root record to the desired file, and can be started by the directory identification number of any directory on the path from the root record to the desired file. It has a directory identification name number of the directory and a series of directory names. It is clear that the search mechanism that follows this specification is a variation on what has been described above. Although the incremental catalog structure 90 is a simplified structure and FIG. 6 depicts a single structure with a single root directory 91, the catalog structure can be expanded in any number of ways. In this embodiment, one memory device such as a disk is
It uses a two-hierarchical inventory structure. However, one disk can be divided and one hierarchical catalog can be assigned to each part. The catalog record of configuration 97 in FIG. 6 is used as a data record at the leaf node 42 shown in FIG.
is stored in the . The records are inserted and stored in the Inventory B tree structure in alphanumeric numerical order. Then, when the B tree glue node moves from left to right,
Data records appear in order as shown in structure 97 of FIG. Records are stored in order according to the directory identification number portion of the key, with the highest number first. For records with the same directory identification number within a key, the alphanumeric order of the name part of the key is used. It is also recognized that other related information can be stored in records such as those described in FIG. For example, the directory and file records of the present invention store signals of the date and time of creation of the directory or file as well as the date and time of last modification. The file record also includes signals regarding file locks, elements for setting the logical and physical end of the file, file size, and the like. (File extent tree) As already mentioned, the inventory g+B regarding a specific file
A tree file record contains information about the location in the memory device where the file's data is stored. Memory devices are created as a collection of sequentially numbered blocks. A series of adjacent memory blocks is called an extent. Ideally, files are stored in a single extent with contiguous memory placement space. However, due to the size of each file as well as additions, deletions, and modifications to the current file after creation, files are typically located in more than one location in memory. Aside from small pre-located files, the contents of a particular file are typically stored in more than one location and in noncontiguous and separate extents on a volume. Each file extent can be identified by an extent descriptor. Further, complete location information for a particular file is a continuous extent list, and this list includes extent descriptors of extents that contain file data. The file extent list of the present invention also constitutes a B tree known as a file extent B tree configuration, in which volume positions and sizes of extents that shoulder files are recorded. Although most of the various memory allocation systems can use the file extent records of the present invention, one example of the memory allocation system will be described by illustrating the file extent records of this embodiment. FIG. 7 shows a memory volume 120 that is part of a memory device and uses a hard disk or the like. Volume 120 is divided into a number of logical blocks 126. Typically, each logical block 126 has a predetermined fixed number of bytes9, which in this embodiment is 512 bytes. A fixed number of logical blocks starting with block O and ending with block n are reserved by volume information. The remainder of the memory device starting with block n+1 can become data memory, and this storage is divided into installed units, each installed unit containing one or more logical blocks. The volume 120 has 121 to 12404 areas. System boot area 121 maintains certain contiguous system parameters that are well known in disk and other memory device operations. Volume information area 122 contains information regarding housekeeping parameters of the volume, such as the number and size of each installed unit. The volume bitmap 123 stores a record of each installed unit on the volume, and the bitmap indicates whether each installed unit is in use or not in use. Starting from block n+1, file content area 1
24 is up to the end of volume 120. The file content area 124 is divided into a number of installed units, each installed unit having a fixed number of logical blocks. The bitmap 123 manages volume space but does not map files. The file mapping function is provided by the file extent list. FIG. 8 shows a portion of the file content area 124 that contains information regarding a file named file E. In this example, the entire contents of file E are divided into seven extents 125-131. The first part of the file is stored in basic extent 125, and the next part is distributed into extents 2-T, labeled 126-131. File E is 1
It has seven extents ranging from 25 to 131, which are not physically adjacent. Basic extent 1 of file E to hold file extent information
Extent descriptor 140 is used for extent 25 and each of the following extents 126-131. The extent descriptor 140 has a starting installation unit number 141 and a number 142 of installation units. The extent list 135 for file E has seven extent descriptors 125a-131&, and this list provides information about the address and length of each of the extents 125-131 for file E. For example, the fourth extent 128 is the boot installation address 1.
Since the installation block length is 89 and only 2, the value 189 is set in the area 141 of the descriptor 128a, and the value 189 is set in the area 141 of the descriptor 128a.
2 has a value of 2. In the present invention, extent descriptors for all files within a volume are maintained in data records within the leaf nodes of the tree, as shown in FIGS. 3-5. This tree is known as a file extension B tree, and is a B tree different from the catalog B tree described above. Each data record of this extent B tree is
It has one key and one information segment as described above in the discussion of FIGS. 3-5. The information segment of the file extent B tree data record contains a series of extent descriptors for a particular file. The maximum number of extent descriptors in a record can be changed between executions, but is set to three in this example. The file extent B tree key has two fields, which indicate the file number of a particular file and the relative file position of the activation block of the first extent descriptor within that record. These extent records are stored in the extent nodes of the B tree, and are partitioned by previous instructions into a first file number area and a second file start block relative position. With this division, it is possible to effectively search for data position information at the relative position of a specific file within the B tree. In fact, this embodiment has a total of three extent descriptors t[, the basic and the following two, which is the information data segment 114 of the file catalog B tree record as shown at 94 in FIG. Therefore, in FIG. 8, the information segment of the catalog structure and 128&~131
Extent a is stored in the file extent B tree shown in FIG. The ability to store limited extent information within the data segments of a scrap inventory structure allows faster data access. If a file only has four or more extents, it may be necessary to examine the file extent B tree. It is of course recognized that the number of extents stored in a file's Inventory B tree record without using the file extent Blt tree' can be varied at will without departing from the scope of the claims of the present invention. FIG. 9 also shows a catalog file record 145 and file extension) B tree records 143 and 144. As mentioned in the B tree structure of the present invention, 143
and 144 have keys 148 and 149 and extent lists 146 and 147, respectively. To locate data in a particular file, first search the Catalog B tree for that file data. The file number can be determined from the information segment of this file record. Also, the first three extent descriptors in the information segment of the inventory B tree file record are examined. If the required file data is contained within the corresponding extent, then the location information is immediately useful. However, if the desired file data is in an extent other than the three extents in the file record of the inventory, the file extent is searched using the file number as the search key and the calculation result of the relative position of the file containing the desired data. ) Search with B tree. This search will yield the file extension)B tree record with the desired location information. In this embodiment, file E has 22 blocks, and the file number is equal to 20 for convenience. The extent descriptor of the catalog file record 145 of file ε has position information of the first three extents,
This extent contains the first 9 (3+5+1) file blocks. Position information for the remaining 13 blocks (2+3+1+7) of the file is contained in two data records 143 and 144 in the file extent B tree. Assume that the desired data is located in file E at file block relative location tt13. The extent descriptor in the file's inventory record is searched first. Since the relative block 13 is larger than the number of the block located in the extent descriptor in the file's 1000 list record, the file extent B tree is searched next. The key when searching for the relative block position 13 in the B tree is <20, 13>. The key number 13 is greater than the value "9" of the key 148 of the first file extent B tree record 143 of the file E, and the value of the key 149 of the second record 144 is "15".
'' Since the tree record 144 is small, the search results in 1 finding and 1 less than 6t, but the search moves on to the 2nd B tree record 144. A search for the previous record 143 with key 148 yields an extent descriptor with relative block 13. The number 9 in the key 148 indicates that the extent list 146 is the 10th relative block.

It is derived from [arrangement unit number 9]. key 149 number 1
5 is derived from the fact that the extent list 147 is the 16th relative block (location unit number 15). (Execution) Although any storage means can use the hierarchical file system, the hierarchical file system of the present invention is implemented in a computer coupled with a memory device, such as a disk, having an information capacity of several million bits. . Typically, the hierarchical file system of the present invention catalogs groups, such as data, such as files, stored on disks. In this embodiment, data storage is performed by the above-described catalog structure that catalogs data stored on a mass storage device. This configuration also stores file extent records for up to three extents for each file in the inventory. Subsequent extent information is stored in separate file extent records. Inventory records and extent records are stored using the two B-trees of the B-tree configuration described above. The hierarchical file system of this embodiment is controlled by a combination of computer system hardware and software. The control routines of the hierarchical file system are stored on a separate storage device that is different from the devices that store the available data. Although almost any storage means can be used, in this embodiment the routine is stored in read-only memory (ROM).

[Brief explanation of the drawing]

FIG. 1 is an explanatory diagram of the uniform file system of the prior art, FIG. 25A is an explanatory diagram of the hierarchical file system of the present invention, FIG. 3 is an explanatory diagram of the B tree structure of the present invention, and FIG. 4 is an explanatory diagram of the B tree structure of the present invention. An explanatory diagram of the contents of an arbitrary node of the B tree structure, FIG. 5 is an explanatory diagram of the left rotation operation of the left division of the B tree structure of this embodiment,
FIG. 6 is an explanatory diagram of the kana catalog structure of this embodiment and the configuration of the ← catalog structure in a node like a B tree, and FIG. 7 is an explanatory diagram of the allocation map volume of the file system of this embodiment. FIG. 8 is an explanatory diagram of a file extent list and file extents such as those in memory in this embodiment, and FIG. 9 is an explanatory diagram of a file extent structure in a B tree of extents and a list of extents in this embodiment. 10...Uniform file system, 11...Directory, 12-150-...File, 16...
Hierarchical file system, 17...root devictory, 31...B tree structure, 32-34...index node, 35-38...cloud/leaf node, 39...Φ...
Record, 40...Key, 41Φ...Information segment, 42...Node, 4311...Node display segment, 44...Fist record segment, 45...
・・O free space segment, No. 46・・Record branch segment, 90−・@@Inventory tree structure, 91・
@φ・root director) IJ, 92...directory,
93, 94... File, 120... Memory volume, 126... Logical block, 124...
... File content area, 125 to 131 --- Extent, 140 ... Cloudy extent descriptor,
135...--Extent list, 145...--
Catalog file record, 143.144 ...File extent B tree record. Patent applicant Apple Computer Inc.

Claims (3)

[Claims] (1) In the process of a memory device storing information,
A method of providing a computer program for cataloging said information, the method comprising: grouping said information into a number of files; having a start node, a number of end nodes, and a number of intermediate nodes. and the intermediate nodes are located at various levels after the start node and connect the end nodes to the start node, such that there is only one path from the start node to the respective end node. forming a hierarchical structure such that each end node has file location information associated with it and can provide the location information to search for its associated files; placing information in a predetermined end node; and assigning a unique value to each of said files, so that said information of a particular file is associated with said value for this file within said hierarchical configuration. A method characterized in that the search is performed by searching. (2) A method of preparing a computer program for obtaining a file system in the process of cataloging information in a file system, the method comprising: a root directory, a plurality of branch directories, and a plurality of files; forming a hierarchical node configuration such that each of the files has a single path from the root directory to the file, and the single path passes through the branch directory; assigning an identification value; assigning a unique identification name to each of the files; assigning location information of data stored in each file responsible for a group of data to be stored; A method, whereby a particular group of stored data is cataloged by its associated name within the hierarchical structure. (3) A method for preparing a computer program for building a file system, in the process of cataloging information in the file system and retrieving it from a memory device using the file system, the method comprising: It has a root directory and a number of branch directories arranged at various levels following the root directory, and has a hierarchical catalog structure in which some of the branch directories are branched from other branch directories, and connecting branch directories with a single path connecting themselves to said root directory; assigning each of said directories a unique key value to identify a group of directories; and branching said files from related directories. , structuring a number of files in said hierarchical arrangement such that each said file having a particular identification name is associated with a particular group of data stored in said memory device; providing location information to each file; providing within each directory and file the value of said key of its parent directory; and determining said single path by referencing said key value of said parent directory; determining: retrieving said particular data group by moving from a directory along each of said paths through said hierarchical structure to said each of said files, wherein said file is located at said location; supplying information, whereby the search and retrieval of the stored data is performed in a systematic and hierarchical technique.