This set covers how a DBMS stores and finds data: file organisation, types of indexes, B and B+ trees, hashing and the basics of query optimisation and cost estimation. About half the questions are numericals of the kind asked in GATE and university exams, and the concept questions are useful for database interviews and placements.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 18 questions.
Topics covered in this set
- File organisation and index types
- Dense, sparse, clustered and secondary indexes
- B-tree vs B+ tree, order and fan-out numericals
- Static and extendible hashing
- Query processing, optimisation and join cost
DBMS MCQs with answers and explanations
Q1. In a heap (unordered) file organisation, which operation is the cheapest?
a) Searching for a record by key
b) Running a range query on a key
c) Finding the minimum value of an attribute
d) Inserting a new record
Q2. A primary index (also called a clustering index in Korth) is an index whose search key:
a) Also defines the physical (sequential) order of records in the data file
b) Is any non-key field of an unordered file
c) Is stored in a separate hash table
d) Must always be a foreign key
Q3. Which statement about a sparse index is correct?
a) It has an entry for every record in the file
b) It can be built on a file that is not sorted on the search key
c) It has entries for only some search-key values, so the data file must be sorted on that key
d) It is always a secondary index
Q4. Why must a secondary index be dense?
a) Because secondary indexes are always built on the primary key
b) Because the file is not sorted on the secondary key, so records with a given value can be anywhere and each value must be indexed
c) Because dense indexes take less space than sparse indexes
d) Because B+ trees cannot store sparse entries
Q5. How many clustered (clustering) indexes can a single table have?
a) At most one
b) At most two
c) One per column
d) Unlimited
Q6. A sorted file has 30,000 records of 100 bytes each, stored unspanned in 1024-byte blocks. A sparse primary index has one entry per data block, each entry being 15 bytes (9-byte key + 6-byte pointer). How many blocks does the index occupy?
a) 30
b) 300
c) 442
d) 45
Q7. What is the key structural difference between a B-tree and a B+ tree?
a) A B+ tree is not height-balanced, while a B-tree is
b) A B-tree stores data pointers only in its leaf nodes
c) In a B+ tree all data (record) pointers are in the leaves and the leaves are linked, which makes range queries efficient
d) A B+ tree cannot store duplicate search-key values
Q8. Block size is 512 bytes, a search key is 10 bytes and a block (child) pointer is 8 bytes. What is the maximum order p (number of child pointers) of a B+ tree internal node?
a) 29
b) 28
c) 30
d) 51
Q9. Using the same 512-byte block and 10-byte key, a B+ tree leaf stores (key, record pointer) pairs plus one 8-byte pointer to the next leaf. A record pointer is 6 bytes. What is the maximum number of keys in a leaf?
a) 32
b) 31
c) 28
d) 29
Q10. In a B+ tree, every internal node can have at most 100 children and every leaf can hold at most 100 keys. What is the maximum number of keys that can be indexed by a tree with exactly 3 levels (root, one internal level, leaf level)?
a) 10,000
b) 30,000
c) 100,000
d) 1,000,000
Q11. A B+ tree's internal nodes can hold at most 7 child pointers. What is the minimum number of child pointers a non-root internal node must have?
a) 3
b) 7
c) 4
d) 2
Q12. When does the height of a B-tree or B+ tree increase during insertion?
a) Whenever any leaf node splits
b) Only when the root node splits
c) Whenever a key is inserted into the root
d) Whenever a leaf becomes exactly half full
Q13. What is the main limitation of static hashing in a growing database?
a) The number of buckets is fixed, so growth leads to long overflow chains (or wasted space if the data shrinks)
b) It cannot support equality searches
c) It requires the data file to be sorted
d) It cannot store records with duplicate keys
Q14. In extendible hashing, the global depth is 3. How many directory entries point to a bucket whose local depth is 2?
a) 1
b) 3
c) 2
d) 4
Q15. In extendible hashing with global depth 3, a bucket with local depth 3 overflows. What happens to the directory size after the split?
a) Stays at 8
b) Becomes 9
c) Becomes 12
d) Doubles to 16
Q16. Which index is most suitable for the query WHERE salary BETWEEN 30000 AND 50000?
a) A hash index on salary
b) A B+ tree index on salary
c) A hash index on emp_id
d) No index, since hashing always outperforms trees
Q17. Which heuristic is applied in algebraic (rule-based) query optimisation?
a) Perform selections and projections as early as possible to shrink intermediate results
b) Perform Cartesian products before any selection
c) Delay all selections until every join is complete
d) Always use nested-loop join regardless of relation size
Q18. Relation R occupies 100 blocks and S occupies 400 blocks. Using block nested-loop join with R as the outer relation and only one buffer block for each relation (worst case), how many block transfers are needed?
a) 40,000
b) 500
c) 40,400
d) 40,100
Quick revision notes
- Heap file: fast insert, slow search; sorted file: fast search and range scan, slow insert.
- Primary/clustering index is on the sort key of the file; at most one per table.
- Sparse index needs a sorted file; secondary indexes are always dense.
- B+ tree: record pointers only in leaves, leaves linked; higher fan-out than a B-tree.
- B+ internal node order: p × (pointer size) + (p - 1) × (key size) ≤ block size.
- Non-root nodes are at least half full; the root may have just 2 children; height grows only on root split.
- Extendible hashing: directory doubles only when an overflowing bucket's local depth equals the global depth.
- Block nested-loop worst case = b_R × b_S + b_R; put the smaller relation on the outside.
Frequently asked questions
Why do databases use B+ trees instead of binary search trees?
A B+ tree node is sized to one disk block and holds hundreds of keys, so the tree stays very shallow and needs only a few disk reads per lookup. A binary tree would have a large height and need far more disk accesses.
What is the difference between a dense and a sparse index?
A dense index has an entry for every search-key value in the file, while a sparse index has entries only for some values, typically one per block. Sparse indexes are smaller but work only when the file is sorted on the index key.
What does the query optimiser actually do?
It rewrites the query into equivalent relational algebra plans, estimates the cost of each using statistics such as table sizes and number of distinct values, and picks the plan with the lowest estimated cost. Choices include join order, join algorithm and which index to use.
Comments
Post a Comment