Concepts
Similar pages
| Similarity |
Page |
Snapshot |
| 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
... |
| 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
... |
| 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
... |
|
|
