File System Practice Questions

S1: A hash index must be a dense index Status: True Reason: Every unique search-key value requires a corresponding entry in the hash table to be located by the hash function. By definition, an index that tracks every search-key value is a dense index . S2: A B+ tree index can be a sparse index Status: True Reason: While B+ trees are often dense, they can be sparse when acting as a primary (clustering) index. In this mode, they only store entries for a subset of keys (usually one per data block), which helps minimize index size. so option A is correct

For scan operations (reading a large portion or all of the data), different file organizations have varying I/O efficiencies.
(a) Heap file: Data is stored in no particular order. A full scan requires reading all pages, which is inefficient if specific ordering is needed.
(b) Sorted file: Records are stored in a specific order (e.g., by a key). This is highly efficient for range queries and full scans if the scan order matches the sort order, as pages can be read sequentially.
(c) Unclustered hash index: Data is distributed based on a hash function. Scanning by key range is very inefficient as it requires accessing many random pages.
(d) Unclustered tree index: The index itself is ordered, but the data records are not physically ordered on disk. Scanning a large portion of data via an unclustered index often involves many random disk I/Os, which is less efficient than a physically sorted file.
Therefore, a sorted file organization is most I/O efficient for scan operations.
===END_Q26===

First, calculate the number of records per data block. Given a block size of 1024 bytes and a record size of 100 bytes, the block factor for the data file is $\lfloor (1024 - 0) / 100 \rfloor = 10$ records per block.
Next, determine the total number of data blocks. With 25,000 records and 10 records per block, the number of data blocks is $\lceil 25000 / 10 \rceil = 2500$ blocks.
Now, calculate the number of index entries per index block. An index entry consists of a primary key (15 bytes) and a block pointer (5 bytes), totaling $15 + 5 = 20$ bytes. The block factor for the index file is $\lfloor (1024 - 0) / 20 \rfloor = 51$ entries per block.
The number of index blocks at the first level is $\lceil 2500 / 51 \rceil = 49$ blocks.
Finally, for binary search on the index file, the number of block accesses required is $\lceil \log_2(\text{number of index blocks}) \rceil$. For 49 index blocks, this is $\lceil \log_2 49 \rceil = \lceil 5.61 \rceil = 6$ block accesses.

In a linear list based directory, to successfully create a new file, the entire directory must be scanned to ensure the new file name is unique. Similarly, for renaming an existing file, the directory must be scanned to find the file and then again to confirm the uniqueness of the new name. Opening or deleting a file might find the entry earlier, not necessarily requiring a full scan for success.

Given:
Number of student records = 1,50,000.
Block size = 4096 bytes.
Record pointer size = 7 bytes.
ANum size = 12 bytes.
Index file records consist of (ANum value, record pointer).
Size of one index entry = ANum size + Record pointer size = 12 + 7 = 19 bytes.

Block factor for index file = $\lfloor \frac{\text{Block size}}{\text{Size of one index entry}} \rfloor = \lfloor \frac{4096}{19} \rfloor = \lfloor 215.57 \rfloor = 215$ entries/block.

Number of blocks in the index file = $\lceil \frac{\text{Number of student records}}{\text{Block factor for index file}} \rceil = \lceil \frac{150000}{215} \rceil = \lceil 697.67 \rceil = 698$ blocks.

To find the minimum disk accesses, first determine the B+ tree order $p$ and leaf node capacity $k$:
For internal nodes, $p \cdot 8 + (p-1) \cdot 12 \le 4096 \implies 20p \le 4108 \implies p = 205$.
For leaf nodes, $k \cdot (8 + 12) + 8 \le 4096 \implies 20k \le 4088 \implies k = 204$.
The number of levels $h$ for $N=10^6$ records is given by $N \le p^{h-1} \cdot k$:
$1,000,000 \le 205^{h-1} \cdot 204 \implies 4901.96 \le 205^{h-1}$.
Since $205^1 < 4901.96$ and $205^2 > 4901.96$, we require $h-1 = 2$, so $h = 3$.
Retrieving a record requires 3 index level accesses plus 1 disk access to the record itself.
Total disk accesses = $3 + 1 = 4$.

[CORRECT_OPTION: 4]

In a $B^+$ tree structure, pointers to actual data records are stored only in the leaf nodes. The non-leaf (internal) nodes contain only key values and pointers to other child nodes in the tree. These pointers in non-leaf nodes are used to navigate the tree structure to find the correct leaf node. Therefore, the statement that non-leaf nodes have pointers to data records is incorrect.

Given the number of records $N = 1,000,000$ and the order of the B+ tree $M = 100$, we calculate the tree height.
The average branching factor for a B+ tree is approximately $M/2 = 50$.
The capacity $C$ for a tree of height $h$ is estimated by $C \approx (M/2)^{h-1} \times M$.
For $h=3$, $C \approx 50^2 \times 100 = 250,000$, which is less than $1,000,000$.
For $h=4$, $C \approx 50^3 \times 100 = 12,500,000$, which is sufficient to store $1,000,000$ records.
Thus, in the worst case, the tree must have a height of 4, requiring 4 node accesses to reach the leaf.

