L31_Ch12b

Chapter 12 File Management (Part B: Sections 12.3-12.5)

Page 1: Overview

• Focuses on file management concepts and structures.

• Sections covered: B-Trees and file directory management.

Page 2: Prerequisites for Section 12.3

• Assumes prior knowledge of Tree Data Structures.

  • Essential terms:

    • Nodes, Branches, Parent nodes, Children nodes, Sibling nodes, Root node, Leaf nodes, Inner nodes.

    • Concepts of Breadth and Depth.

    • Importance of trees being cycle-free.

• Reference: Section 12.5 of the 1st-Semester COS151 textbook for foundational understanding.

Page 3: B-Trees

• Definition:

  • A balanced tree data structure with all branches of equal length.

• Characteristics:

  • Standard structure for organizing indices.

  • Widely employed in Operating System (OS) file systems for indexing.

  • Facilitates efficient operations: searching, adding, and deleting items.

• Advice to consult Study-Year 2: Algorithms and Data Structures for deeper insights on B-Trees.

Page 4: B-Tree Characteristics

• Node Structure:

  • A node can contain at most 2d - 1 keys and 2d children (or pointers).

  • Except for the root, every node must have at least d - 1 keys and d pointers.

  • Internal nodes (excluding root) at least half full, must have a minimum of d children.

  • The root node must have a minimum of 1 key and 2 children.

  • All leaf nodes are at the same level and do not contain any information.

  • Nonleaf node with k pointers contains k - 1 keys.

Page 5: B-Tree Node Structure

• Structure of a B-Tree Node:

  • Displays keys in sorted order: Key1 < Key3 < ... < Keyk-1.

  • Subtrees rooted at each key to maintain order and branching.

Page 6: Inserting Nodes into a B-Tree

• Inserting Nodes Dynamics:

  • Different types of insertions:

    • Simple insertion within a node (e.g., Key = 90).

    • Node splitting when necessary, promoting a key to the root (e.g., Key = 45 and Key = 84).

  • Demonstrates dynamic changes in node structure as keys are added.

  • Example: B-tree of minimum degree d = 3 with varying keys listed.

Page 7: File Directory Elements (Table 12.1)

• Basic Information Components:

  • File Name: Unique identifier for the file within a directory.

  • File Type: Categories such as text, binary, etc.

  • File Organization: Specifies structure based on system capabilities.

• Address Information:

  • Volume: Indicates storage device.

  • Starting Address: Physical location in secondary storage.

  • Size Used: Current file size.

  • Size Allocated: Maximum file size duration.

• Access Control Information:

  • Owner: User with control, can modify access.

  • Access Information: Includes names/passwords for access rights.

  • Permitted Actions: Control over read, write, execute permissions.

• Usage Information:

  • Tracks file creation, modification, and access dates and activities.

Page 8: Operations on File Directory

• Types of operations that can be performed on a directory:

  • Search

  • Create files

  • Delete files

  • List directory contents

  • Update directory

Page 9: Two-Level Directory Scheme

• Structure Overview:

  • Each user has a dedicated directory.

  • Master directory listing all user directories:

    • Contains addresses and access control info for each user.

  • User directories display files owned by that user.

  • Unique names enforced only within individual user’s collection.

Page 10: Directory Internal Structure

• Visual representation:

  • Describes how each directory can have its structure with master and user directories.

  • Illustrates hierarchical data organization.

Page 11: Tree-Structured Directory Example

• Depicts a tree structure of directories and subdirectories:

  • Example of how a file's pathname is structured (e.g., /User_B/Word/Unit_A/ABC).

  • Shows nested relationship among directories.

Page 12: File Sharing Considerations

• Two main issues for file sharing:

  • Access Rights: Specification of permissions for users.

  • Management of Simultaneous Access: Coordinating multiple users interacting with files.

Page 13: Access Rights

• Different levels of access rights include:

  • None: No access to directory.

  • Knowledge: Awareness of file existence; can request access.

  • Execution: Can run programs, cannot copy.

  • Reading: Full reading capability of files.

  • Appending: Can add data but not modify existing content.

  • Updating: Can modify and delete data.

  • Changing Protection: Can alter access rights for others.

  • Deletion: Can remove the file from the system.

Page 14: User Access Rights Types

• Owner: Completes full control and rights.

• Specific Users: Designated users with defined rights.

• User Groups: Defined groups sharing access rights.

• All Users: Public access to files.

• Consideration: Potential risks if ownership rights are misallocated to other users.