GATE_Practice Sheet 01_DPP 1 https://qbg-admin.penpencil.co/finalize-question-paper...

GATE

CS & IT

Database Management System

DPP: 1
File Organization and Indexing

Q1 Assume a relational database system that holds Q3 Consider a SQL statement SELECT P1, P2, P3 from
relation: C(colleges) with the following Q WHERE P2 = ‘Pavan’ is frequently executed,
characteristics which column(s) should be considered for
• Records are stored as fixed length, fixed indexing based only on the statement itself ?
format records, length is 256 bytes. (A) P1 only (B) P2 only
• There are 16384 records. (C) P3 only (D) P1, P2 and P3
• Records contains key attribute
Q4 Consider the following specification of system-
CollegeNumber (C.N), length 22 bytes and
Disk block size = 2048 bytes
other fields.
Block pointer size = 16 bytes
• Unspanned organization is used to store the
Record pointer size = 20 bytes long
information or record.
file contains 30,000 records.
Let’s suppose we want to build a sparse primary
Each record of the file has the following fields:
index on C.N then how many numbers of 4096-
byte blocks are needed to store the primary
index when block pointer size is 10 bytes ______?
(A) 7 (B) 8
(C) 9 (D) 10

Q2 Assume a relational database system that holds

relation: Product (P) with the following
characteristics
• Records are stored as fixed length, fixed
format records, with the length of 256 bytes.
• There are 262144 records.
• Records contain attribute P.I (The identifier of
the product involved), with the length 24
bytes, and an attribute P.C (the cost of
product), with the length 32 bytes and other
fields.
• Unspanned organization is used to store the
record.
Assume that we want to build a dense secondary
index on P.C, then how many numbers of 4096-
byte blocks needed to store the dense
secondary index. When record pointer size is 32
bytes? _______.

Android App | iOS App | PW Website

1 of 8 11/07/24, 14:24
GATE_Practice Sheet 01_DPP 1 https://qbg-admin.penpencil.co/finalize-question-paper...

GATE

stored as an ordered file. The database has

Size 25,000 records with each records being 100
Field (in bytes, of which the non-key attribute on which
s Byte clustering index is formed occupies 10 bytes. The
s) data file is completely block aligned.
Suppose, block size, of the file system is 512
Emp bytes and a pointer to the block occupy 5 bytes.
Nam 5 You may assume that a binary search on an index
e file of b block may take élog2bù accesses in worst
case.
Emp Given that a cluster consumes 2 blocks, the
10
Num number of block accesses required to identify
the desired data in the worst case is ______.
Dept
9 Q7 Consider the following statements-
Num
S1 : If the records of a relation X are physically
Addr 20 ordered over a non-key field P and an index is
build over the key-field of relation X, then the
PhN
9 index is necessarily a secondary index over key
um
attribute.
DOB 1 S2: More than one secondary indexes are
possible.
Sex 1
Which of the given statement(s) is/are CORRECT
Job 3 ?
(A) S1 only
Sal 5
(B) S2 only
An extra/additional byte is used per record to (C) Both S1 and S2
represent end of the record. (D) Neither S1 nor S2
What is the block factor of the database file
assuming unspanned file organization ? Q8 The order of a leaf node in a B+ tree is the
(A) 16 (B) 32 maximum number of (value, data record pointer)
(C) 48 (D) 64 pairs it can hold. Given that the block size is 1K
bytes, data record pointer is 8 bytes long, the
Q5 Which one of the following statements is/are value field is 10 bytes long and a block pointer is
True regarding indexing ? 6 bytes, then what is the order of the leaf node?
(A) A database file can contain multiple clustered (A) 53 (B) 54
indexes. (C) 55 (D) 56
(B) A database file can consist of only one
clustered index with multiple secondary Q9 Given a block can hold either 3 records or 10 key
indexes pointers. A database contains P records, then
(C) A database file can consist of multiple how many blocks do we need to hold the data
primary indexes. file and the dense index?
P
(D) A database file can consist of both primary (A) 30 (B) P
3
and clustered index. (C) 13P
30
P
(D) 10

