Slide 6.8: Variable-length record deletion

Slide 6.7: Reclaiming space dynamically
Slide 6.9: Variable-length record deletion (cont.)
Home

Variable-Length Record Deletion

Compared to fixed-length record deletion, variable-length record deletion is much more complicated. The following book information file embedded with a linked list is for the variable-length record deletion:

-1    560  
81    12    File Structures:     An Object-Oriented Approach with C++ |0201874016|94.80|360|
52    105    Learning WML   &   WMLScript |1565929470|17.48|12|
62    169         XML in a Nutshell,     2nd Edition|0596002920|39.95|39|
39    243     Java and 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   Advances 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|

It is structured as follows:

Since we can not compute the byte offset of variable-length records from their RRNs (Relative Record Numbers), the head/last/offsets must contain the byte offsets themselves. Each of them takes five bytes.

The first record is head+' '+last+'\n' where the head is the head (offset) of the avail list and the last is the offset of the last record.

For the remaining records, each record begins with length+' '+offset+' ' where
- the length is the actual record length including '\n' but not including the length+' '+offset+' ' , and
- the offset is the disk offset right before the length.

Some examples of offset computation: the offset -1 means empty; the offset 12 = 5 + 1 + 5 + 1; the offset 105 = 12 + 12 + 81.

The head, last, length, and offset are not part of records. They are used to implement the variable-length record deletion and are not supposed to be seen by users.

^†Note that the above file structure is not the only implementation of variable-length record deletion. Numerous other structures are available.