Free-space bitmap

Free-space bitmaps are one method used to track allocated sectors by some s. 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 that the bitmap itself is stored elsewhere. The example disk would require 1,048,576 bits, one for each sector, or 1 MiB. 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. Simple: Each bit directly corresponds to a sector. Fast random-access allocation check: Checking whether a sector is free is as simple as checking the corresponding bit. Fast deletion: Data need not be overwritten on delete; flipping the corresponding bit is sufficient. Fixed cost: Both an advantage and disadvantage. Other techniques to store free-space information have a variable amount of overhead depending on the number and size of the free-space extents. Bitmaps can never do as well as other techniques in their respective ideal circumstances, but don't suffer pathological cases either. Since the bitmap never grows, shrinks or moves, fewer lookups are required to find the desired information.