Q6 Consider a database of fixed-length records Q10 The order of an internal node in B+ tree index is

Android App | iOS App | PW Website

2 of 8 11/07/24, 14:24
GATE_Practice Sheet 01_DPP 1 https://qbg-admin.penpencil.co/finalize-question-paper...

GATE

the maximum number of children it can have. (C) Both S1 and S2 are true
Assume that a child pointer takes 6 bytes, the (D) Neither S1 nor S2 is true
search field value takes 34 bytes and the blocks
Q15 Which of the following is/are true reading B+
size is 2048 bytes. The order of the internal node
tree?
is ________.
(A) Records can be fetched in equal number of
Q11 Assume a disk with block size B = 1024 Bytes, A disk access.
block pointer is PB = 12 bytes long and a record (B) Height of the tree remains balanced and less
pointer is PR = 18 bytes long. A file has 1,00,000 as compared to B tree.
patients records of size 100 bytes. Suppose the (C) Keys are used for indexing
file is ordered by the key field PID and we want (D) Faster search queries as the data is stored
to construct a secondary (dense) index on non- only on the leaf nodes.
key field DeptID (14 bytes), then minimum of how
Q16 Consider the following specification of system
many blocks are required to store index file
with disk block size 2048 bytes, block pointer
assuming an unspanned organisation?
size 14 bytes, record pointer size 18 bytes long
(A) 3000
and file size 60,000 records. Each record of file is
(B) 3100
256 bytes long and record of the size is sorted
(C) 3125
on the key field. If the primary index (sparse) is
(D) None of the above
built on the kye field (ESN) which is 18 bytes
Q12 The order of a node in B tree is the maximum long. What is the Index blocking factors (That is
number of block pointers it can hold. Given that number of indexes per block)
the block size is 2K bytes, data record pointer is 8 Assuming unspanned file organization
bytes long, the search key is 9 bytes long and a _________.
block pointer is 5 bytes long. The best possible
Q17 Data For This & Next Question :
order of B tree node is .
Consider a disk blocking size B = 1024 bytes. A
Q13 Consider the keys (1– 5000) are going to be block pointer is PB =12 bytes long and a record
interested into a B+ tree. Assume, all the order are pointer is PR = 7 bytes long. A file has r = 60,000
available before insertion. The orders P for B+ patient records of fixed length. The size of record
tree node is defined as- is 230 bytes. Suppose the file is not ordered by
2 to P pointer for root the key field PSN (18 bytes) and we want to
⌈ P2 ⌉ to P pointer for another node. construct a secondary index on PSN.
+ The number of first level index entries is .
The maximum possible levels in a B tree index
for P = 9 is _________.
Q18 The number of first level index block is ?
(Assume that level of the root node is 1)
(A) 1800 (B) 1825
Q14 Consider the following statements: (C) 1850 (D) 1857
S1: In a B+ tree, data pointers are stored only
Q19 Consider an unordered file of 106 records with
at the leaf nodes of the tree.
records size of 200 bytes stored on blocks of
S2: The leaf node has an entry for every
8KB with a spanned records organization. We will
value of the search field, along with the data
assume that no system related information is
pointer to the record.
stored within a block, then how many blocks
Choose the correct statements.
would it be need to store this file ?
(A) Only S1 is true
(A) 24400 (B) 24405
(B) Only S2 is true

Android App | iOS App | PW Website

3 of 8 11/07/24, 14:24
GATE_Practice Sheet 01_DPP 1 https://qbg-admin.penpencil.co/finalize-question-paper...

GATE

