File System Practice Questions

For non-leaf nodes of order $P$, the constraint is $P \times B_p + (P - 1) \times K \le S$.
Substituting given values: $P \times 8 + (P - 1) \times 12 \le 1024$, which simplifies to $20P \le 1036$, yielding $P = 51$.
For leaf nodes of order $P_{leaf}$, the constraint is $P_{leaf} \times (K + R) + B_p \le S$.
Substituting given values: $P_{leaf} \times (12 + 10) + 8 \le 1024$, which simplifies to $22P_{leaf} \le 1016$, yielding $P_{leaf} = 46$.
Therefore, the values are $P_{leaf} = 46$ and $P = 51$.

The entry size of the secondary index is the sum of the key field size ($6$ bytes) and the pointer size ($10$ bytes), totaling $E = 16$ bytes. The number of index entries per block is $\lfloor 1024 / 16 \rfloor = 64$. For the first-level index, the number of blocks required for $16384$ records is $N_1 = \lceil 16384 / 64 \rceil = 256$ blocks. For the second-level index, we index the $256$ blocks of the first level, requiring $N_2 = \lceil 256 / 64 \rceil = 4$ blocks. Thus, the number of first-level and second-level blocks are $256$ and $4$, respectively.

A leaf node in a B+ tree stores $N$ (value, data record pointer) pairs and one block pointer to the next leaf node. The total size must fit within the block size.

Given:
Block size = $1024$ bytes
Data record pointer ($D$) = $7$ bytes
Value field ($V$) = $9$ bytes
Block pointer ($P$) = $6$ bytes

The space occupied by $N$ pairs and one next-leaf pointer is:
$N \times (V + D) + P \le \text{Block Size}$
Substituting the given values:
$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 number of pairs is $63$.

For $x = 5000$, all tuples in the Paid relation satisfy $amount > 5000$ since the amounts are $6000, 7000, 8000, 9000,$ and $10000$.
Plan 1 applies the selection $amount > x$ on the $N$ student records before the join, requiring $N$ filter operations.
Plan 2 performs the join first and then applies the selection on the resulting $M$ tuples, where $M$ is the total number of enrollments ($M \ge N$).
Since the filter operation takes $10 \, \mu\text{s}$ per tuple, Plan 1 performs $10N \, \mu\text{s}$ worth of selection work, while Plan 2 performs $10M \, \mu\text{s}$.
Because $M \ge N$, Plan 1 executes fewer filter operations and is therefore faster for all databases.

In a B+ tree non-leaf node of order $p$, there are $p$ block pointers and $p-1$ search keys. The constraint on the block size is given by the equation:
$p \times (\text{block pointer size}) + (p-1) \times (\text{search key size}) \le \text{block size}$
Substituting the given values (ignoring the record pointer, as it only appears in leaf nodes):
$p \times 6 + (p-1) \times 9 \le 512$
$6p + 9p - 9 \le 512 \implies 15p \le 521$
$p \le \frac{521}{15} \approx 34.73$
Thus, the largest possible order $p$ is $34$.

The cost of a Tuple Nested-Loop Join is given by the formula $Cost = B_{outer} + (N_{outer} \times B_{inner})$, where $B$ is the number of blocks and $N$ is the number of records.
For $T_1$ (2000 records, 80 blocks) as the outer loop: $Cost = 80 + (2000 \times 20) = 40080$ block accesses.
For $T_2$ (400 records, 20 blocks) as the outer loop: $Cost = 20 + (400 \times 80) = 32020$ block accesses.
To minimize the number of block accesses, we choose $T_2$ as the outer loop, yielding $32020$ total accesses.

For a file size $F$ and block size $S$, the number of data blocks is $N = \lceil F/S \rceil$. Since bookkeeping takes 4 bytes per data block, the total bookkeeping requirement is $4N$ bytes, needing $K = \lceil 4N/S \rceil$ additional blocks, making the total space $(N + K) \times S$.

For $S = 100$:

• 11050: $(111 + \lceil 444/100 \rceil) \times 100 = 11600$; 4990: $(50 + \lceil 200/100 \rceil) \times 100 = 5200$;
• 5170: $(52 + \lceil 208/100 \rceil) \times 100 = 5500$; 12640: $(127 + \lceil 508/100 \rceil) \times 100 = 13300$;
• Total space $= 11600 + 5200 + 5500 + 13300 = 35600$ bytes.

For $S = 200$:

• 11050: $(56 + \lceil 224/200 \rceil) \times 200 = 11600$; 4990: $(25 + \lceil 100/200 \rceil) \times 200 = 5200$;
• 5170: $(26 + \lceil 104/200 \rceil) \times 200 = 5400$; 12640: $(64 + \lceil 256/200 \rceil) \times 200 = 13200$;
• Total space $= 11600 + 5200 + 5400 + 13200 = 35400$ bytes.

To minimize the number of block accesses, we select the smaller table ($T_2$) as the outer loop table.

The cost for Nested-Loop Join (NLJ) is:
$C_{NLJ} = B_{outer} + (R_{outer} \times B_{inner}) = 20 + (400 \times 80) = 32020$

The cost for Block Nested-Loop Join (BNLJ) with $M=1$ block available for the outer relation is:
$C_{BNLJ} = B_{outer} + \left( \frac{B_{outer}}{M} \times B_{inner} \right) = 20 + \left( \frac{20}{1} \times 80 \right) = 20 + 1600 = 1620$

The reduction in block accesses is:
$\Delta = C_{NLJ} - C_{BNLJ} = 32020 - 1620 = 30400$

