Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 4

Heap File: Implementation and I/O Analysis

Recommended resources

Hello! Welcome back to our course on database system internals.

In our last lesson, we took a microscopic view, dissecting a single block of data to design an efficient slotted page layout. We saw how this structure elegantly handles variable-length records and provides stable record identifiers, (page_id, slot_id), which are crucial for building indexes.

Today, we zoom out. A single page is rarely enough to store a whole table, so we need a way to organize a collection of pages. This lesson addresses the learning outcome: Implement a heap file structure supporting record insertion and full scans, analyzing its I/O cost. A heap file is the simplest and most fundamental way to store a table's data, serving as the foundation upon which more complex structures are built.

Let's begin by defining what a heap file is and the challenges it must solve.

What is a Heap File?

At its core, a heap file is an unordered collection of pages containing a table's records. The "heap" here simply means an unordered pile; it's not related to the heap data structure used for priority queues. Since there's no ordering, records can be placed on any page with sufficient space.

The main challenge for a heap file implementation is management:

  1. Tracking Pages: How does the system know which pages on disk belong to this specific file?
  2. Tracking Free Space: How does the system efficiently find a page with enough free space to insert a new record?

Let's explore two common strategies to address these challenges.

Lec 4 5 Part 1 Files

This short segment from a UC Berkeley database lecture introduces the core concepts of file organization and distinguishes between heap files, sorted files, and indexes.

Watch from the beginning to 4:24. This will set the stage by explaining how logical tables are mapped to physical files and pages, and it will formally define what an unordered heap file is.

Strategy 1: The Linked List Approach

A straightforward way to organize pages is to link them together, forming a list. The file's header page would store a pointer (a PageId) to the head of this list. To manage free space, we could maintain two separate linked lists: one for pages with free space and one for full pages.

Heap File Structure
This diagram from Swarthmore's CS44 course illustrates the linked-list heap file architecture. A header page contains metadata and points to a linked list of data pages.

This seems simple to implement, but it has a significant performance drawback. To explore this, watch the next segment of the video.

Lec 4 5 Part 1 Files

This clip explains the linked-list implementation of a heap file and highlights its critical performance flaw related to insertions.

Watch from 4:24 to 5:44. Focus on the 'fatal flaw': why is finding a page with enough space potentially very expensive in terms of I/O?

I/O Cost Analysis: Linked List

Let's analyze the performance of this approach, where 1 I/O means reading or writing one page from/to disk.

  • Full Scan: To read all records, we must visit every data page. If there are N data pages in the file, a full scan costs N I/Os.
  • Insertion (Worst Case): To insert a new record, we need to find a page with free space. In the worst case, we might have to traverse the entire list of pages with free space, reading each one from disk, only to find that none have enough room. This would force us to allocate a new page. The cost can be proportional to the number of pages in the file, which is inefficient.

Strategy 2: The Page Directory Approach

To solve the insertion problem, we can introduce a level of indirection: a page directory. Instead of data pages pointing to each other, we have special directory pages that contain an array of entries. Each entry stores:

  1. A PageId pointing to a data page.
  2. The amount of free space on that data page.

Now, to find a page for insertion, the DBMS only needs to scan the directory pages, which are much smaller and more likely to be cached in memory.

Lec 4 5 Part 1 Files

This final clip from the Berkeley lecture presents the more efficient page directory implementation.

Watch from 5:44 to 7:08. Understand how the directory structure helps locate a suitable page for insertion much faster than the linked-list approach.

I/O Cost Analysis: Page Directory

  • Full Scan: The cost is still N I/Os to read all N data pages. The directory isn't needed for a full scan.
  • Insertion (Worst Case): We first search the directory pages to find a data page with enough space. Let D be the number of directory pages. In the worst case, we read all D directory pages. Once we find an entry, we need 1 I/O to read the target data page, and 1 I/O to write it back after inserting the record. We also need to update the free space count in the directory, costing 1 I/O to write the modified directory page.
    • Total Cost = D (read directory) + 1 (read data page) + 1 (write data page) + 1 (write directory page) = D + 3 I/Os.

This is a huge improvement, as the number of directory pages D is typically much smaller than the number of data pages N.

To solidify your understanding, let's work through a quick problem.

Test your understanding!

You have a heap file implemented with a page directory. The directory consists of 4 header pages. Each header page points to 100 data pages. You need to insert a new record. In the worst-case scenario, the only data page with enough free space is pointed to by an entry on the very last header page.

What is the I/O cost to insert this record? Assume you don't need to allocate a new page.

Show answer

