File System Practice Questions

When local depth equals global depth and the bucket overflows, the directory must first be doubled (global depth incremented by 1, directory size doubled). Then the overflowing bucket is split: its local depth is incremented to the new global depth, keys are redistributed, and the two new directory halves are updated to point to the two resulting buckets.

If the directory is small enough to fit in main memory (common assumption in GATE), searching requires: (1) Compute hash, (2) Look up directory in memory to get bucket pointer - 0 disk accesses, (3) Read the bucket from disk - 1 disk access. Total = 1 disk access. If the directory does NOT fit in memory, it's 2 disk accesses (1 for directory page + 1 for bucket).

Inserting 6 keys into a B+ tree of order 3: leaf nodes hold at most 2 keys. After splits, we get 3 leaf nodes at level 1 and a root at level 0 with 2 keys, giving height = 2 (counting from root=0).

Height of B+ tree = ceil(log_{50}(200000)) (using minimum fan-out 50). log_50(200000) ≈ log(200000)/log(50) ≈ 5.3/1.699 ≈ 3.12 → height = 4 levels. Block accesses = height + 1 (for data block) = 4 + 1 = 5.

The correct procedure when local depth = global depth and overflow occurs: (1) Double the directory (global depth d → d+1, directory entries 2^d → 2^(d+1)); (2) Increment the splitting bucket's local depth to d+1; (3) Create a new sibling bucket; (4) Redistribute all keys in the old bucket between the two new buckets based on the (d+1)-th bit; (5) Update all directory pointers - each old pair of entries now points to one of the two new buckets based on the new prefix bit.

In a B+ tree, internal nodes guide search and do not point directly to data records. Data-record pointers are at the leaf level.

The sum of directory entries pointing to each bucket must equal the total number of directory entries = 2^global_depth = 2^4 = 16. Since each bucket i contributes 2^(d - d_i) directory pointers, and every directory entry points to exactly one bucket, the sum over all buckets = 2^d = 16.

(A) True - extendible hashing doubles the entire directory on a critical split; linear hashing splits the 'next' bucket in round-robin order. (B) True - if all keys collide on the same prefix bits, directory size can grow exponentially. (C) False - linear hashing uses a direct computation (two hash functions), not a directory pointer table. (D) False - both can have overflow chains; linear hashing commonly uses overflow chains on bucket overflow. (E) True - linear hashing uses two hash functions h_i and h_{i+1} to compute the bucket address directly; no directory is needed.

A B+ tree's sorted leaf linked list makes range queries very efficient. A hash index excels at equality searches but cannot efficiently answer range queries.

(A) True - without directory in memory: 1 I/O for directory page + 1 I/O for bucket = 2 I/Os. (B) False - directory can grow exponentially if keys cluster (e.g., global depth can be much larger than log2(N)). (C) False - insertion can require directory doubling which costs O(2^d) work in the worst case. (D) True - a key moves only when its bucket is split; otherwise it stays put. (E) False - extendible hashing does not support range queries efficiently.

The local depth d_i of bucket i is the number of hash-prefix bits that all keys in that bucket share. A bucket may be pointed to by 2^(global_depth - local_depth) directory entries. When local depth equals global depth and the bucket overflows, the directory must double before the bucket can split.

(A) True - local depth = global depth on overflow mandates directory doubling. (B) False - when local depth < global depth, the directory already has sufficient entries to accommodate the split; no doubling needed. (C) False - merging may allow directory halving (reverse of doubling), not doubling. (D) False - redistribution after a split is routine; no directory doubling unless triggered by ld=gd condition. (E) False - there is still space; no overflow, no split, no doubling.

The number of directory entries pointing to a bucket with local depth d_i when global depth is d is 2^(d - d_i) = 2^(3-2) = 2^1 = 2.

Minimum fan-out per internal node = ceil(50/2) = 25. Height h satisfies 25^h >= 1,00,000. 25^1=25, 25^2=625, 25^3=15625, 25^4=390625 >= 100000. So height = 4.

If internal nodes are in memory and only leaf nodes and data blocks need disk I/O: 1 I/O to read the matching leaf node + 1 I/O to read the data block = 2 block accesses total.

The global depth d of the directory in extendible hashing is the number of least-significant (or most-significant) bits of the hash value h(k) used to determine the directory entry. The directory has 2^d entries. Global depth grows by 1 each time the directory doubles.

Maximum keys in a block determine order p: (p-1)20 + p8 ≤ 1024 ⟹ 28p - 20 ≤ 1024 ⟹ 28p ≤ 1044 ⟹ p ≤ 37.28. Thus max order p = 37.

On leaf overflow in a B+ tree: (A) the middle key is pushed/copied up to the parent. (B) A new leaf is created for the split. (C) The leaf linked list must be updated to include the new leaf. (E) If the parent is full, it splits too (key is pushed up further). (D) The data file is never reorganized for a secondary index.