• +1 (317) 799-6577
  • support@sharksavewriters.com
Hire Writer

Tree Structure for File and Data Allocation

 

 

 

 

Tree Structure for File and Data Allocation

Student’s Name

Institution

Abstract

The paper discusses Tree Structure as used to distribute nodes in a distributed network environment. Since each Tree is unique in its operations, the way the data is and files are allocated in the nodes varies. Such capabilities are highlighted in the paper, including the essential services performed in a Tree, that is, search, insert, delete, among others. Also covered here are the standard explanations about the terminologies of the Tree Structure like path, node, root, leaf, etcetera. The importance of Trees in file and data allocation is also explained, and why the various environments should adopt them. Such includes the multiple applications of the Tree Structure. There are various types of trees, including binary, B+ Trees, Binary Search Trees, among others, that help with the process of file allocation, all of which are also expounded on in-depth. The paper covered various files allocation techniques like Index Allocation, Linked List, and Contiguous Allocation. All the discussions are summed up by the glitches in nodes, fault tolerance, and the methods for ensuring data integrity.

Keywords: Tree, structure, file, data, allocation

Introduction

In a structured tree directory, everything is a file, including the directory themselves. Therefore, some subdirectories can contain both the files and other subdirectories. Any operations required in the directory thus affects related nodes. For example, the deletion of a directory leads to missing information that changes the functioning of other nodes. When the directory is empty, then its entry in the containing directory can be deleted without affecting other node functionality.

If the directory is not empty and it is to be deleted, some systems will hinder the operation from protecting other activities. The directory has to be empty for the system to permit it for deletion. Therefore, it is a common practice to first delete all the files and subdirectories before deleting the parent directory.

The distributed system uses specified algorithms within the data structure to store and access records, files, and data. Such algorithms include linked lists, stack, queues, graphs, searching, sorting, Tree, among others. Many systems assume the organization of a tree structure.

In a Tree-structured architecture, the computing systems include many nodes. High-speed communication networks ensure all the nodes are interconnected in the distributed environment and function independently. Since each node comprises an individual processor and operating system to interact with other nodes, they will need to adopt a transfer of blocks of data and message traffic over the communication network.

File data structures can be evenly spread throughout the entire nodes instead of being centrally focused on a single node. To achieve this in a more efficient form for all the nodes, the distributed data structures should fulfill the capacity for system recovery in cases of process or system malfunction in one or more nodes.

The allocation of files in the storage media depends on the file structure. There are three commonly known structures. First, the byte sequence, where data are stored as an unstructured sequence of bytes. The managing or accessing nodes and their operating system does not need any prior knowledge of what the file contains. Instead, all it considers are the bytes that are visible to the system. For any meaning to be derived from the files, additional user-level programs are imposed. Secondly, there is an order of records from which the files are considered as a sequence of records with a fixed length. Each record is believed to have its specific internal file structure. For a read operation, only one record is returned at a time, write operation appends or overwrites one record. Finally, the Tree, where each file is considered to be consisting of a tree of records, regardless of length, and each has a unique key to identify their position. The paper thus covers the Tree structure and how files are allocated.

In the tree architecture, a file is usually a group of records arranged in the form of a tree. The records vary in length, and each contains a key field used to locate them from the structure. Every key field is stored in a fixed position within the record. Because of the need to support rapid searching for various particular keys, the Tree assumes the organization on the key field. Trees can be binary, binary search trees, AVL trees, B tree, and B+ trees.

A Tree is a powerful and advanced form of data structure. It is recursive and contains a set of nodes. Within the structure, there is a root node found at the root of the Tree. The remaining nodes within the structure are the children belonging to the root node. Unlike arrays, stack, queue, and linked lists, trees are non-linear data structures.

Tree structure shows the representation of nodes and their connection by edges. Apart from the root, the remaining nodes assume the partition into the non-empty sets. Here each node is then referred to as a sub-tree.

The relationship between the nodes in the Tree is a parent-child relationship. There can also be sister nodes. A parent node can have many children, that is, there is no limit to the number of children existing from the root. However, every node can only have one parent node.

