| Indexing Review Part 2 |
| The following review questions were covered in Labs 02 and 03 and are questions taken from the course website. NOT ALL questions from the course website were discussed in lab. Please note that the information presented here does not necessarily represent a complete answer to the review question. The information is intended to spark student's memory for those who attended lab OR provide a base (hint) from where to start for those students who did not attend lab.
| Question 1: If one has an indexed record file, why might one want to sort the records themselves (at least two reasons)? |
|  | To restore locality of records for sequential processing and to compact the file. |
| Question 2: How can one effect a binary search on a varying length record file? |
|  | Create an index file and perform the binary search on it. |
| Question 3: Discuss the relative advantages and disadvantages of using the same free list for both the primary and secondary indices of an indexed record file when the keys in both indices are different sizes? |
|  | ADVANTAGE - only one file to keep track of (when a record is deleted the free space of both indices can be dealt with at the same time). DISADVANTAGE - because the indices are different sizes, we need to come up with a way of accessing the free list (more complicated). |
| Question 4: Suppose we have an indexed varying length record file stored in binary format. The records are blocked so that each read to fill one buffer retrieves a number of records and no record crosses a block boundary. What would the relative advantages and disadvantages of keeping the block number of the record in the index as opposed to the actual byte offset? |
|  | ADVANTAGE - the index would be smaller, work is offloaded to the OS DISADVANTAGE - must deal with search for records within each block |
| Question 5: What would eventually happen to a dynamic, indexed, varying-length record file if we did not manage the free space ourselves with some sort of free list? |
|  | PLACEMENT OF NEW RECORDS - would have to go at the end of the file EFFICIENCY OF SEARCHES - because of index, this will not be affected SEQUENTIAL FILE UPDATES - will not be possible (direct access will not be affected) FILE SIZE - will grow rapidly OVERALL PROCESSING SPEED - will degrade overtime (if file is large enough, may cause thrashing) |

BACK

© Copyright 2002
Questions? Please Email: gwen@cpsc.ucalgary.ca
Last modified October 7, 2002