(C) 24410 (D) 24415 two di�erent denes first level indexes on various
keys.
Q20 Consider the following statements:
Select the correct statements.
S1: for any given data file, it is possible to create
(A) Only S1 correct
two di�erent sparse first level indexes on various
(B) Only S2 correct
keys.
(C) Both S1 and S2 is correct
S2: for any given data file, it is possible to create
(D) Neither is S1 nor S2 is correct.

Android App | iOS App | PW Website

4 of 8 11/07/24, 14:24
GATE_Practice Sheet 01_DPP 1 https://qbg-admin.penpencil.co/finalize-question-paper...

GATE

Answer Key
Q1 (B) Q11 (C)

Q2 (4096) Q12 93

Q3 (B) Q13 6

Q4 (B) Q14 (C)

Q5 (B) Q15 (A, B, C, D)

Q6 (10) Q16 (64)

Q7 (C) Q17 (60000)

Q8 (D) Q18 (D)

Q9 (C) Q19 (D)

Q10 52 Q20 (B)

Android App | iOS App | PW Website

5 of 8 11/07/24, 14:24
GATE_Practice Sheet 01_DPP 1 https://qbg-admin.penpencil.co/finalize-question-paper...

GATE

Hints & Solutions

Q1 Text Solution: (b) True: A database file can consist of one
In the primary index, number of entries in the clustered index and multiple secondary index.
index block equals to number of blocks of (c) False: The index on a unique field on which
relation. database is sorted is primary index and there can
Number of database records in a single block B = be only one primary index.
4096/256 = 16 (d) False: A database file can consist of either a
Number of blocks of relation C = 16384/16 = 1024 primary or clustered index but not both.
Size of indexes = size of key field Q6 Text Solution:
+ size of block pointer Block factor of database file = ⌊ 100 ⌋
512
= 22 + 10 = 32 bytes
= 5 records/block
Number of indexes records present in single
Number of blocks required to store 25,000
block = 4096/32 = 128
records
Total number of blocks required to store primary 25000
=⌈ 5
⌉
index = 1024/128 = 8.
= 5000 blocks
Q2 Text Solution: Each cluster consumer 2 blocks
In dense secondary index, number of entries in 5000
Number of entries in index file = 2
= 2500.
the index blocks equals to number of records of 512
Block factor of index file = ⌊ 15 ⌋ = 15 entries/
relation. block
• Number of records in the relation P = 262144 25000
Number of blocks in index file = ⌈ 15 ⌉ = 167
Size of index = size of key field The number of block accesses in worst case
+ size of record pointer = ⌈log2 167⌉ + 1 + 1
= 32 + 32 = 64 bytes ⏐ ⏐
↓ ↓
• Number of index entry in single block ⏐
↓
= 4096/64 = 64
So, the total number of blocks required to store
for index Accessing 1st Accessing 2nd
file search block of cluster block of cluster
primary index = 262144/64 = 4096. = 8 + 1 + 1 = 10
Q3 Text Solution:
The column on which condition gets applied Q7 Text Solution:
should be considered for indexing. S1: Records are ordered over non-key field. It is
\ P2 is the answer. unordered over key field.
Q4 Text Solution: Hence, secondary index if formed over
Blocking factor (i.e number of records per block) unordered key-field. Hence, its CORRECT.
= Block size S2: CORRECT. More than one secondary index is
record size
Record size of file = Sum of all field + additional possible.

bytes = 63 + 1 = 64 Q8 Text Solution:

2048
∴ Number of records per block = 64
= 32. Disk block

Q5 Text Solution:
(a) False: A database file can contain one Given data,
clustered index because the database is sorted Disk block size = 1K byte = 210 bytes = 1024
on one field only. bytes

Android App | iOS App | PW Website

6 of 8 11/07/24, 14:24
GATE_Practice Sheet 01_DPP 1 https://qbg-admin.penpencil.co/finalize-question-paper...

GATE

Block pointer (B) = 6 bytes = ⌈100000/32⌉

