Table of contents
1.
Introduction
2.
Problems
3.
Frequently Asked Questions
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

File Organisation (sequential files, indexing, B and B+ trees)

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

A database is made up of a large amount of information. In an RDBMS, the data is organized into tables, with each table containing related records. The data seems to be stored in the form of tables to the user, but it is kept in physical memory in the form of files.

A file is a grouping of linked data stored on secondary storage devices such as magnetic discs, magnetic tables, and optical discs.

Various ways for organizing files have been introduced. Based on access or selection, these specific approaches offer advantages and disadvantages. As a result, it is entirely up to the programmer to choose the appropriate file organization strategy for his needs.

A few different types of file structures are:

  • Sequential File Organization
  • Hash File Organization 
  • B+ Tree File Organization 
  • Clustered File Organization 

Refer to this link to learn more about File Structure.

Problems

Now, we will see gate questions on File Structures with their solutions and explanations.

  1. The directory can be thought of as a _________ Mechanism that converts filenames into directory entries.

    a. Symbol table
    b. Cache
    c. Swap space
    d. Partition

    Ans: a

    Explanation: The directory can be a symbol table that converts filenames into directory entries. Compilers construct and maintain symbol tables to record information about the presence of various entities such as variable names, function names, objects, classes, and interfaces, among other things. 
     
  2. In a Hierarchical database, a hashing function is used to locate the _______ ?

    a. Collision
    b. Root
    c. Foreign Key
    d. Records

    Ans: b

    Explanation: A hashing function is used to locate the root in a hierarchical database.
     
  3. A block can contain either three records or ten key pointers. How many blocks do we need to hold the data file and the dense index in a database with n records?

    a. 13n/30
    b. n/3
    c. n/10
    d. n/30

    Ans: a

    Explanation: To store a data file containing n records, the number of blocks required is n/3. The number of blocks required to store a thick file index equals n/10. The total number of blocks required is n/3 + n/10 = 13n/30. Option (A) is the correct answer.
     
  4. Which of the following file structure file keys are inserted into the record locations using a formula which transforms a file key into a record location?

    a. Hashed file
    b. B-Tree file
    c. Indexed file
    d. Sequential file

    Ans: a

    Explanation: Using a formula or the hash key, file keys are inserted into record locations in Hashed files. The position of each of these file keys can subsequently be recovered using this formula. Option (A) is the correct answer.
     
  5. Which of the following is provided by the Embedded pointer?

    a. a secondary access path
    b. a physical record key
    c. an inverted index
    d. a prime key

    Ans: a
     
  6. The index allocation strategy of blocks determines the maximum allowable size of a file to a file:

    a. The size of the blocks, as well as the size of the blocks' address
    b. The size of the blocks and the number of blocks utilized for the index
    c. The size of the blocks and the number of blocks utilized for the index, and the size of the block addresses are all factors to consider.
    d. None of these

    Ans: b

    Explanation: An index block maintains the address of all the blocks assigned to a file under the index allocation method. When indexes are formed, the maximum number of blocks that can be assigned to a file is determined by the index size, which specifies how many blocks can be present and the size of each block.
     
  7. The ordering of data records in a file is the same as or very near to ordering data entries in some index. The index is then referred to as

    a. Dense
    b. Sparse
    c. Clustered
    d. Unclustered

    Ans: c

    Explanation: The data blocks in a Clustered Index are stored in a form that matches the index. As a result, each database table can only have one clustered index.
     
  8. The maximum number of keys that may be handled in each non-leaf node of a B+ tree is ________, if the search-key value is 12 bytes long, the block size is 1024 bytes, and the block pointer is 6 bytes.

    a. 57
    b. 54
    c. 58
    d. 56

    Ans: d

    Explanation:  Let m be the B+ tree's order, m(6)+ (m-1) 12 <= 1024. [Note that non-leaf nodes do not require a record pointer.] m <= 57.56, which means m = 57. The maximum number of keys is 56 because the maximum order is 57. Option (D) is the right answer.
     
  9. A trigger is

    a. A Statement that enables to start any DBMS
    b. The condition that the system checks for the database user's validity. 
    c. A statement executed by the user when debugging an application program
    d. A statement is executed automatically by the system due to a database alteration.

    Ans: d
     
  10. Block-level striping with double distributed parity is provided by which RAID level?

    a. RAID 10
    b. RAID 2
    c. RAID 6
    d. RAID 5

    Ans: c

We will close the article now with faqs since you get some idea of the gate questions of the file structures.

Frequently Asked Questions

  1. What does it mean to organize files in sequential order?
    Each record in a file has a data attribute that uniquely identifies it. Based on the unique key field or search key, records are stored in the file in consecutive order. However, physically storing all records in a sequential order is unfeasible. This method is simple in design and efficient for large amounts of data.
  2. What is a BST (Binary Search Tree), and how does it work?
    A BST is a sort of tree in which the values at the parent's left node must be smaller than the parent node's value, and the value at the parent's right node must be greater than the parent node's value. This rule is applied to the tree's left and right subtrees of the tree's root recursively.
  3. What is the Hash file system?
    The computation of the hash function on some fields of the records is used by Hash File Organization. The output of the hash function defines the position of the disc block where the records will be stored.
  4. What are the types of file operations?
    The following are the two types of file operations:
    1. Insertions, updates, and deletions are used in update operations to change the data values.
    2. Data retrieval - this process does not change the data. After filtering, it simply retrieves them.
  5. What are the advantages of using a heap file system?
    The following are some advantages of heap file organization: 
    1. In the case of a small database, fetching and retrieving records is faster than sequential records.
    2. When a large amount of data needs to be imported into the database simultaneously, this method is appropriate.

Conclusion

This article extensively discussed various GATE questions on File Structures. This article covers the solution and explanation of these GATE questions.

Refer to this link to learn more about the File Structures in detail.
Check out this problem - Largest BST In Binary Tree

We hope that this blog helped you improve your knowledge regarding the Application layer, and in case you like to learn more, check our articles in the code studio library. Do upvote our blog to help other ninjas grow. Happy Coding!

Live masterclass