To better understand the Tree structure, the following terminologies are used throughout the paper.

Root Node: This is the node occupying the topmost node in the hierarchy. It does not have any parent.

Sub Tree: In some instances, the root node can be null. However, in the cases when the root node is not null, there exists sub-trees of the root node, that is, T1, T2, T3, as shown in the diagram below.

Leaf nodes: They are also referred to as external nodes. These are the nodes without any children. Their existence does not require any following nodes. They occupy the very bottom position in the tree hierarchy. Depending on the size of the Tree, there can be any desired number of named eternal nodes present in the Tree.

Path: Consecutive edges are connected through a sequence called a path. Depending on the position of any node in the structure, they can be reached through a path. In the diagram below, to reach node E, we take the path A -> B -> E

 

 

 

 

Tree Representation of nodes

Ancestor node: Any node that precedes another on the path from a root node to the target node is called an ancestor node. Therefore, only the root node does not have an ancestor. Consider the structure above. If we take node G, its ancestors are nodes D and A.

Degree: A degree of any node is the total number of its children. From the diagram, the degree of node C is 0. Similarly, all leaf nodes always have a degree of 0. Node D has a degree of 2. For a complete binary tree, each node has a degree of 2.

Level number: the level number increases as you move further from the root node. The level of each node is one step above that of their parents. Level 0 is for the root node.

Importance of Tree structure

Trees can be applied to a varied number of services. These include, but not limited to, the following:

There are various categories of trees. They include General Tree, Forests, Binary Tree, Binary Search Tree, AVL trees, B tree, and B+ trees.

General Tree

Here all the elements are stored in a hierarchical structure. The top-level is Level 0 and the root element. The following levels have accompanying numbers depending on their level in the system, which is Level 1, Level 2, etcetera. Both the siblings and parent-child relationships are adopted in this case. Also available are the subtrees and ternary Tree, that is, a tree in which every node present accommodates three subtrees.

Forest

When a general tree is disjointed such that the root node is removed, we get a forest tree. Here, all the accompanying edges that establish a sequence connection to the root node or the first level node is also removed. It is a forest since the resulting trees hang on their own without any supporting roots.

Binary Tree

When the number of nodes is limited to at most two children, we get a binary tree. The root still exists in this instance. Binary trees are common in applications such as expression evaluation.

AVL trees

AVL tree is a self-balancing Binary Search Tree (BST). For an AVL Tree, the difference between heights in the right subtree and left subtree is less than or equal to one for all the nodes.

For an AVL Tree, it takes part of the BST operations. For example, when you take 0(h), h becomes the height of the BST. When you maintain the height of the Tree at 0(Logn) after every operation, that is, insertion or deletion. This way, an upper bound of 0(Logn) is guaranteed for all the activities. Given that n represents the total number of nodes in the Tree, the height of the AVL remains 0(Logn).

Insertion

The Tree must remain AVL after every insertion operation. The standard BST insert operation is augmented to establish rebalancing in the nodes. To ensure the BST property is not violated, that is, maintained as (keys(left) < key(root) < keys(right)), the following operations are performed:

1) Left Rotation

2) Right Rotation

Implementation

A BST insert operation can be used recursively to the application of the insertion of a new AVL node. After the insertion, pointers are directed to all ancestors in the Tree, in a bottom-up approach. As a result, there is no need for a parent pointer traversing up the Tree.

Time complexity is realized in an AVL Tree structure. The right and left rotation operations utilize constant time since the pointers being changed are few. Even when updating the height of the Tree, the balance factor remains constant. With the height of the Tree being 0(Logn), the AVL tree remains balanced, and its time complexity of inserting a new node is 0(Logn). Similar scenario is witnessed whenever a deletion operation is performed on an AVL Tree.

B – Tree

This is a self-balancing search tree. The scheme assumes that every data is in the main memory.

“When the number of keys is high, the data is read from disk in the form of blocks. Disk access time is very high compared to main memory access time” (Geeks for Geeks, n.d.). B-Trees reduces the number of accesses to the disk. All the operations of the Tree Structure like insert, search, delete, etcetera require O(h) disk accesses. As discussed earlier, h represents the tree height.

