CN101169699A - Tree-structured file system and management method thereof - Google Patents

Abstract

The invention discloses a tree-structured file system and a management method thereof, the file system is provided with (K +1) binary search trees, the node of each binary search tree comprises a logic block address field and a size field, firstly, a storage space requirement is input, and the storage space requirement comprises a required logic block address and a required cluster number. And according to the number of the required clusters, calculating a corresponding binary search tree with the number of m. And then judging whether the binary search tree with the number m has unused nodes, if so, searching the node closest to the required logic block address from the binary search tree with the number m, and removing the node closest to the required logic block address from the binary search tree with the number m.

Description

A tree structure file system and its management method

technical field

The invention relates to the technical field of file systems, in particular to a tree structure file system and a management method thereof.

Background technique

In the management of the remaining space, the best management efficiency can be obtained by using the linear algorithm of the first hit (First Hit) according to the theory. Therefore, in the actual file system, well-known file systems such as FAT, Ext2, and Ext3 all use the linear algorithm of First Hit to search for the remaining space on the storage medium. The file system first divides the space on the storage medium into several clusters or blocks, and adopts linear management for the clusters or blocks. For example, Ext2 and Ext3 file systems use bit vectors (Bit Vector) to record whether clusters have been used, and FAT file systems use file allocation tables (File Allocation Table) to record cluster usage.

However, the disadvantage of using the linear algorithm of First Hit is mainly to generate a fragmentation (Fragement) situation on the storage medium. Since the linear algorithm of First Hit uses the first remaining space in each traversal (Traverse), regardless of the size of the space, each new file record may need to perform multiple remaining space traversals, and the file record May be stored in non-contiguous spaces. And after adding files and deleting files many times, the files in the file system are often stored on the storage medium with different degrees of disconnection.

Due to the disconnection of the file, when the file is read, the required data cannot be obtained at one time, and it is often necessary to perform multiple transmissions to obtain the required data. At the same time, due to the disconnection of the file, when writing the file, multiple transmissions are required to complete the action of writing the file once.

In a storage medium with a read-write head (for example: a hard disk drive, an optical drive), the separation of the file will cause a large increase in the seek time (Seek Time) and rotation time (Rotating Time) of the read-write head, which makes the file read Write efficiency dropped drastically. In a real-time system, since the linear search time of the First Hit linear algorithm is difficult to predict, it is difficult to use a file system using the First Hit linear algorithm in a real-time system. It can be seen that there is still room for improvement in the known file system and its management method.

Contents of the invention

The object of the present invention is to provide a file system and its management method, so as to reduce the disconnection of the file system, avoid the problem of difficult maintenance of remaining space, and greatly improve the access performance of the file system.

According to the characteristics of the present invention, the present invention proposes a management method for a tree-structured file system, the file system has n clusters and (K+1) binary search trees, wherein n is an integer greater than 2, and K is a positive Integer, the (K+1) binary search trees are numbered 0, 1, 2, ..., K, each node of the binary search tree includes a logical block address field and a size field, the logical The block address is used to record the starting logical block address of the continuous available cluster corresponding to the node, and the size field is used to record the cluster number of the continuous available cluster corresponding to the node. The method includes the following steps: (A) Input A storage space requirement, the storage space requirement includes a required logical block address and a required number of clusters; (B) according to the required number of clusters, it is used to calculate a corresponding binary search tree numbered m, 0≤m ≤K; (C) judge whether there is a node in the binary search tree numbered m; (D) if it is judged in step (C) that there is a node in the binary search tree numbered m, the number m Find the nearest node from the demand logical block address in the binary search tree, and remove the nearest node from the demand logical block address from the binary search tree whose number is m; (E) if step (D The size of the continuous available clusters found in the node records found in ) is greater than the required number of clusters, and the remaining continuous available clusters after deducting the required number of clusters form a new node and add to an appropriate binary search tree; (F ) If no node can be found in the binary search tree with number m in step (D), you can find the binary search tree with number m+1 or m-1 and repeat step (C).

