Computer-Networks
September 6, 2024UGC NET CS 2016 July- paper-3
September 6, 2024Database-Management-System
| Question 2 |
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 ⌈log2b⌉ 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 _____?
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 ⌈log2b⌉ 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 _____?
| 6 |
Question 2 Explanation:
Index entry size = primary key size + block pointer size = 5 + 15 = 20 bytes
Number of records per block = block size / record size = floor(1024/100) = 10
Number of data blocks required = number of records / number of records per block = 25000/10=2500 blocks
Number of entries of index file per block = block size / index entry size = floor(1024/20) = 51
Now, index file will have entries equal to number of blocks i.e. 2500 entries
Number of blocks required for index file = number of index file entries / entries per block = ceil(2500/51) = 50
Number of block access = ceil(log250)+1 = 6+1 = 7
One extra access is required to access the record in file.
Number of records per block = block size / record size = floor(1024/100) = 10
Number of data blocks required = number of records / number of records per block = 25000/10=2500 blocks
Number of entries of index file per block = block size / index entry size = floor(1024/20) = 51
Now, index file will have entries equal to number of blocks i.e. 2500 entries
Number of blocks required for index file = number of index file entries / entries per block = ceil(2500/51) = 50
Number of block access = ceil(log250)+1 = 6+1 = 7
One extra access is required to access the record in file.
Correct Answer: A
Question 2 Explanation:
Index entry size = primary key size + block pointer size = 5 + 15 = 20 bytes
Number of records per block = block size / record size = floor(1024/100) = 10
Number of data blocks required = number of records / number of records per block = 25000/10=2500 blocks
Number of entries of index file per block = block size / index entry size = floor(1024/20) = 51
Now, index file will have entries equal to number of blocks i.e. 2500 entries
Number of blocks required for index file = number of index file entries / entries per block = ceil(2500/51) = 50
Number of block access = ceil(log250)+1 = 6+1 = 7
One extra access is required to access the record in file.
Number of records per block = block size / record size = floor(1024/100) = 10
Number of data blocks required = number of records / number of records per block = 25000/10=2500 blocks
Number of entries of index file per block = block size / index entry size = floor(1024/20) = 51
Now, index file will have entries equal to number of blocks i.e. 2500 entries
Number of blocks required for index file = number of index file entries / entries per block = ceil(2500/51) = 50
Number of block access = ceil(log250)+1 = 6+1 = 7
One extra access is required to access the record in file.