B+ Tree

B+ Tree is a (key, value) storage strategy in a Tree structure. It has a root node, intermediary nodes, and a leaf node. Actual records are stored in all leaf nodes. Pointers to the leaf nodes can be found at the intermediary nodes, and they have not data at all. There can be only two leaves for any node.

To search for any record, they can only be found at the leaf nodes. This means that the search operation takes the same time due to the equidistance of the leaf nodes. Time is also utilized, and since the procedure takes the form of a sequential search, it is faster. This is also contributed by the fact that the nodes and the data in them are sorted. All the insertion and deletion operations on the nodes and records also take equivalently short time to accomplish.

The following procedures are thus achieved:

Binary Search Tree

This is derived from a Binary Tree. The difference is that in this case, the Tree is ordered. “All the elements in the left subtree are less than the root while elements present in the right sub-tree are greater than or equal to the root node element” The technique of Binary Search Trees are common in applications that support sorting and searching capabilities.

Tree structures in distributed systems attempts to eliminate the problems and delays associated with access to nodes. It therefore deploys the following techniques:

Caching: There is caching of part of the tree structure, or the entire structure in some instances. This is done on the Client node. As a result, the client is able to access the server directly to serve their requests. Assuming all nodes are functioning at optimum state, the speed of access is guaranteed. In order to improve the search for a specific server, the Client node keeps an image of cached records where the client has visited previously. For example, if in the previous search to reach the server, the client used the path from node c through node d, that part of the structure is cached by the client image. Any query from the client that addresses similar part of the keyspace in the future can then access node c, avoiding the struggle of traversing from the root to the intended server c again. In the instance where the client has only the knowledge of node d, any query will be forwarded above from node c, to next available and closest ancestor to handle the query criteria, then proceeded down to the leaf.

Replication: The upper levels of the Tree are replicated. This serves in load balancing, therefore avoiding overloading the servers handling the nodes in such levels. The whole Tree can be replicated in each present node in the structure, from the root to the leaf. So, if a client wants to access a specific server, it can send its query directly to that server and get the exact feedback intended. Applying a protocol that distributes the keys evenly to all the servers help handling the load balancing problem, especially when the entire cluster is expansive. However, this comes with the additional task of maintaining the replica of the whole structure at every node. For instance, you might find that in each request, the server sends the entire image of the Tree as a response to the client request. You end up with loads of queries which present significant overhead.

Routing table: each node stores a routing table. This enables them to navigate the Tree easily, both vertically and horizontally. Assuming that the lists of all the siblings are stored in every node, together with their accompanying keyspaces. The navigation is no longer to the parent and child axis. A search targeting node e can be initiated at node c, which then inspects its local routing table. This is followed by forwarding of the query to the sibling d. from there, there is a very short path leading to the leaf.

Tree Traversal

To access all the nodes, the Tree Traversal operation is performed. Since all the nodes are linked and connected through edges, to traverse the Tree structure you can start from the root node and access all the nodes to the leaf. Random access in a Tree is not supported. The purpose of tree traversal is to search or locate any given key or item contained in the Tree.

The following traversal operations are conducted, that is, In-order Traversal, Pre-order Traversal, and Post-order Traversal.

In-order Traversal: First, visit the left subtree recursively, then root, and finish with the right subtree recursively. The approach produces a sorted key-value logically arranged in ascending order. (D → B → E → A → F → C → G)

Pre-order Traversal: First, visit the root node, then recursively traverse the left subtree, and finish with the right subtree. (A → B → D → E → C → F → G)

Post-order Traversal: First, traverse the left subtree recursively, then right subtree, and finish with the root node, thus the naming as post-order.

File Allocation

Files are usually allocated using the File Allocation Table.

To properly allocate files, a file management operation is involved. The technique provides an abstraction mechanism for handling file activities. A file is considered as a composition of data on a disk, which can be arranged in a sequence of bytes. Since each file has a filename, its allocation on the drive is not considered by the user.