According to another feature of the present invention, the present invention proposes a tree structure file system, including n clusters and (K+1) binary search trees. The n clusters are used to store data, wherein n is a positive integer greater than 2; each node record of the (K+1) binary search trees corresponds to a continuous available cluster; wherein, each binary search tree Nodes are arranged according to the size of the logical block address.

Adopting the tree structure file system and its management method of the present invention, adopting the tree structure, and mixing Best Hit (Best Hit) and first hit, can reduce the phenomenon of disconnection in the file system, and can also avoid the difficulty of remaining space maintenance At the same time, the file system access performance is greatly improved, and its time complexity is also greatly reduced, which is suitable for real-time systems.

Description of drawings

Fig. 1 is the schematic diagram of tree structure file system of the present invention;

Fig. 2 is the schematic diagram of the binary search tree of the present invention;

Fig. 3 is a flow chart of the management method of the tree structure file system of the present invention;

Figure 4 is a schematic diagram of an embodiment of the present invention.

Detailed ways

1 is a schematic diagram of a tree-structured file system of the present invention, which is used in a disk drive or a flash memory to provide a file operation method (File Operation) in the disk drive or flash memory.

The tree structure file system includes n clusters (Cluster) and (K+1) binary search trees (BinarySearch Tree). The n clusters are used to store data, where n is a positive integer greater than 2. Each node of the above-mentioned binary search tree records its corresponding cluster, and K is a positive integer. Among them, each node (Node) of the binary search tree is arranged according to the size of the logical block address (Logical Block Address, LBA).

The (K+1) binary search trees are related to the cluster number n. That is, the value of K is Ceiling[log ₂ (n)], where n is the number of clusters in the tree structure file system, and Ceiling is a ceiling function.

Fig. 2 is a schematic diagram of the binary search tree of the present invention. The (K+1) binary search trees are numbered 0, 1, 2, . . . , K, and a binary search tree with number j has at most 2 ^j nodes. The number of clusters corresponding to each node of the binary search tree with the number j is $\frac{\mathrm{no}}{2^j}~\frac{\mathrm{no}}{2^{j-1}},$ j=1, 2, . . . , (K-1). The number of clusters corresponding to the nodes of the binary search tree numbered 0 is n. The number of clusters corresponding to the nodes of the binary search tree with the number K is 1.

Taking a flash memory file system with a capacity of 1 Gbyte (byte) as an example, the cluster unit is 4K bytes, so the file system has 262144 (=2 ¹⁸ ) clusters. K is 18 (that is, Ceiling(log ₂ (2 ¹⁸ ))), so there are 19 binary search trees numbered 0, 1, 2, ..., 18. The binary search tree with number 0 has at most 1 node, and the number of clusters corresponding to the nodes of the binary search tree with number 0 is 262144. The binary search tree numbered 1 has at most 2 nodes, and the number of clusters corresponding to the nodes of the binary search tree numbered 1 is 131072 (=262144/2)˜262143. By analogy, the number 18 binary search tree has a maximum of 262144 nodes, and the number of clusters corresponding to the nodes of the number 18 binary search tree is 1.

Each node of the binary search tree includes a logical block address (Logical Block Address, LBA) field and a size field. The logical block address (LBA) field is used to record the starting logical block address of the continuously available cluster corresponding to the node. The size field is used to record the number of continuously available clusters corresponding to the node.

Fig. 3 is a flow chart of the management method of the tree structure file system of the present invention. The file system has n clusters and (K+1) binary search trees, where n is a positive integer greater than 2, K is a positive integer, and the (K+1) binary search trees are numbered 0, 1, 2, ..., K. Each node of the binary search tree includes a logical block address (LBA) field and a size field, and the logical block address (LBA) is used to record the initial logical block address of the continuous available cluster corresponding to the node, The size field is used to record the number of continuously available clusters corresponding to the node. The nodes in the binary search tree labeled i record consecutively available clusters of size n/(2^i) to n/(2^(i-1)).

