13.4

Consider the bitmap representation of the free-space map, where for each block in the file, two bits are maintained in the bitmap. If the block is between 0 and 30 percent full the bits are 00, between 30 and 60 percent the bits are 01, between 60 and 90 percent the bits are 10, and above 90 percent the bits are 11. Such bitmaps can be kept in memory even for quite large files.

  1. Outline two benefits and one drawback to using two bits for a block, instead of one byte as described earlier in this chapter.

  2. Describe how to keep the bitmap up to date on record insertions and deletions.

  3. Outline the benefit of the bitmap technique over free lists in searching for free space and in updating free space information.

  1. Outline two benefits and one drawback to using two bits for a block, instead of one byte as described earlier in this chapter.

The space used is less with 2 bits, and the number of times the free-space map needs to be updated decreases significantly, since many inserts/deletes do no result in any change in the free-space map. However, we have only an approximate idea of the free space available, which could lead both to wasted space and/or increased search cost for finding free space for a record.

  1. Describe how to keep the bitmap up to date on record insertions and deletions.

Every time a record is inserted/deleted, check if the usage of the block has changed levels. In that case, update the corresponding bits. Note that we don’t need to access the bitmaps at all unless the usage crosses a boundary, so in most of the cases there is no overhead.

  1. Outline the benefit of the bitmap technique over free lists in searching for free space and in updating free space information.

When free space for a large record or a set of records is sought, then multiple free list entries may have to be scanned before a proper-sized one is found, so overheads are much higher. With bitmaps, one page of bitmap can store free info for many pages, so I/O spent for finding free space is minimal. Similarly, when a whole block or a large part of it is deleted, bitmap technique is more convenient for updating free space information.