A dense index structure $I$ contains an entry for every search key value present in the database file.
Primary and clustered indexes are typically sparse, maintaining only one entry per data block to minimize overhead.
Conversely, a secondary index is built on non-ordering attributes, meaning the data file is not sorted by that search key.
Because every record must be retrievable regardless of physical order, the index $I$ must map every unique search key value explicitly to its record pointer.
Therefore, a secondary index is fundamentally a dense index.

In a $4$-level B-Tree, an insertion into a full leaf node ($Level \ 4$) triggers a chain reaction of splits if all ancestors are also full. The leaf node splits, creating $1$ new node. This split propagates to the parent ($Level \ 3$), grandparent ($Level \ 2$), and the root ($Level \ 1$), creating $1$ new node for each of these three levels. When the root node itself splits, an additional new root node must be created to hold the promoted key, adding $1$ more node. Therefore, the total number of newly created nodes is $1 (\text{leaf}) + 1 (\text{Level } 3) + 1 (\text{Level } 2) + 1 (\text{Level } 1) + 1 (\text{new root}) = 5$.

In a $B^{+}$ tree of order $n$, each index node contains at most $n$ block pointers and $n-1$ search-key values. Given the block pointer size $P = 2$ bytes, the search-key size $S = 8$ bytes, and the block size $B = 512$ bytes, we must satisfy the storage constraint:
$n \cdot P + (n-1) \cdot S \le B$
Substituting the given values into the inequality:
$n(2) + (n-1)(8) \le 512$
$2n + 8n - 8 \le 512$
$10n \le 520 \implies n \le 52$
Thus, the maximum order of the $B^{+}$ tree is 52.

[CORRECT_OPTION: 52]

RAID 5 implements block-level striping where parity data is rotated across all drives in the array rather than being stored on a single dedicated disk. This configuration avoids the performance bottleneck associated with dedicated parity drives (as seen in RAID 4). While RAID 6 utilizes double parity and RAID 2 employs Hamming code parity, RAID 5 is specifically defined by its use of distributed parity, which enhances both read performance and fault tolerance.

To calculate the order $n$ of the leaf node in a $B^+$-tree, we must satisfy the condition that the total size of all entries plus the pointer to the next leaf node does not exceed the block size. Each entry consists of a value ($9$ bytes) and a data record pointer ($7$ bytes), totaling $16$ bytes per pair. Let $P_b = 6$ bytes be the size of the pointer to the next leaf node.

The inequality is given by:
$n \times (9 + 7) + 6 \le 1024$
$16n + 6 \le 1024$
$16n \le 1018$
$n \le \frac{1018}{16} = 63.625$
Since $n$ must be an integer, the maximum order is $n = 63$.

A clustering index is built on a data file that is physically sorted (ordered) based on the values of a specific field. Since the records are physically arranged according to this field, it is classified as an "ordering" field. Unlike a primary index, which requires a unique primary key, a clustering index is typically defined on a non-unique attribute, referred to as a "non-key" field, to facilitate efficient range queries or grouping. Therefore, a clustering index is defined on fields that are both non-key and ordering.

A clustered index is a special type of index that reorders the way records in the table are physically stored on disk. Because the data rows themselves are stored in a specific order, there can be only one clustered index per table. This is in contrast to a non-clustered index, which has a separate structure from the data rows that points back to them.

In a B+ tree, a non-leaf node with $k$ keys contains $k+1$ block pointers. The total size of the keys and pointers must not exceed the block size.
Given: key size = 12 bytes, block pointer size = 8 bytes, block size = 1024 bytes.
The inequality is:
$k \times (\text{key size}) + (k+1) \times (\text{block pointer size}) \le \text{block size}$
$12k + 8(k+1) \le 1024$
$12k + 8k + 8 \le 1024$
$20k \le 1016$
$k \le 50.8$
Since the number of keys must be an integer, the maximum number of keys is 50.

The data file consists of $n$ records, and since each block holds 3 records, the number of blocks required for the data file is $\frac{n}{3}$.
A dense index requires one pointer for every record; with $n$ records, we have $n$ pointers.
Since each block holds 10 key pointers, the number of blocks required for the dense index is $\frac{n}{10}$.
To find the total number of blocks, we sum the blocks for the data file and the dense index:
Total blocks = $\frac{n}{3} + \frac{n}{10} = \frac{10n + 3n}{30} = \frac{13n}{30}$.

The system manages $2^{16} = 65,536$ unique files.
Each user requires 1 bit for 'read' and 1 bit for 'write' access per file, totaling 2 bits per file.
The total memory required for one user is $65,536 \text{ files} \times 2 \text{ bits/file} = 131,072 \text{ bits}$.
Converting this value to bytes yields $\frac{131,072 \text{ bits}}{8 \text{ bits/byte}} = 16,384 \text{ bytes}$.
Finally, converting to kilobytes, we get $\frac{16,384 \text{ bytes}}{1,024 \text{ bytes/KB}} = 16 \text{ KB}$.

The process of mapping a file key $K$ to a physical storage location $A$ via a mathematical transformation is known as hashing. Specifically, a hash function $h(K) = A$ is applied to compute the direct address of the record. Unlike indexed files that use auxiliary search structures, or B-trees that use balanced hierarchical structures, hashed files provide direct access by calculating the location formulaically. Sequential files simply store records in consecutive order without requiring a transformation formula. Therefore, this specific mechanism is the defining characteristic of a hashed file.