First, in step S205 , a storage space requirement is input, and the storage space requirement includes a required Logical Block Address (LBA) and a required cluster number s.

In step S210, initialize an index (index) i, and initialize it to 0.

In step S215 , a binary search tree corresponding to number m is calculated according to the required number of clusters s, 0≤m≤K. m is calculated according to the formula log ₂ (n)-floor(log ₂ (s))+i, where n is the number of clusters in the file system, s is the number of required clusters, and floor is the floor function.

In step S220, it is judged whether there is a node in the binary search tree with the number m, and the nodes in the binary search tree with the number m represent logical blocks of continuously available clusters.

In step S225, if it is determined in step S220 that there is a node in the binary search tree with number m, it means that there is a node suitable for the storage space requirement in the binary search tree with number m. Therefore, in the binary search tree of the number m, find the node closest to the required logical block address (LBA), and move the node closest to the required logical block address from the binary search tree of the number m remove.

Since m is calculated according to the formula log ₂ (n)-floor(log ₂ (s))+i, the size of the continuous available cluster recorded by the node in the binary search tree with the number m is greater than or equal to the number of required clusters s. When the continuous available cluster size of the node record found in step S225 is greater than the required number of clusters, the remaining continuous available clusters after deducting the required number of clusters form a new node and add to the appropriate binary search tree.

In step S230, a balancing operation is performed on the binary search tree numbered m. Since the node is removed in step S225, a balance operation needs to be performed on the binary search tree so that the number of nodes on the left and right sides of the binary search tree is as equal as possible to maintain the search speed of the binary search tree.

If it is determined in step S220 that there is no node in the binary search tree with number m, it means that there is no node suitable for the storage space requirement in the binary search tree with number m. Therefore, unused nodes are found in the upper binary search tree of the number m binary search tree. The upper-level binary search tree referred to here refers to a binary search tree with a smaller number m. First search whether there is a node in the binary search tree of the number (m-1), if there is, then find the node closest to the required logical block address (LBA) in the binary search tree of the number (m-1) ; If not, search sequentially whether there is a node in the binary search tree numbered (m-2), until the binary search tree numbered 0.

Here, there is no node suitable for the storage space requirement in the binary search tree of the number m, first find an unused node from the upper binary search tree of the binary search tree of the number m instead of the node of the number m The purpose of searching in the lower binary search tree of m's binary search tree is to avoid the situation that the storage space requirement may be divided into sub-requirements when searching from the lower layer first.

If there is still no unused node in the binary search tree numbered 0, the unused node is searched from the lower binary search tree of the binary search tree numbered m. The lower layer binary search tree referred to here refers to the binary search tree whose number is larger than m. First search whether there is an unused node in the binary search tree of the number (m+1), if there is, then find the distance from the required logical block address (LBA) in the binary search tree of the number (m+1) The nearest node; if not, then search sequentially whether there is an unused node in the binary search tree of number (m+2), until the binary search tree of number K.

In step S235, it is determined whether the index i is less than or equal to 0, if yes, step S240 is executed, if not, step S255 is executed.

Execution of step S240 means searching for unused nodes in the upper binary search tree of the number m binary search tree. Therefore, in step S240, the index i is decremented by 1. Executing step S255 means searching for unused nodes in the lower binary search tree of the number m binary search tree.

In step S245, it is judged whether the binary search tree number is greater than or equal to 0, if greater than or equal to 0, re-execute step S220, if less than 0, then execute step S250. If the binary search tree number is less than 0, it means that the search of the upper binary search tree has been executed. Therefore, step S250 is executed to find unused nodes in the lower binary search tree of the number m binary search tree. In step S245, the binary search tree number is an update number m'=log ₂ (n)-floor(log ₂ (s))+i.

In step S250, the index i is set to 0.

In step S255, 1 is added to the index i.

