File Structures and Indexing · Database Management System · GATE CSE

Which of the following file organizations is/are I/O efficient for the scan operation in DBMS?

In a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for which one of the following cases?

Consider a linear list based implementation in a file system. Each directory is a list of nodes, where each node contains the file name along with the file metadata, such as the list of pointers to the data blocks. Consider a given directory foo.

Which of the following operations will necessarily require a full scan of foo for successful completion?

There are five records in a database.

There is an index file associated with this and it contains the values 1, 3, 2, 5 and 4. Which one of the fields is the index built from?

In a $\mathrm{B}^{+}$- tree where each node can hold at most four key values, a root to leaf path consists of the following nodes:

$$A=(49,77,83,-), B=(7,19,33,44), C=\left(20^*, 22^*, 25^*, 26^*\right)$$

The *-marked keys signify that these are data entries in a leaf.

Assume that a pointer between keys $k_1$ and $k_2$ points to a subtree containing keys in [ $k_1, k_2$ ], and that when a leaf is created, the smallest key in it is copied up into A record with key value 23 is inserted into the $\mathrm{B}^{+}$- tree.

The smallest key value in the parent of the leaf that contains $25^*$ is _________ . (Answer in integer)

Consider a database of fixed-length records, stored as an ordered file. The database has 25,000 records, with each record being 100 bytes, of which the primary key occupies 15 bytes. The data file is block-aligned in that each data record is fully contained within a block. The database is indexed by a primary index file, which is also stored as a block-aligned ordered file. The figure below depicts this indexing scheme.

Suppose the block size of the file system is 1024 bytes, and a pointer to a block occupies 5 bytes. The system uses binary search on the index file to search for a record with a given key. You may assume that a binary search on an index file of b blocks takes $$\left\lceil {{{\log }_2}b} \right\rceil $$ block accesses in the worst case.

Given a key, the number of block accesses required to identify the block in the data file that may contain a record with the key, in the worst case, is ___________.

Consider two files systems A and B, that use contiguous allocation and linked allocation, respectively. A file of size 100 blocks is already stored in A and also in B. Now, consider inserting a new block in the middle of the file (between 50^th and 51^st block), whose data is already available in the memory. Assume that there are enough free blocks at the end of the file and that the file control blocks are already in memory. Let the number of disk accesses required to insert a block in the midele of the file in A and B are n_A and n_B, respectively, then the value of n_A + n_B is _____________.

10, 3, 6, 8, 4, 2, 1

Now the key K 50 is deleted from the B⁺ tree resulting after the two insertions made earlier. Consider the following statements about the B⁺ tree resulting after this deletion.

i) The height of the tree remains the same.

ii) The node (disregarding the links) is present in the tree.

iii) The root node remains unchanged (disregarding the links).

Keys K 15 and then K 25 are inserted into this tree in that order. Exactly how many of the following nodes (disregarding the links) will be present in the tree after the two insertions?