is no
K3-list, the field reserved for its pointer could well have been omitted.
So could any blank pointer field, so long as no ambiguity arises as to which pointer belongs to which keyword.
One way of ensuring this, particularly if the data values (attribute-values) are fixed format, is to have the pointer not pointing to the beginning of the record but pointing to the location of the next pointer in the chain.
The multi-list is designed to overcome the difficulties of updating an inverted file.
The addresses in the directory of an inverted file are normally kept in record-number order.
But, when the time comes to add a new record to the file, this sequence must be maintained, and inserting the new address can be expensive.
No such problem arises with the multi-list, we update the appropriate K-lists by simply chaining in the new record.
The penalty we pay for this is of course the increase in search time. This is in fact typical of many of the file structures.
Inherent in their design is a trade-off between search time and update time.
Cellular multi-lists
A further modification of the multi-list is inspired by the fact that many storage media are divided into pages, which can be retrieved one at a time.
A K-list may cross several page boundaries which means that several pages may have to be accessed to retrieve one record.
A modified multi-list structure which avoids this is called a cellular multi-list.
The K-lists are limited so that they will not cross the page (cell) boundaries.
At this point the full power of the notation introduced before comes into play.
The directory for a cellular multi-list will be the set ofsequences
(Ki, ni, hi, ai1, .
.
.
aihi)i = 1, 2, .
.
.
, m
where the hi have beenpicked to ensure that a Ki-list does not cross a page boundary.
In an implementation, just as in the implementation of an index-sequential file, further information will be stored with each address to enable the right page to be located for each key value.
Ring structures
A ring is simply a linear list that closes upon itself.
In terms of the definition of a K-list, the beginning and end of the list are the same record.
This data-structure is particularly useful to show classification ofdata.
|