Neural Sync Active
22 - File Organization
Registry Synced
22 - File Organization
355 words
2 min read
Reading compass
Now · 🎯 Learning Objectives
22 - File Organization
🎯 Learning Objectives
After reading this topic, you will be able to:
- Compare fixed-length and variable-length record storage
- Explain slotted page organization
- Describe heap, sequential, and hash file organizations
- Understand data structure operations complexity
📖 Core Content
22.1 File Organization Methods
| Organization | Description | Best For |
|---|---|---|
| Heap | Records stored wherever space available | Bulk loading, full scans |
| Sequential | Records ordered by search key | Range queries, sorted output |
| Hashing | Records distributed by hash function | Equality lookups |
22.2 Fixed-Length Records
Each record has the same length. Simple to implement:
- Record i starts at offset i×recordlength
- Deleting a record: move the last record to fill the gap (or mark as deleted)
22.3 Variable-Length Records
Records have different lengths (e.g., VARCHAR attributes). Two approaches:
Slotted Page Structure
(Diagram)
The header contains:
- Number of record entries
- Array of (offset, length) for each record
- Pointer to end of free space Advantages: Supports variable-length records, easy to add/delete records, no external fragmentation.
22.4 Data Structures Review
| Structure | Search (Avg) | Insert (Avg) | Delete (Avg) |
|---|---|---|---|
| Array | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(1) | O(1) |
| Stack | O(n) | O(1) | O(1) |
| Queue | O(n) | O(1) | O(1) |
| BST (balanced) | O(log n) | O(log n) | O(log n) |
| Hash Table | O(1) | O(1) | O(1) |
| B-Tree | O(log n) | O(log n) | O(log n) |
22.5 Heap File Organization
- Records stored in any available space
- No particular ordering
- Insert: Append to last page (fast)
- Search: Must scan all pages (slow for large files)
- Best for: Tables where you always read all rows
📝 Practice Questions
Q1. What is a slotted page? Why is it used?
AnswerA slotted page divides a disk block into slots that can hold variable-length records. The page header contains an array of (offset, length) pairs for each record. Used because DBMS records have variable length (VARCHAR fields), and slotted pages minimize wasted space.
Q2. Compare heap and sequential file organization.
Answer
- Heap: Unordered; fast inserts, slow searches
- Sequential: Ordered by key; fast range queries and sorted output, slower inserts (need to maintain order)
🔗 Cross-References
- Previous Topic: 21 - RAID Systems
- Next Topic: 23 - Indexing
- Textbook: Chapter 10 (Storage and File Structure) Join Discord Previous21 - RAID SystemsNext23 - Indexing