Objectives: Introduction Over View of System Analysis and Design
Download 0.94 Mb. View original pdf
|
- Navigate this page:
- 7.3.3 Inverted List Organization
| Chaining File organization requires that relationships be established among data items. It must show how characters form fields, fields form files, and files relate to one another. Establishing relationships is done through chaining or the use of pointers. The example on airline reservation file showed how pointers, link one record to another. Part number retrieves a record. Abetter way is to chain the records by linking a pointer to each. The pointer gives the address of the next part type of the same class. The search method applies similarly to other parts in the file. 7.3.3 Inverted List Organization Like the indexed-sequential storage method, the inverted list organization maintains an index. The two methods differ, however, in the index level and record storage. The indexed- sequential method has a multiple index fora given key, whereas the inverted list method has a single index for each key type. In an inverted list, records are not necessarily stored necessarily stored in particular sequence. They are placed in the data storage area, but indexes are updated for the record keys and location. Data for our flight reservation system has a separate Index area and a data location area. The index area may contain flight number and a pointer to the record present in the data location area. The data location area may have record numbers along with all the details of the flight such as the flight number, flight description, and flight departure time. These are all defined as keys, and a separate index is maintained for each. In the data location area, flight information is in no particular sequence. Assume that a passenger needs information about the Delhi flight. The agent requests the record with the flight description Delhi flight. The Data Base Management System (DBMS) then reads the single-level index sequentially until it finds the key value for the Delhi flight. This value may have two records associated with it. The DBMS essentially tells the agent the departing time of the flight. Looking at inverted-list organization differently, suppose the passenger requests information’s on a Delhi flight that departs at 8:15. The DBMS first searches the flight description index for the value of the Delhi flight It finds both the records. Next it searches the flight departure index for these values. It finds that one of them departs at 10:10, but the other departs at 8:15. The later record in the data location area is displayed for followup. It can be seen that inverted lists are best for applications that request specific data on multiple keys. They are ideal for static files because additions and deletions cause expensive pointer updating. Download 0.94 Mb. Share with your friends:
|