The problem of managing the blocks of an external data fi le indexed by either a B-tree or an external hashing scheme is similar to that of managing memory for internal structures. When an external structure such as a data fi le needs more memory (for example, to insert a new record), it gets a new block from a free list that the system manages. That is, if the fi le contains n blocks, the system can allocate to it an ( n + 1) th block. When the fi le no longer needs a block, you can deallocate it and return it to the system. The complication in the management of external storage is that a block allocated to a fi le may have available space interspersed with data. For example, after you have removed a record from the middle of a data fi le, the block that contained that record will have space available for at least one record. Therefore, you must be able to keep track of blocks that have space available for one or more records as well as recognize when blocks are completely empty (so that you can return them to the system). Assuming the existence of allocate Block and return Block functions that get empty blocks from and return empty blocks to the system, write pseudo code implementations of the following external memory-management functions:
What data structure is appropriate to support these operations? You may assume that you can distinguish slots of a block that do not contain a record from those that do. You can make this distinction either by having a convention for null values within a record or by adding an empty/full flag.