File System Practice Questions

B+ trees support range queries and ordered traversal due to the sorted leaf linked list. They also self-balance on insert/delete. Hash indices offer O(1) average lookup but do not support range or ordered queries. Overflow buckets are a concern for hash indices, not B+ trees, but hash indices don't inherently avoid them - B+ trees are not relevant to this problem.

Each leaf node holds 4 entries (order 5 ⟹ max 4 key-pointer pairs per leaf). Number of leaf nodes = ceil(16000 / 4) = 4000.

The root node of a B+ tree must have at least 1 key (2 pointers) unless the tree has only one node (the root itself is a leaf). For a non-leaf root, the minimum is 1 key.

Start: global depth=1, Bucket0 (prefix 0, local depth 1), Bucket1 (prefix 1, local depth 1), capacity=2. Insert h=00 → Bucket0 (0); h=01 → Bucket0 (01 shares prefix 0); h=10 → Bucket1; h=11 → Bucket1. Now Bucket0 has {00,01} and Bucket1 has {10,11} - both full. Insert h=00: goes to Bucket0 (prefix 0), which is full and local depth=1=global depth=1 → double directory (global depth=2, 4 entries). Split Bucket0 into B00 (local depth=2, keys with prefix 00) and B01 (local depth=2, keys with prefix 01). Redistribute: 00→B00, 01→B01. Now insert h=00 → B00 which has 1 slot free (capacity 2). Final global depth = 2.

In a secondary B+ tree index, leaf nodes point to data records (or a bucket of pointers). The search key need not be unique. Secondary indices do NOT cluster data - that is a property of primary/clustering indices. Duplicate search key values are allowed in secondary indices.

The directory in extendible hashing contains exactly 2^d entries, where d is the global depth. Each entry is a pointer to a bucket. Multiple entries may point to the same bucket (when the bucket's local depth is less than the global depth).

The directory in extendible hashing contains exactly 2^d entries, where d is the global depth. Each entry is a pointer to a bucket. Multiple entries may point to the same bucket (when the bucket's local depth is less than the global depth).

Hash values: 1→001, 2→010, 3→011, 4→100, 5→101, 6→110, 7→111, 8→000, 9→001. Start gd=0, 1 bucket, cap=3. After 3 inserts (say 1,2,3) → full. 4th insert causes split → gd=1 (2 buckets). Continue. Keys 1,9 share prefix ..001 in relevant bits. With bucket size 3 and 9 distinct hash values (0-7), each possible 3-bit prefix has at most 2 keys (except prefix 001 which has keys 1 and 9). Starting from gd=0: first overflow → gd=1; subsequent splits of full buckets where ld<gd don't double directory. Minimum doublings = 1 (when splits are distributed evenly). Answer: 1.

Each entry in a leaf node = search key + record pointer = 12 + 10 = 22 bytes. Plus one block pointer for the next-leaf link = 8 bytes. So: floor((512 - 8) / 22) = floor(504 / 22) = floor(22.9) = 22 keys per leaf node.

When a full internal node (5 keys + new pushed-up key = 6 keys, 7 pointers) splits: the middle key (4th key) is pushed up to the parent. The right node receives the keys to the right of the middle: 3 keys (positions 5, 6 from 1-indexed). So the right sibling gets 3 keys.

A primary (clustering) index requires the data file to be physically ordered on the search key. A secondary index does not impose any ordering on the data file - it just provides a separate access path.

Deletion from a secondary B+ tree index requires removing the leaf entry (I). If the leaf underflows, nodes may merge (II). Internal nodes may need key updates when merges propagate (IV). Reorganization of the data file (III) is NOT required - the secondary index is independent of the data file ordering.

By definition, local depth d_i ≤ global depth d. When d_i = d, the bucket is 'private' (only 1 directory entry points to it). When d_i < d, multiple directory entries share the bucket. d_i can never exceed d because splitting a bucket with d_i = d requires first doubling the directory (incrementing d) before incrementing d_i.

Leaf nodes of a B+ tree store search key values and pointers to data records (not data records themselves in a secondary index). They are linked (typically singly or doubly) to support sequential/range access. They do support efficient range queries through this linkage.

When local depth d_i < global depth d, the directory already has enough entries to distinguish the two new buckets (since 2^d > 2^d_i). So: increment local depth from d_i to d_i+1; create a new sibling bucket; redistribute keys; update the 2^(d - d_i) directory entries that used to point to the old bucket - half now point to bucket A (prefix 0...) and half to bucket B (prefix 1...). No directory doubling required.

When the global depth increments from d to d+1, the number of directory entries goes from 2^d to 2^(d+1), which is exactly double. Each old entry at index i is duplicated: entries 2i and 2i+1 both initially point to the same bucket that entry i used to point to. Then the splitting bucket's two new halves are pointed to by the two relevant directory entries.

The directory has 2^d entries. In the best case, each directory entry points to a unique bucket (all local depths = global depth d), giving 2^d distinct buckets. Each bucket holds at most b records. Total maximum records = b × 2^d.

Start: gd=1, B0(prefix 0, ld=1, cap=2), B1(prefix 1, ld=1, cap=2). Insert 10(h=0)→B0{10}. Insert 20(h=0)→B0{10,20} full. Insert 30(h=1)→B1{30}. Insert 40(h=0)→B0 overflow! ld_B0=1=gd=1 → double directory: gd=2, 4 entries. Split B0: B00(prefix 00,ld=2) and B10(prefix 10,ld=2). Redistribute B0 contents: 10 (binary=1010, last 2 bits=10)→B10; 20 (binary=10100, last 2 bits=00)→B00. Insert 40 (binary=101000, last 2 bits=00) → B00{20,40}. Total buckets: B00, B10, B1 = 3 buckets.