Tree-structure file system and its managerial approach

Abstract

The invention discloses a tree structure file system and a management method thereof. The file system has (K+1) binary search trees, wherein the node of each binary search tree contains a logical block address field and a size field. The management method comprises firstly inputting a memory space demand including a demanded logic block address and a demanded cluster number; computing a binary search tree with the code m according to the number of the demanded cluster; and determining whether the binary tree with the code m has unused node, if the binary tree with the code m has the unused node, searching the node nearest to the demanded logic block address in the binary search tree with the code m, and removing the node nearest to the demanded logic block address from the binary search tree with the code m.

Description

technical field [0001] 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 [0002] 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, the Ext2 and Ext3 file systems use bit vectors (Bit Vector) to record whether clusters have been used, and the FAT file system uses a file allocation table (File Allocation Table) to record cluster usage. [0003] However, the disadvantage of using the linear algori...

AI Technical Summary

Problems solved by technology

[0005] In a storage medium with a read-write head (for example: hard disk drive, optical drive), the disconnection of the file will cause a large increase in the seek time (Seek Time) and rotation time (Rotating Time) of the read-write head, making the file read Write efficiency drops sharply

In a real-time system, since the linear search time of the First Hit linear algorithm is difficult to predict, the file system using the First Hit linear algorithm is difficult to use in a real-time system

It can be seen that there is still room for improvement in known file systems and their management methods

Images