📁 FILES OF UNORDERED AND ORDERED RECORDS
DBMS File Organization • Unordered Records • Ordered Records
📘 What are Unordered and Ordered Records?
A database file contains a collection of records. The records can be physically arranged in different ways.
Unordered File: Records are stored without following a particular ordering based on a search key.
Ordered File: Records are stored according to the values of a specified ordering field or search key.
Example:
A database file contains a collection of records. The records can be physically arranged in different ways.
Unordered File: Records are stored without following a particular ordering based on a search key.
Ordered File: Records are stored according to the values of a specified ordering field or search key.
Example:
Student_ID = 105, 101, 108, 103
Unordered
Student_ID = 101, 103, 105, 108
Ordered
Unordered
Student_ID = 101, 103, 105, 108
Ordered
📁 File Organization Based on Record Ordering
The physical order in which records are stored can affect
how efficiently records are inserted, searched, updated,
and deleted.
There are two basic arrangements:
1. Unordered Records
Records are stored in no particular order.
2. Ordered Records
Records are stored according to a specified search key.
1. Unordered Records
Records are stored in no particular order.
2. Ordered Records
Records are stored according to a specified search key.
UNORDERED
105 → 101 → 108 → 103
ORDERED
101 → 103 → 105 → 108
105 → 101 → 108 → 103
ORDERED
101 → 103 → 105 → 108
🔀 File of Unordered Records
In an unordered file, records are not maintained according
to a specific ordering field.
This type of organization is often called a heap file organization.
Example
| Student_ID | Name | Marks |
|---|---|---|
| 105 | Ravi | 78 |
| 101 | Anita | 91 |
| 108 | Suman | 84 |
| 103 | Rahul | 88 |
Notice that Student_ID values are not arranged in ascending
or descending order.
Basic Idea
New Record
↓
Find Suitable Free Space
↓
Store Record
🔢 File of Ordered Records
In an ordered file, records are physically maintained
according to a specified ordering field called the ordering key.
Example
| Student_ID | Name | Marks |
|---|---|---|
| 101 | Anita | 91 |
| 103 | Rahul | 88 |
| 105 | Ravi | 78 |
| 108 | Suman | 84 |
Student_ID is maintained in ascending order.
101 → 103 → 105 → 108
🏫 Same Data in Two Different Files
Student Records
Suppose the following students are entered:
105, 101, 108, 103
Unordered File
105 → 101 → 108 → 103
The DBMS does not rearrange the records according to Student_ID.
Ordered File
101 → 103 → 105 → 108
The DBMS maintains the records according to Student_ID.
Important:
The same logical records can be stored using different
physical organization methods.
➕ Insertion in an Unordered File
Insertion is generally simple because the new record does
not need to maintain a particular ordering.
Initial File
101 → 105 → 108
Insert Student 103
1
Receive the new record: Student_ID = 103.
2
Find suitable free space.
3
Store the new record.
101 → 105 → 108 → 103
Insertion is simple because no sorting is required.
➕ Insertion in an Ordered File
In an ordered file, insertion must preserve the ordering
of the records.
Initial File
101 → 105 → 108
Insert Student 103
1
New key = 103.
2
Compare 103 with existing keys.
3
103 belongs between 101 and 105.
4
Space may need to be created or records reorganized.
101 → 103 → 105 → 108
Insertion can be more expensive because the ordering must
be preserved.
🔍 Searching an Unordered File
Since records are not sorted, a search may require examining
records one by one.
Example
105 → 101 → 108 → 103
Search for Student_ID = 103.
1
Check 105 → Not found.
2
Check 101 → Not found.
3
Check 108 → Not found.
4
Check 103 → Found!
The search may require a linear scan.
Average idea: O(n)
🔎 Searching an Ordered File
Because the records are ordered, the DBMS can exploit
the ordering to search more efficiently.
Example
101 → 103 → 105 → 108
Search for Student_ID = 105.
1
Check the middle record: 103.
2
105 is greater than 103, so search the right half.
3
Check 105.
4
105 = 105 → Found!
Ordered records can support binary-search-style access
when the storage/access method permits it.
Binary search: O(log n)
🗑️ Delete from Unordered File
101 → 105 → 108 → 103
Delete Student_ID = 105.
1
Search for 105.
2
Record 105 is found.
3
Remove or mark the record according to the storage method.
101 → 108 → 103
Deletion is comparatively simple because no ordering
needs to be maintained.
🗑️ Delete from Ordered File
101 → 103 → 105 → 108
Delete Student_ID = 103.
1
Locate 103 using the ordering.
2
Remove or mark the record.
3
Maintain the required ordering and storage structure.
101 → 105 → 108
Physical deletion can require record movement or later
reorganization depending on the storage implementation.
🔄 Updating Records
An update changes one or more field values in an existing record.
If the updated field is the ordering key, maintaining the
order can become more complicated.
Example
101 | Rahul | 80
Change Student_ID 101 to 110.
If Student_ID is the ordering key, changing 101 → 110
may require the record to be moved to a new position.
If a non-ordering field such as Marks changes:
101 | Rahul | 80
↓
101 | Rahul | 90
The record's ordering position does not change.
101 | Rahul | 80
↓
101 | Rahul | 90
The record's ordering position does not change.
➡️ Sequential Access
Sequential access means records are processed one after
another in their physical or logical sequence.
Unordered File
105 → 101 → 108 → 103
The DBMS reads records in this stored sequence.
Ordered File
101 → 103 → 105 → 108
Sequential processing follows the maintained order.
Ordered files are useful for applications that frequently
process records in key order.
⚡ Binary Search on Ordered Records
Binary search repeatedly divides a sorted search space
into two parts.
It requires the search keys to be ordered.
Example
101 | 103 | 105 | 108 | 112 | 115 | 120
Search for 115.
1
Middle value = 108.
2
115 > 108, so ignore the left half.
3
Search the right half: 112, 115, 120.
4
Middle value = 115.
5
115 = 115 → Found!
Binary Search:
O(log n)
But practical DBMS file access also depends on blocks, disk I/O, buffering and the available access path.
But practical DBMS file access also depends on blocks, disk I/O, buffering and the available access path.
⭐ Advantages
🔀 Unordered File
✔ Simple organization
✔ New records can generally be inserted easily
✔ Good when insertions are frequent
✔ No need to maintain a sort order
✔ New records can generally be inserted easily
✔ Good when insertions are frequent
✔ No need to maintain a sort order
🔢 Ordered File
✔ Records remain sorted by the ordering key
✔ Efficient sequential processing in key order
✔ Can support efficient searching techniques
✔ Useful for range-based processing when appropriately stored
✔ Efficient sequential processing in key order
✔ Can support efficient searching techniques
✔ Useful for range-based processing when appropriately stored
⚠️ Disadvantages
🔀 Unordered File
❌ Search may require a linear scan
❌ Range processing may be inefficient without an index
❌ No inherent ordering for sequential key-based processing
❌ Range processing may be inefficient without an index
❌ No inherent ordering for sequential key-based processing
🔢 Ordered File
❌ Insertion may be expensive
❌ Deletion may require maintenance/reorganization
❌ Updating the ordering key can be costly
❌ Maintaining physical order adds overhead
❌ Deletion may require maintenance/reorganization
❌ Updating the ordering key can be costly
❌ Maintaining physical order adds overhead
⚖️ Unordered vs Ordered Records
| Feature | Unordered | Ordered |
|---|---|---|
| Record Arrangement | No particular order | Sorted by ordering key |
| Insertion | Generally easier | More expensive |
| Search | Usually linear scan | Can exploit ordering |
| Deletion | Generally easier | May require order maintenance |
| Sequential Processing | No key order | Efficient in key order |
| Range Processing | Usually less convenient | More convenient when appropriately accessed |
| Maintenance | Simple | Higher |
| Best For | Frequent insertion | Ordered processing/search |
UNORDERED
INSERTION ⭐⭐⭐⭐⭐
SEARCH ⭐⭐
ORDERED
INSERTION ⭐⭐
SEARCH ⭐⭐⭐⭐
SEQUENTIAL ORDER ⭐⭐⭐⭐⭐
INSERTION ⭐⭐⭐⭐⭐
SEARCH ⭐⭐
ORDERED
INSERTION ⭐⭐
SEARCH ⭐⭐⭐⭐
SEQUENTIAL ORDER ⭐⭐⭐⭐⭐
🎯 Complete Step-by-Step Example
Starting Records
105 → 101 → 108
Step 1 — Unordered File
1
Records are stored as they are inserted.
105 → 101 → 108
Step 2 — Insert 103
2
Find available storage space.
105 → 101 → 108 → 103
Step 3 — Ordered File
101 → 103 → 105 → 108
Step 4 — Search 105
3
Unordered file may scan records one by one.
4
Ordered file can use the ordering to narrow the search.
Step 5 — Insert 102 into Ordered File
5
Find the correct position for 102.
101 → 102 → 103 → 105 → 108
The ordered file requires additional work to maintain the
correct physical/logical ordering.
Final Concept
Unordered:
Fast and simple insertion, but searching may be slower.
Ordered: Searching and ordered processing can be efficient, but maintaining order makes updates and insertions more costly.
Ordered: Searching and ordered processing can be efficient, but maintaining order makes updates and insertions more costly.
❓ Important Questions & Answers
Q1. What is an unordered file?
An unordered file stores records without maintaining a
particular ordering based on a search key. It is commonly
associated with heap file organization.
Q2. What is an ordered file?
An ordered file stores records according to the values of
a specified ordering field or search key.
Q3. Give an example of unordered records.
For Student_ID values 101, 103, 105 and 108, an unordered
file might physically contain 105, 101, 108, 103.
Q4. Give an example of ordered records.
The same records may be stored as 101, 103, 105, 108
when Student_ID is the ordering key.
Q5. Which file is easier for insertion?
An unordered file is generally easier for insertion because
the new record does not have to be placed at a particular
position to preserve ordering.
Q6. Why can searching be faster in an ordered file?
Because the ordering provides information about where the
desired key can occur, allowing techniques such as binary
search when the storage/access method supports it.
Q7. What is the main disadvantage of an ordered file?
Maintaining the ordering can make insertion, deletion and
updates to the ordering key more expensive.
Q8. What happens if the ordering key is updated?
If the new key changes the record's correct position,
the record may need to be moved or the file reorganized
to preserve the ordering.
Q9. What is heap file organization?
Heap file organization stores records without requiring
them to be maintained in a particular sorted order.
Q10. Can binary search be applied directly to an unordered file?
No. Binary search requires the search values to be ordered.
An unordered file normally requires a different access method,
such as a scan or an index.
Q11. Which organization is useful for sequential processing in key order?
An ordered file is useful because records are already arranged
according to the ordering key.
Q12. What is the main difference between unordered and ordered files?
The fundamental difference is record arrangement. Unordered
files do not maintain a specified key order, whereas ordered
files maintain records according to an ordering field.
No comments:
Post a Comment