In step S260, it is judged whether the number of the binary search tree is greater than K, if so, it means that the search for unused nodes in the lower binary search tree of the binary search tree with the number m has been executed, so the search procedure ends. If not, execute step S220 to find unused nodes. In step S260, the binary search tree number is an update number m"=log ₂ (n)-floor(log ₂ (s))+i, and whether the binary search tree number is greater than K is to execute the following formula:

log ₂ (n)-floor(log ₂ (s))+i＞Ceiling(log ₂ (n))

Among them, n is the number of clusters in the file system, s is the number of required clusters, floor is a floor function, and Ceiling is a ceiling function.

When searching for unused nodes in the lower binary search tree, the clusters of the found nodes are smaller than the required number of clusters s. At this time, the storage space requirement needs to be divided into sub-requirements, that is, scattered nodes are used to meet the storage space requirement .

Fig. 4 is a schematic diagram of an embodiment of the present invention. In this embodiment, the capacity of a disk drive is 1G byte, and the cluster unit is 4K bytes, so the disk drive has a total of 262144 (=2 ¹⁸ ) clusters. K is 18 (=Ceiling(log ₂ (2 ¹⁸ ))), so there are 19 binary search trees numbered 0, 1, 2, . . . , 18. As shown in FIG. 3 , in this embodiment, the maximum number of concurrently existing nodes is the sum of the nodes of the above 19 binary search trees, that is, 524,287 nodes. A node represents a continuous cluster. Assuming that the addressing length is 32 bits, one node needs 8 bytes, so a total of 4096 (524287*8/512) sectors are needed to store the above nodes. Therefore, four thousandths of the storage space is required to store nodes.

In the present invention, if the file system is to find a piece of remaining space close to position a with a size of s clusters. The best situation is that there are nodes in the Floor(s/2)th tree structure. Since the maximum height of this tree structure is Floor(s/2), it only needs to perform Floor(s/2) comparisons at most. Find the appropriate node. The worst case is that there are only nodes in the Ceiling(log ₂ (n)) tree structure, because it will first check whether there are nodes in the other Ceiling(log ₂ (n))-1 tree structures, and then at the maximum height Do s traversals for the Ceiling(log ₂ (n)) tree structure of Ceiling(log ₂ (n)), so in the worst case there will be a total of [Ceiling(log ₂ (n))-1] +[Ceiling(log ₂ (n))×s] traversals.

From the above description, it can be known that when a storage medium has x clusters and it is necessary to find a remaining space of s clusters close to the position a, the known technology cannot understand the spatial separation because it uses a linear first hit search method. The degree of disconnection will inevitably increase continuously, so the time complexity of the known technology is O(x*s). Since the present invention adopts a tree structure and mixes best hit and first hit, even after a long period of operation, the degree of spatial separation can still be grasped in a simple way, so the time complexity of the present invention is O(log ₂ (x)*s). Compared with the disadvantages of long search time, high time complexity and unsuitability for real-time systems in the prior art, the present invention is more suitable for real-time systems. The present invention can reduce the phenomenon of disconnection in the file system, avoid the problem of difficult maintenance of remaining space, and greatly improve the access performance of the file system.

Of course, the present invention can also have other various embodiments, and those skilled in the art can make various corresponding changes and deformations according to the present invention without departing from the spirit and essence of the present invention, but these corresponding Changes and deformations should belong to the scope of protection of the appended claims of the present invention.

Claims (13)

1. the management method of a tree structure file system, this document system has n bunch and reaches (K+1) individual binary search tree, wherein n is the integer greater than 2, K is a positive integer, should be numbered 0 by (K+1) individual binary search tree, 1,2, ..., K, the node of each described binary search tree comprises a logical block addresses field and a size field, described logical block addresses is in order to put down in writing the corresponding continuously available bunch initial logical block addresses of this node, described size field is in order to put down in writing the corresponding continuously available bunch number of clusters order of this node, and this method comprises the following step:

(A) input one storage area demand, this storage area demand comprises a requirement logic block address and a demand number of clusters order;

