A table on disk is a file. How you arrange it decides how fast you find a row.
Every query this course wrote eventually has to read actual bytes from disk. This lesson steps down to that physical level from Unit 1, and shows how a table's rows are physically organized into a file before any index exists.
After this lesson
You should be able to
- Explain why disk access, not CPU speed, is usually the bottleneck for a database query.
- Distinguish heap file organization from sorted file organization, with a trade-off for each.
Disk is slow the way a library shelf is slow compared to your desk
Everything this course discussed so far — relations, SQL, transactions — ultimately lives on disk, because a database must survive a power-off, exactly as Unit 1 established. Reading from disk takes vastly longer than reading from memory, the same way walking to a library shelf takes vastly longer than glancing at a paper already on your desk. A DBMS's performance is dominated by how many disk accesses a query needs, not by how clever its arithmetic is.
Data moves between disk and memory in fixed-size chunks called blocks or pages, not one row at a time — reading one row from a block costs the same disk access as reading every row in that block. This single fact motivates almost everything in this unit: organizing rows and building indexes are both, at heart, strategies to minimize the number of blocks a query must touch.
Two ways to lay rows out inside a file
Heap file organization places rows in no particular order — a new row is simply appended wherever there is free space, making insertion very cheap. But finding a specific row without an index means scanning the entire file block by block, exactly like the messy WhatsApp chat from Unit 1's opening lesson.
Sorted file organization keeps rows physically ordered by some key, which makes a search for a specific value dramatically faster using binary search over blocks — directly reusing the CS205ES binary search algorithm, just applied to disk blocks instead of an in-memory array. The cost shows up on insertion: keeping rows sorted means a new row may need everything after it physically shifted to make room, which is expensive compared to a heap file's simple append.
Try it yourself
A logging system inserts thousands of new rows per second and almost never searches old rows. Which file organization fits better, heap or sorted, and why?
Need a hint?
The workload described is almost entirely insert-heavy, with essentially no search requirement.
Check the worked solution
Heap file organization fits better. Since inserts dominate and searches are rare, the cheap append cost of a heap file is exactly what this workload needs, and the search penalty barely matters since search almost never happens. Sorting the file would add continuous shifting cost for a search speed benefit that is rarely used.
Quick check
Why does a DBMS's real-world performance depend heavily on the number of disk block accesses a query requires, rather than purely on CPU computation?
Why this lesson exists
Syllabus mapping
Data on External Storage, File Organization and Indexing
Maps to course outcome CO4.