File System Practice Questions

For a B+ tree of order n=4, an internal node (non-root) must have at least ceil(n/2) = 2 pointers and hence ceil(n/2) - 1 = 1 key.

In a B+ tree, internal nodes act as routing nodes with search keys and child pointers. Only leaf nodes hold the actual search key-record pointer pairs, and they are chained together for efficient sequential scan and range queries.

A dense index has one entry per data record - so A is correct. B is also possible when multiple records in a block share the same salary, but C is false (secondary index doesn't sort data). D is true as well since B+ tree leaves are sorted. The single best answer in a standard MCQ is A, but in GATE 2012 context the answer is A and D.

(A) True - leaf nodes are linked for sequential access. (B) True - a dense index has one entry per record. (C) False - secondary indices do not require the data file to be sorted. (D) True - B+ trees support both via their structure. (E) True - only leaf nodes contain record pointers; internal nodes have only routing keys and child pointers.

Order 7 means max 6 keys per leaf. With height 3 (Root=L1, L2=Internal, L3=Leaves): Root has max 7 children. Each L2 node has max 7 children. Max leaves = 7 × 7 = 49. Total records = 49 leaves × 6 records/leaf = 294.

Number of directory entries = 2^global_depth = 2^4 = 16.

(A) True - overflow is handled by bucket splitting, not chaining. (B) True - only the directory doubles on a split, not a full rehash of all keys. (C) False - worst case can degrade if many keys hash to the same bucket (all bits identical), causing repeated splits. (D) True - buckets are allocated on demand. (E) False - extendible hashing does not maintain sorted order; range queries require a full scan.

The worst-case height of a B+ tree occurs when every node is at its minimum occupancy (ceil(n/2) pointers for internal nodes). Hence the height is at most ceil(log_{ceil(n/2)}(N)).

(A) True - directory has 2^d entries, always a power of 2. (B) False - different buckets can have different local depths; a split only increments the splitting bucket's local depth. (C) True - when local depth equals global depth, a split forces directory doubling. (D) True - when a bucket's local depth < global depth, it is shared by 2^(d - d_i) directory entries. (E) True - typically the directory is small enough to fit in memory but is logically stored on disk like the buckets.

Key 22: h(22) mod 4 → we use 2-bit suffix. 22 in binary is 10110, last 2 bits = 10 → directory[10] = B3. B3 currently has {6,14} (full, capacity=2). Insert 22 → overflow. B3 local depth=1 < global depth=2 → no directory doubling needed. Split B3: local depth becomes 2. New B3' gets prefix 10, new B4 gets prefix 00... wait: 6 in binary = 0110 → last 2 bits = 10 → B3'; 14 = 1110 → last 2 bits = 10 → B3'; 22 = 10110 → last 2 bits = 10 → B3'. All three keys hash to 10! A split doesn't help; we may need an overflow chain or further splits. In standard textbook treatment: split is attempted; if all keys fall in the same new bucket, we may need to double the directory again. This is a degenerate case. The correct initial answer for the question as posed is A - split without directory doubling since ld < gd.

After inserting A(00), B(01), C(10), D(10): bucket for prefix 10 has {C, D} (2 entries, fine). Insert E(10): bucket 10 has {C,D,E} = 3 = capacity, it overflows when the next insert comes. Actually capacity is 3, so {C,D,E} fills it. Next insert into prefix 10 would overflow. Since all 5 are inserted and bucket 10 hits exactly capacity 3, no overflow yet → global depth stays 2. BUT the 5th key E fills bucket 10 to capacity 3 (not overflow). If a 6th key with hash 10 were inserted it would trigger a split. As stated, global depth remains 2. Re-reading: insert A,B,C,D,E. Bucket-10 gets C,D,E = 3 = full but not overflow. Global depth = 2.

(A) True - directory entries are pointers to disk buckets, not records. (B) False - directory doubles only on the specific condition where ld=gd; overflow with ld<gd splits the bucket without doubling. (C) True - this is the exact triggering condition for directory doubling. (D) True - after deletions and bucket merges, if max(all local depths) < global depth, the directory can be halved. (E) False - the directory is typically small enough to fit entirely in main memory, which is one of extendible hashing's advantages.

(A) True - directory does not double since ld < gd; global depth stays the same. (B) True - the splitting bucket's local depth goes from d_i to d_i+1. (C) False - the new sibling bucket gets local depth d_i+1, same as the updated old bucket (not same as the old local depth d_i). (D) True - the 2^(gd - d_i) directory entries that pointed to the old bucket are split: half go to the new bucket A and half to new bucket B. (E) True - splitting one bucket does not affect others.

By the standard GATE definition, a B+ tree of order n has at most n pointers in internal nodes (and n-1 keys). Leaf nodes hold at most n-1 search-key/pointer pairs (plus one pointer to the next leaf). So the maximum data pointers in a leaf = n - 1.

Maximum number of distinct buckets = number of directory entries = 2^global_depth = 2^5 = 32. This occurs when every bucket has local depth equal to the global depth (5), meaning each of the 32 directory entries points to a unique bucket.