File Organization in DBMS

12
0

Introduction

A college office needs to pull up student 105 to correct a name. Later that day, it needs every student record with an ID from 103 through 105. Both requests use the same table, but they look for data in different ways. One needs an exact match. The other needs a range.

How much work the database does for each request depends partly on how the records are stored.

What Is File Organization?

File organization is how a database arranges records across data pages. A page can hold several records, so when we look for a student, the first question is which page to check.

Say these six records arrive in this order. We’ll use them for all three layouts.

student_id

student_name

104

Kabir

101

Asha

106

Nila

102

Ravi

105

Omar

103

Meera

Heap File Organization

In a heap file, records can go on any page with enough free space. Say each page holds two records and we fill the pages in the order the students arrive.

Data page

Student IDs

P0

104, 101

P1

106, 102

P2

105, 103

Now look for IDs 103 through 105. The first page gives us 104. The next page has no matches, but we still have to check P2, where 105 and 103 are stored. Without a suitable index, the database has to scan all three pages to find every match.

That freedom is handy when adding records. If a slot opens up on P0, the next student can go there regardless of their ID.

Sorted File Organization

Store those same records in student_id order and the pages look different.

Data page

Student IDs

P0

101, 102

P1

103, 104

P2

105, 106

This time, once the database locates 103 on P1, it can keep reading through 104 and 105. When it reaches 106, it can stop. The rest of the IDs will be outside the range.

Now suppose student 100 arrives and P0 is full. The new record belongs ahead of 101, so the database has to make room or handle the insert through an overflow area, depending on how the file is implemented.

Heap vs Sorted File Organization

Heap vs Sorted File Organization

Hash File Organization

For the office’s first request, we only need student 105. A hash file uses the student ID to choose a bucket. In this example, divide the ID by 3 and use the remainder as the bucket number.

Bucket

Student IDs

0

102, 105

1

106, 103

2

104, 101

Since 105 MOD 3 = 0, the database goes straight to bucket 0. It still checks the IDs inside that bucket because 102 also leaves a remainder of 0. Two different IDs landing in the same bucket is a hash collision.

Try the range request again and the trade-off becomes clear. ID 103 is in bucket 1, 104 is in bucket 2, and 105 is in bucket 0. The hash function tells us where to look for an exact ID, but it gives us no useful order for reading a range.

Key Differences at a Glance

File organization

Where a new record goes

What the layout helps with

Trade-off

Heap

A page with room

Inserting records without maintaining key order

Finding matches may require scanning the file

Sorted

In key order

Reading a range on the ordering field

Inserts can take extra work

Hash

A bucket chosen from the key

Finding an exact match on the hash key

Collisions add checks, and nearby keys can land in different buckets

File Organization and Indexes

The college could keep the student records in a heap file and create a separate index on student_id. Student 105 would still live on P2 in our example, but the index would give the database a way to locate that record without scanning the heap.

If the office wants the report in student ID order, the query should use ORDER BY student_id. That is how SQL specifies the order of the result.

Summary

Think about the request the database handles most often. A heap file is handy when records arrive frequently and can go wherever there’s room. A sorted file helps when readers ask for a run of IDs. A hash file helps when the usual request is to find one exact ID.

CS Core

Read Similar Blogs

Comments0