The following are handled through file management, that is, the location of the data on the disk, what sector it is stored, and how the applications can read the data. The file system handles such activities.

A file system is a technique involved in the organization and storage of computer files. They also guide in the management of the data contained in the files. As a result, they make the operations of finding and accessing the data easy and seamless. File systems also provide data access on a file server by the client nodes through a network protocol. The organization forms directory and registry operations.

File Allocation Methods

The allocation methods define how the files are stored in the disk blocks. There are three main disk space or file allocation methods. They include Contiguous Allocation, Linked Allocation, and Indexed Allocation. The methods are all aimed at achieving efficient disk space utilization and fast access to the file blocks.

Each technique has its strengths and drawbacks in their operations, as discussed below.

Contiguous Allocation

Each file holds a connected set of blocks within the disk structure. Consider the scenario where a file requires n number of blocks but is instead given access to a block c as its starting point. This means that all the blocks assigned to the file will be c, c+1, c+2, ….c+n-1. The length of the file is thus the total number of blocks required. It is, therefore, possible to calculate the blocks a file occupies from the file length and starting block address.

All contiguous file allocations have the following in their directory entry:

Advantages:

Drawbacks:

Linked List Allocation

In this approach, every file is in itself a linked list comprising of disk blocks, not necessarily connected. Provided the blocks are on the same disk, they can be scattered within the drive but still be linked. There is a pointer at the directory entry, which shows the starting and ending (optional) of the file block. For every block, there is a pointer indicating the next block in line occupied by the file. For example, consider a file containing five blocks and starts from block nine. This structure might proceed to block sixteen, then block one, block ten, then eventually block twenty-five. Since every block contains a pointer directing it to the next block, the sequence can be traced entirely. Note that the last block in the structure includes a NIL pointer. However, it is possible to use the value -1 instead of NIL. The logic is to ensure the block is different from block 0.

This scheme also provides that there is a pointer at every directory which directs to the first disk block of the file. The NIL pointer identifies an empty file. When writing to the file, the first free blocks are removed and filed with the writings. The newly written blocks are then linked to the end of the file. When reading a file, a block to block operation is adopted, where the pointers are followed.

Advantages:

Disadvantages:

Indexed Allocation

This approach involves a special block, referred to as the Index block, which holds the pointers to every block that the file occupies. The index blocks are unique for every file. The nth entry recorded at the index block contains the nth file block disk address. To get the address of the index block, consider the directory entry.

Advantages:

Drawbacks:

To resolve the drawbacks of the indexed allocation, the following mechanisms can be applied:

Linked scheme: Two or more index blocks can be linked together specifically for holding pointers. Each index block then contains an address to the next index block or a pointer

Multilevel indexing: The first level index block is designed to point to the second index block in the level. The second index block then directs it to the disk blocks for which the file occupies. Depending on the file size, the criteria can extend to more than three levels on the structure.

Combined scheme: There is a dedicated special block referred to as the information node, inode, which contains all file information, including the name, authority, size, etcetera. The remaining space in the inode stores the disk Block address, which in turn contains the actual file.

Every system poses the risk of some glitches. A glitch is a fault that is short-lived in a system. These can be transient faults, which usually corrects itself. As a result, it is difficult to troubleshoot them.

There can be slight and temporary glitches and more serious bugs. They lead to functionality breakdown in the nodes or the entire system. When the problem escalated, it can cause the failure of the system.

In many instances, the glitch can never be noticed at the time of occurrence. The effect is felt later when the data presents errors or the expected system output yields incorrect output.

Since the glitches can run for a long period without being noticed, possible effects are random program malfunctions, abnormalities in the computing resources, and hardware malfunction.

In severe cases, there might be a need for restarting the entire system or sections of the nodes to restore the normal system functioning.

Computer hardware and software manufacturers put a lot of quality checks to minimize the possibilities of glitches. The system administrators, too, enforce stringent policies and procedures during the configuration and acquisition of various node components before authorizing them for use.

