Maintaining a Sequence Set (Cont.)

---

3. Underflow: Deletion of records can cause a block to be less than half full (underflow), which can lead to either of two solutions:
   
   
   1. If a neighboring node is also half full, merge the two nodes, freeing one up for reuse.
   2. If the neighboring nodes are more than half full, redistribute records between the nodes to make the distribution more even.
   
   After deleting the record for DAVIS, Block 4 underflows and is then merged with Block 3 which is freed up for reuse.
   
   

There are costs associated with this avoidance of sorting:

• Once insertions are made, the file takes up more space than an unblocked file because of internal fragmentation within a block.


• The order of the records is not necessarily physically sequential throughout the file. The maximum guaranteed extent of physical sequentiality is within a block. This leads us to the important question of selecting a block size.

The block size can not be arbitrary large because computer memory is limited. One reasonable suggestion for deciding on a block size is to make each block equal to the size of a disk cluster, which is the minimum number of sectors allocated at a time. The reason of clustering is that it guarantees a minimum amount of physical sequentiality.