The I/O cost calculation is as follows:

  1. Read Header Pages: To find the entry, you must read all 4 header pages. Cost: 4 I/Os.
  2. Read Data Page: You read the specific data page that has space. Cost: 1 I/O.
  3. Write Data Page: After inserting the record into the page in memory, you write the modified page back to disk. Cost: 1 I/O.
  4. Write Header Page: You must update the free space count for that data page in the last header page and write it back to disk. Cost: 1 I/O.

Total Worst-Case Cost = 4 + 1 + 1 + 1 = 7 I/Os.

This is exactly the problem presented in the Berkeley CS186 course notes, which you can find in the resource "Disk and Files" (LINK).

An Engineer's View: Implementation and Real-World Systems

Now that you understand the concepts, let's think about how to implement this. Your background in C++ and data structures is perfect for this. We'll focus on the simpler linked-list approach, as it's a common starting point in database coursework and clearly illustrates the necessary interactions.

CS44 Lab 4: SwatDB Heap File

This lab guide from Swarthmore College's database course provides a detailed blueprint for implementing a HeapFile class in C++. It's an excellent resource for understanding the practical details.

Read sections 4.2 ('Heap File Header Page') and 4.3 ('HeapFile Class'), paying close attention to the description of the insertRecord method. You don't need to read the code, but focus on the algorithmic steps described. This will give you a clear mental model of the implementation logic.

Based on that reading, the logic for the two core heap file operations would be:

  • insertRecord(record):
    1. Get the header page to find the start of the data page list.
    2. Traverse the linked list of data pages. For each page:
      • Read the page into the buffer pool.
      • Check if it has enough free space for record.
      • If yes, call the page's internal insertRecord method (like the one we designed in the last lesson), update the header, and return.
    3. If no page had enough space:
      • Allocate a new page.
      • Initialize it as an empty data page.
      • Insert record into this new page.
      • Add the new page to the head of the linked list (by updating pointers in the header and the old first page).
  • scan() (Full Table Scan):
    1. Create an iterator object.
    2. The iterator gets the first data page from the file header.
    3. It then iterates through all records on the current page.
    4. When the records on the current page are exhausted, it follows the "next page" pointer to fetch the next page in the list.
    5. This continues until it reaches the end of the page list.

From Theory to Practice: Free Space Maps in PostgreSQL

Real-world systems use sophisticated variants of the page directory. PostgreSQL, for example, uses a dedicated file called a Free Space Map (FSM) for each table. The FSM compactly stores the amount of free space available on each of the table's pages. This allows the system to quickly find a page for an insertion without scanning the data pages themselves.

Let's watch a fantastic demo that shows this in action.

#03 - Database Storage: Files & Pages ✸ Neon Database Talk (CMU Intro to Database Systems)

This CMU lecture segment includes a live demo in PostgreSQL showing how inserts, deletes, and the VACUUM command affect the file structure and the Free Space Map. This provides a tangible look at how a production system manages heap files.

Watch from 44:01 to 58:41. Don't worry about memorizing the SQL commands. Focus on the concepts: how the system keeps track of pages, how it finds free space after deletions, and the role of the VACUUM process in updating the Free Space Map (the directory).

The key insight from the video is that the free space map (the directory) doesn't always have to be perfectly up-to-date. The system can tolerate some staleness and use background processes like VACUUM to reconcile it over time. This is a classic engineering trade-off between write-time overhead and read-time efficiency.

Conclusion

In this lesson, we bridged the gap between a single page and a complete table file. We learned that a heap file is the most basic storage structure, and its performance, particularly for insertions, depends heavily on how it manages its pages and free space.

Key Takeaways:

  • A heap file stores a table's records in an unordered collection of pages.
  • The two main implementation strategies are a linked list of pages and a page directory.
  • The linked list approach is simple but can have high I/O costs for insertions, as it may require scanning many data pages.
  • The page directory approach is more efficient for insertions because it keeps metadata about free space separate from the data, reducing the number of I/Os needed to find a spot for a new record.
  • A full table scan on a heap file requires reading every data page, costing N I/Os for a file with N pages, regardless of the implementation strategy.
  • Real-world systems like PostgreSQL use optimizations like a Free Space Map (FSM), which acts as a form of page directory.

Preview of the Next Lesson:

So far, we've talked about reading and writing pages as if they magically appear in memory when we need them. The component responsible for this magic is the Buffer Pool Manager. In our next lesson, we will dive into its crucial role, exploring how it caches disk pages in memory to minimize expensive I/O and satisfy the data requests of the query execution engine.