(B) according to this demand number of clusters order, in order to calculate corresponding one binary search tree that is numbered m, 0≤m≤K;

(C) judge in this binary search tree that is numbered m whether node is arranged; And

(D) if judge in the step (C) in this binary search tree that is numbered m node is arranged, be numbered in the binary search tree of m by this and look for the node nearest, and will from this is numbered the binary search tree of m, remove apart from the nearest node of this requirement logic block address apart from this requirement logic block address;

(E) if the continuous available bunch size of the node representative of finding in the binary search tree that is numbered m in the step (D) greater than required number of clusters order, deduct afterwards remaining available continuously bunch another node of formation of required number of clusters order, the new corresponding binary search tree of node adding that forms.

2. management method as claimed in claim 1 is characterized in that,

In described step (E), after the new node that forms adds corresponding binary search tree, the balance computing carried out in the described binary search tree that is numbered m.

3. management method as claimed in claim 1 is characterized in that,

If judging in the step (C) in this binary search tree that is numbered m does not have untapped node, carry out the following step:

(F) this is numbered m and subtracts 1, upgrade numbering m ' to obtain one; And

(G) whether judge this renewal numbering m ' more than or equal to 0, if, execution in step (C).

4. management method as claimed in claim 3 is characterized in that,

If it is non-more than or equal to 0 to judge in the step (G) that this upgrades numbering m ', carry out the following step:

(H) will number m and add 1, to obtain incremental update numbering m ", and as this incremental update numbering m " when being not more than K, execution in step (C).

5. management method as claimed in claim 1 is characterized in that,

The K value is Ceiling[log ₂(n)], wherein, n is the number of clusters order of this tree structure file system, and Ceiling is the ceiling function.

6. management method as claimed in claim 1 is characterized in that,

This corresponding number of clusters order of each node that is numbered the binary search tree of j is $\frac{n}{2^j}~\frac{n}{2^{j-1}},$ J=1,2 ..., (K-1), this corresponding number of clusters order of node that is numbered 0 binary search tree is n, this corresponding number of clusters order of node that is numbered the binary search tree of K is 1.

7. management method as claimed in claim 1 is characterized in that,

In described step (B), described numbering m is log ₂(n)-floor (log ₂(s)), wherein n is the number of clusters order of this tree structure file system, and s is a demand number of clusters order.

8. tree structure file system comprises:

N bunch, in order to storage data, wherein n is the integer greater than 2; And

(K+1) individual binary search tree, K are positive integer, and the node of each described binary search tree is in order to write down corresponding continuously available bunch;

Wherein, the node of each described binary search tree is to arrange according to the size of logical block addresses.

9. tree structure file system as claimed in claim 8 is characterized in that,

Described K value is Ceiling[log ₂(n)], in the middle of, n is the number of clusters order of this tree structure file system, Ceiling is the ceiling function.

10. tree structure file system as claimed in claim 9 is characterized in that,

Described (K+1) individual binary search tree is numbered 0,1,2 ..., K, and this binary search tree that is numbered j has maximum 2 ^jIndividual node, j=0,1,2 ..., K.

11. tree structure file system as claimed in claim 10 is characterized in that,

This number of clusters order that is numbered each the node correspondence in the binary search tree of j is $\frac{n}{2^j}~\frac{n}{2^{j-1}},$ J=1,2 ..., (K-1), this corresponding number of clusters order of node that is numbered 0 binary search tree is n, this corresponding number of clusters order of node that is numbered the binary search tree of K is 1.

12. tree structure file system as claimed in claim 10 is characterized in that,

The node of each described binary search tree more comprises:

One logical block addresses field is in order to put down in writing the initial logical block addresses of corresponding bunch of this node; And

One size field is in order to put down in writing the number of clusters order of corresponding bunch of this node.

13. tree structure file system as claimed in claim 12 is characterized in that,

Described tree structure file system is applicable in a disc driver or the flash memory.

Images