Free-space bitmap

Free-Space Bitmaps are one method used to track allocated sectors by some file systems. While the most simplistic design is highly inefficient, advanced or hybrid implementations of free space bitmaps are used by some modern file systems.

The simplest form of free space bitmap is a bit array, i.e. a block of bits. In this example, a zero would indicate a free sector, while a one indicates a sector in use. Each sector would be of fixed size. For explanatory purposes, we will use a 4 GiB hard drive with 4096 byte sectors, and assume the bitmap itself is stored elsewhere. The example disk would require 1,048,576 bits, one for each sector, or 128 KiB. Increasing the size of the drive will proportionately increase the size of the bitmap, while multiplying the sector size will produce a proportionate reduction.

When the operating system (OS) needs to write a file, it will scan the bitmap until it finds enough free locations to fit the file. If a 12 KiB file were stored on the example drive, three zero bits would be found, changed to ones, and the data would be written across the three sectors represented by those bits. If the file were subsequently truncated down to 8 KiB, the final sector's bit would be set back to zero, indicating that it is again available for use.

As the drive size grows, the amount of time needed to scan for free space can become unreasonable. To address this, real world implementations of free space bitmaps will find ways to centralize information on free space. One approach is to split the bitmap into many chunks. A separate array then stores the number of free sectors in each chunk, so chunks with insufficient space can be easily skipped over, and the total amount of free space is easier to compute. Finding free space now entails searching the summary array first, then searching the associated bitmap chunk for the exact sectors available.

This approach drastically reduces the cost of finding free space, but it doesn't help with the process of freeing space. If the combined size of the summary array and bitmap is greater than can readily be stored in memory and a large number of files with scattered sectors are freed, an enormous amount of disk access is necessary to find all the sectors, decrement the summary counter and flip the bits back to zero. This greatly reduces the benefits of the bitmap, as it is no longer performing its function of summarizing the free space rapidly without reading from the disk.

...
Wikipedia