Similar concepts
Pages with this concept
| Similarity |
Page |
Snapshot |
| 69 |
This section will present a formal description of file structures
...Basic terminology Given a set of attributes A and a set of values V,then a record R is a subset of the cartesian product A x V in which each attribute has one and only one value
...R K 1,x 1,K 2,x 2,...The Ki s are keywords functioning as attributes and the value xi can be thought of as a numerical weight
...R Kt 1,Kt 2,...where Kti i s present if xti 1 and is absent otherwise
...Records are collected into logical units called files
...It is difficult in describing file structures to keep the logical features separate from the physical ones
... |
| 70 |
The fields are not necessarily constant in length
...In the same picture I have also shown some fields labelled Pi
...To indicate that a record is the last record pointed to in a list of records we use the null pointer [[logicaland]]... |
| 71 |
To unify the discussion of file structures we need some further concepts
...1 the K pointers are distinct;2 each non null K pointer in L gives the address of a record within L;3 there is a unique record in L not pointed to by any record containing K;it is called the beginning of the list;and 4 there is a unique record in L containing the null K pointer;it is the end of the list
...Hsiao and Harary state condition 2 slightly differently so that no two K lists have a record in common;this only appears to complicate things
...From our previous example:K 1 list:R 1,R 2,R 5 K 2 list:R 2,R 4 K 4 list:R 1,R 2,R 3 Finally,we need the definition of a directory of a file
...Ki,ni,hi,ai 1,ai 2,...We are now in a position to give a unified treatment of sequential files,inverted files,index sequential files and multi list files
...Sequential files A sequential file is the most primitive of all file structures
...The implementation of this file structure requires the use of asorting routine
... |
| 72 |
Its main advantages are:1 it is easy to implement;2 it provides fast access to the next record using lexicographic order
...Its disadvantages:1 it is difficult to update inserting a new record may require moving a large proportion of the file;2 random access is extremely slow
...Sometimes a file is considered to be sequentially organised despite the fact that it is not ordered according to any key
...Inverted files The importance of this file structure will become more apparent when Boolean Searches are discussed in the next chapter
...An inverted file is a file structure in which every list contains only one record
...Index sequential files An index sequential file is an inverted file in which for every keyword Ki,we have ni hi 1 and a 11 <a 21
... |
| 77 |
is no K 3 list,the field reserved for its pointer could well have been omitted
...The multi list is designed to overcome the difficulties of updating an inverted file
...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
...At this point the full power of the notation introduced before comes into play
...Ki,ni,hi,ai 1,...where the hi have beenpicked to ensure that a Ki list does not cross a page boundary
...Ring structures A ring is simply a linear list that closes upon itself
... |
|
|