However, it is virtually impossible to completely remove the possibilities of glitches in every structure, even in the tree structure for file allocation. As a result, glitches are always witnessed in the file systems.

Considering a large number of nodes in a distributed environment, accompanied by the increased number of users, numerous variables can cause a glitch.

Tree structures also come with their drawbacks. For example, when using B -Tree Structure, rebalancing the nodes in the system posses a great risk. It can make a node storing the data to fail, and in turn, the whole system can fail. The system thus must acknowledge the following aspects. First, any rebalancing or no activity at all on the different nodes in process. Secondly, identify all the nodes that were part of the rebalancing scheme. Finally, examine where the failure occurred, and from which stage during the rebalancing scheme, the failure was noticed. If the structure can establish all the highlighted facts, the failed node can be recovered easily, and the entire system rebooted to allow the faults to reconstruct themselves in a manner that ensures the rebalancing efforts are enhanced. No data should be lost during this period, and the underlying processes should be able to resume normal operations after that.

In the distributed system, possible glitches can be incorrectly configured nodes where the administrator can miss out on possible variables when assigning the necessary ports. When onboarding new users, there can also be a glitch when they are not assigned the required resources entirely. Additionally, when a user asks for clarification, due to miscommunication, there can result in incorrect instructions provided by the network administrator. Invalid data input can also result in glitches. In computing, Garbage In Garbage Out is a factor that faces everyone in various circumstances. Computer viruses and malware are also a possible cause. Such malicious can find their way in the system through unsuspicious user operations or intended harmful operation by individuals. They alter the normal operations of the nodes or expected behavior of the hardware. The programs can run for a long time, collecting user or system information without being detected. Unplanned software updates can also cause the system (operating systems) or application programs to behave unusually. Users will thus be unable to work around the programs with the expected ease. Once the updates are allowed to run completely, the programs resume normal operation. Other glitches are undetected communication errors, Trojan attacks, and hacking, among others.

To ensure data integrity, it is vital to protect the files. Since the contents of the files are valuable to the users and processes of the node and the entire system, they must be guarded against physical damage and unauthorized access. Instances that might cause physical damage are head crashes, hardware problems, power failure, extreme temperatures, dirt, etcetera. Performing regular backups is thus a practice that should be normalized. Depending on the types of access requested by a node, they can be permitted or denied. The operations that can be controlled on the files include read (to read a file), write (write a file), execute (load and execute a file or a program), append (append information at the end of a file), delete (free the space allocated to a file), update (modifying, deleting and adding data to a file), copy and cut (copy the contents of a file), and list (listing the name of the file). The creators of the files can perform all the listed operations in many cases.

Various access rights are enforced to further guard data integrity. Some of the practices are as discussed below.

Access Control

Depending on the identity of the node or the user, access to files and directories can be regulated. The approach limits those who can and how they can access the requested files. Rights can be shared among groups of users, like those in the same department. Each data is associated with a corresponding access list containing information about access levels and types of users with the rights.

Password Protection

This is also another common approach adopted to protect files from unauthorized access. There can be passwords associated with every file. Supposedly a user requests access to the directory or its data. The users are prompted for a password. Failure to which the request is denied. Problem is when certain users have access rights to many files, meaning they have to master all the related passwords. Since the passwords are changed continuously for safety measures, it becomes straining to the associated users.

File Naming

This approach depends on the inability of a node or user to have exclusive access to a file they cannot name. The standard practice is to allow users to complete access to the files created from their nodes or accounts. Because the majority of the file systems only allow limited characters for filenames, there are chances that two users can adopt similar filenames.

Names are attached, each for an individual file or directory to uniquely identify them in the node. Access rights are also granted through the filenames. Strings of at least one letter are used as legal filenames.

The advancing technologies make the systems adopt increased complexities that make them less tolerant of productivity decrease, performance degradation, and safety hazards. They have to detect and identify any suspicious activities, faults, or potential abnormalities in real-time. After that, the automatic implementation of fault-tolerant operations is adopted to avoid dangerous situations and minimize the chances of performance degradation.

 

Reference

error: Content is protected !!