Questions
1–2 long-answer questions
Difficulty
Medium
Importance
Core topic for university DBMS finals
Overview
Indexing and storage are fundamental database concepts that determine how data is physically retrieved and stored to optimize performance. In university exams, mastering these techniques is crucial as they bridge the gap between abstract data structures and efficient query processing.
File Organization
File organization dictates how records are mapped onto disk blocks, which significantly impacts access time. Understanding these methods is essential for answering theory-based questions on sequential, heap, and hashed file structures.
- Sequential organization stores records in order based on a search key
- Heap file organization places records randomly in available disk space
- Clustered file organization stores related records from different tables together
- Hash file organization uses a hash function to map keys to specific buckets
B-Tree and B+ Tree Indexing
B-Trees and B+ Trees are self-balancing search trees designed to minimize disk I/O operations for large datasets. They are the most frequently asked topics in university exams, often requiring diagrams.
- B-Tree nodes contain both keys and actual record pointers
- B+ Tree stores all data in leaf nodes with internal nodes acting as guides
- B+ Tree leaves are linked, enabling efficient range scans
- Minimum degree 't' dictates that every node except the root must have at least t-1 keys
Hashing Techniques
Hashing provides direct access to data by mapping a search key directly to a storage address. It is a highly efficient technique but faces challenges when handling collisions.
- Static hashing uses a fixed number of buckets
- Dynamic hashing allows the hash table to grow or shrink as needed
- Collision resolution methods include open addressing and chaining
- Extendible hashing uses a directory that doubles in size to manage overflow
Formula Sheet
Min keys per node: t - 1
Max keys per node: 2t - 1
Min children per node: t
Max children per node: 2t
Exam Tip
Always draw the tree structure even if not explicitly asked; a clean diagram showing node splitting is a guaranteed mark booster.
Common Mistakes
- Confusing B-Tree with B+ Tree, specifically forgetting that only B+ Trees have linked leaf nodes.
- Neglecting to mention the 'order' or 'degree' of the tree in structural diagrams.
- Failing to explain collision handling when describing hashing algorithms.
More Revision Notes
Ready to test yourself?
Play topic-wise Indexing & Storage questions in Aspirant Arcade — gamified MCQ practice.
Download Free