Course contentsShow
← Computer Science
Lesson 1405 of 2,87232. File SystemsFree lesson

Free Space Management: Grouping and Counting

Learn advanced techniques that store multiple free block addresses together for efficiency.

Free Space Management: Grouping and Counting

You'll learn two advanced techniques that reduce overhead in tracking free disk blocks by storing multiple addresses together or summarizing runs of contiguous free space.

The Efficiency Problem

In previous lessons, you learned about bitmaps and linked lists for tracking free blocks. But what if you have millions of free blocks? Storing them one-by-one wastes space and time. Grouping and counting are optimization strategies that batch information for efficiency.

Grouping

Grouping stores the addresses of N free blocks in the first free block itself, with the last address pointing to another block containing N more addresses.

Think of it like a treasure map where each chest contains coins and directions to the next chest full of coins. Instead of one linked list node per free block, you pack multiple addresses into each node, dramatically reducing the chain length.

For example, if each block can hold 100 addresses, tracking 10,000 free blocks requires only 100 "index" blocks instead of 10,000 linked-list nodes.

Counting

Counting takes advantage of contiguous free space. Instead of listing blocks 500, 501, 502, 503 individually, you store: (500, 4) — meaning "starting at block 500, there are 4 consecutive free blocks."

This is like saying "rooms 201-215 are vacant" rather than listing each room number separately. When files are deleted, they often leave contiguous runs of free blocks, making this approach very space-efficient.

These techniques are often combined: a grouping structure where each entry contains (start_address, count) pairs.

When to Use Them

  • Grouping: When free blocks are scattered and you want faster allocation without huge linked lists
  • Counting: When deletions create contiguous free regions (common in real file systems)

Key Takeaway: Grouping stores multiple free block addresses per index block, while counting compresses consecutive free blocks into (address, length) pairs—both dramatically reduce the overhead of free space tracking compared to naïve one-address-per-node approaches.