Key field (K) = 10 bytes = 3125 blocks
Record/ data pointer (R) = 8 bytes Q12 Text Solution:
Order of leaf node= P Order P: maximum blocks pointers per node.
B + (P)(K + R) < D Block size > P × (Block size pointer) + (P –1) × (size
6 + (P)(10 + 8) < 1024 of keys + size of record pointers)
18 P < 1024 – 6 Block size > P ×5 + (P – 1) × (9 + 8)
P = ⌊ 1018
18
⌋ 2048 > 5P + 17P – 17
∴ P = 56 22P≥ 2065
Maximum number of (value, data record P = ⌊ 2065 ⌋ = 93
22
pointer)
Q13 Text Solution:
Pairs = 56
For maximum possible levels, minimum number
The order of the leaf node is 56.
of keys should be present in an index node.
5000
Number of nodes in the last level = ⌊ 4 ⌋=1250
Q9 Text Solution: 9
[Minimum (⌈ 2 ⌉ − 1) keys for other node]
For storing the records, numbers of blocks
required = P
3
and for storing the keys in dense
P
index number of blocks required = 10
So, total blocks required are P
3
P
+ 10 = 13P
30

Q10 Text Solution:

Size of child pointer = 6 bytes
Size of search field value = 34 bytes
Block size = 2048.
Order of internal node = P Q14 Text Solution:
(Number of blocks pointer in any node) S1(True): In a B+ tree, data pointers are stored
(P –1)34 + P × 6 < 2048 only at the leaf nodes of the tree.
34P + 6P < 2048 + 34 S2(True): the leaf nodes have an entry for every
40P < 2082 value of the search field, along with the data
2082
P≤ 40 pointer to the record.
= ⌊52.05⌋ ≃ 52 Q15 Text Solution:
Q11 Text Solution: True: Records can be fetched in equal number
Blocking factor, bfr = ⌊1024/100⌋ of accesses
= 10 records per block True: Height of the tree remains balanced and
Number of blocks needs for file = ⌈r/bfr⌉ less as compared to B tree.
True: We can access the data stored in a B+ tree
= ⌈100000/10⌉ = 10000 sequentially as well.
Index records size Ri= (Non – Key DeptID + PR)) True: Faster search queries as the data is stored
= 14 + 18 = 32 bytes only on the leaf node.
Index blocking factors bfri Q16 Text Solution:
= ⌊B/Ri ⌋ = ⌊1024/32⌋ = 32 2048
Number of indexes per blocks = 14+18 = 64.
st
Number of 1 level index entries r1 = number of –
records in the file = 100000 entries. Q17 Text Solution:

Number of first level index blocks b1 = ⌈r1 /bfri⌉ Number of first level index entries r1 = Number of

Android App | iOS App | PW Website

7 of 8 11/07/24, 14:24
GATE_Practice Sheet 01_DPP 1 https://qbg-admin.penpencil.co/finalize-question-paper...

GATE

files records r = 60,000. records.

Q18 Text Solution: As it is spanned hence it takes whole as 40.96

Index records size Ri = PSN + PR = 18 + 14 = 32 1 block contains 40.96 records.

106
bytes ∴ 1012 in 40.96
= 24415 blocks.
Index blocking factor bfri = fan-out = ⌊B/Ri ⌋ Q20 Text Solution:
= ⌊1024/32⌋ = 32 index Records per block. S1: (false): It is not possible because the
Number of 1st level index block b1= ⌈r1 /bfri ⌉ requirement of sparse indexing is that the
= ⌈60,000/32⌉ database must be stored and as we know that
= 1875 blocks. database is sorted only on one column.
Q19 Text Solution: S2:(True): Any number of dense index is possible
Blocks size = 8 KB to construct because no requirement of sorting
Records size = 200 bytes database in it.
8192
Number of records in a blocks = 200 = 40.96

Android App | iOS App | PW Website

8 of 8 11/07/24, 14:24