Slide 6.8: Variable-length record deletion
Slide 6.10: Storage fragmentation
Home

Variable-Length Record Deletion (Cont.)

In the beginning, the head of the avail list is -1 (empty). When a record is deleted, it is marked by an asterisk, a bar, and a link (the offset of the next deleted record) and is added to the list. After some operations applied to the book information file, its contents may become the following: 

243   560  
81    12    File Structures:     An Object-Oriented Approach with C++ |0201874016|94.80|360|
52    105   *|-1    g WML   &   WMLScript |1565929470|17.48|12|
62    169         XML in a Nutshell,     2nd Edition|0596002920|39.95|39|
39    243   *|465   nd XSLT |0596001436|26.37|890|
84    294   WAP Servlets:   Developing Dynamic Web Content With Java and WML|047139307|32.99|4|
63    390      WAP Development with WML and WMLScript|0672319462|18.99|56|
83    465   *|105    in Security and Payment Methods for Mobile Commerce|1591403456|89.95|182|
79    560   M Commerce:   Technologies, Services, and Business Models |0471135852|23.09|5|

where the head of the avail list is an offset 243 and there are three deleted records. The avail list is 
         head = 243 —> 465 —> 105 —> -1 = end
A record is later requested to be added to the book file. Instead of appending the record at the end of file, a record in the avail list is reclaimed to save space.

They are many ways, placement strategies, to select a record to be replaced. They will be discussed later. A simple placement method, first-fit, is explained here. It sequentially searches the avail list and selects the first available record slot large enough to hold the new record. For example, the previous file becomes the following after the addition: 

243   560  
81    12    File Structures:     An Object-Oriented Approach with C++ |0201874016|94.80|360|
52    105   *|-1    g WML   &   WMLScript |1565929470|17.48|12|
62    169         XML in a Nutshell,     2nd Edition|0596002920|39.95|39|
39    243   *|105   nd XSLT |0596001436|26.37|890|
84    294   WAP Servlets:   Developing Dynamic Web Content With Java and WML|047139307|32.99|4|
63    390      WAP Development with WML and WMLScript|0672319462|18.99|56|
83    465   Dynamic WAP Application Development     |1930110081|34.59|18|                     
79    560   M Commerce:   Technologies, Services, and Business Models |0471135852|23.09|5|

where the newly added record is appended with spaces until its length reaches 83. If no deleted records are large enough to store the incoming record, it is then appended at the end of the file.