Database storage relies on disk I/O, which operates on fixed-size blocks. Binary search trees have a fan-out of $2$, forcing a new disk access for each node traversal, resulting in $O(\log_2 N)$ disk reads. Conversely, $B^{+}$-trees are designed with a high fan-out, allowing many keys to be stored within a single disk block. This structure significantly reduces the total number of disk accesses required to navigate the index and retrieve data. Thus, the block-based transfer mechanism of secondary storage is the fundamental reason for preferring $B^{+}$-trees over binary search trees.

A B-tree node of order $p$ contains $p$ block pointers ($P_B$) and $p-1$ entries, where each entry consists of a key ($K$) and a data pointer ($P_D$). The size constraint for a single block is:
$p \cdot P_B + (p-1) \cdot (K + P_D) \leq B$
Substituting the given values $P_B = 5$, $K = 10$, $P_D = 8$, and $B = 512$:
$5p + (p-1)(10 + 8) \leq 512$
$5p + 18(p-1) \leq 512 \implies 23p - 18 \leq 512$
$23p \leq 530 \implies p \leq \frac{530}{23} \approx 23.04$
Since $p$ must be an integer, the maximum value is $p = 23$.

For an internal node of order $p$, we require $p$ child pointers and $p-1$ search field values to fit within the block size.
Substituting the provided sizes, the inequality is $p \times 6 + (p-1) \times 14 \leq 512$.
Expanding this gives $6p + 14p - 14 \leq 512$, which simplifies to $20p \leq 526$.
Solving for $p$ yields $p \leq \frac{526}{20} = 26.3$.
As $p$ must be an integer, the maximum valid order is $26$.

For a B+-tree node, the capacity constraint is defined by the number of pointers $n$ and keys $(n-1)$, such that the total size fits within a disk block $B$: $n \times P + (n-1) \times K \le B$.
Substituting the given values ($P = 4$, $K = 8$, $B = 512$):
$4n + 8(n-1) \le 512$
$4n + 8n - 8 \le 512$
$12n \le 520 \implies n \le \frac{520}{12} \approx 43.33$
Since $n$ must be an integer, the maximum valid degree is 43.

In an index allocation scheme, the index blocks store pointers to data blocks. The number of pointers that can be stored in a single index block is given by $\frac{\text{Block Size}}{\text{Address Size}}$. The total number of addressable data blocks is determined by the total capacity of the index structure, which is derived from the number of blocks used for the index, the capacity of each block (\text{Block Size}$), and the size of each pointer (\text{Address Size}$). Since the maximum file size is the product of the number of addressable data blocks and the $\text{Block Size}$, it depends on all three parameters: the $\text{Block Size}$, the $\text{Address Size}$, and the number of blocks used for the index.

Databases reside on disks, which have significantly higher access latency compared to RAM. B$^{+}$-trees utilize a high branching factor (order $M$), resulting in a shallow tree height $h \approx \log_{M}(N)$, which minimizes the number of disk I/O operations required to locate a record. In contrast, binary trees have a height of $h \approx \log_{2}(N)$, necessitating far more disk accesses. Because disk access latency is the primary performance bottleneck in database systems, minimizing the number of disk seeks is crucial. Therefore, B$^{+}$-trees are preferred because they mitigate the performance cost of slow disk access.

To determine the index source, we examine the alphabetical order of the values in each field. For the "Occupation" column, the values are CON (Row 1), ENG (Row 2), DOC (Row 3), SER (Row 4), and MUS (Row 5).
Sorting these alphabetically gives:

1. CON (Row $1$)
2. DOC (Row $3$)
3. ENG (Row $2$)
4. MUS (Row $5$)
5. SER (Row $4$)
   This yields the sequence of row indices $1, 3, 2, 5, 4$, which matches the provided index file exactly.

Maximum keys per leaf = 7. 8192 records ⟹ ceil(8192/7) = 1171 leaf nodes. Each internal node has max 8 pointers. Level 1 (Leaves): 1171 nodes. Level 2 (Internal): ceil(1171/8) = 147 nodes. Level 3 (Internal): ceil(147/8) = 19 nodes. Level 4 (Internal): ceil(19/8) = 3 nodes. Level 5 (Root): ceil(3/8) = 1 node. Total levels = 5.

(A) If a sibling has extra entries, redistribution (borrowing) avoids a merge. (B) If redistribution is not possible, the leaf merges with a sibling. (C) After a merge, the corresponding separator key is removed from the parent, possibly causing the parent to underflow recursively. (D) The secondary index deletion is independent of the data file - the record may still be in the file. (E) The data file is never re-sorted due to secondary index operations.

In a standard Extendible Hashing system, the relationship between Global Depth ($gd$), Local Depth ($ld$), and the number of directory entries is absolute.The Standard RuleThe number of directory pointers for any bucket $i$ is defined by:$\text{Pointers} = 2^{(gd - ld_i)}$Using this rule, we can solve for the Local Depth ($ld$):$ld_i = gd - \log_2(\text{Number of Pointers})$Step-by-Step Calculation (The Academic Way)Given the Global Depth $gd = 3$, let's count the actual pointers \in the directory provided:BucketDirectory Entries Pointing to ItPointer CountB1000, 0102B2001, 0112B3100, 1012B4110, 1112Applying the math to each bucket:For B1: $ld = 3 - \log_2(2) = 3 - 1 = \mathbf{2}$For B2: $ld = 3 - \log_2(2) = 3 - 1 = \mathbf{2}$For B3: $ld = 3 - \log_2(2) = 3 - 1 = \mathbf{2}$For B4: $ld = 3 - \log_2(2) = 3 - 1 = \mathbf{2}$