Give brief and clear answers to the following: NOTE: THE ANSWER SHOULD BE MORE THAN FIVE LINES AND WITH CLEAR EXPLANATION. (a) Explain how hashing can be used to build an index (b) Explain why a primary index file might be smaller than the data file (c) Give an example of a situation where hashing indexes might work better than a B tree index (d) Explain the main advantage(s) and disadvantage(s) of keeping the data file sorted. (e) Explain the main advantage B-trees have over a multilevel index of the type shown in Figure 17.6 (f) Explain why writes to a log disk might be faster than writes to the disk containing the database (g) Since indexes speed up searches, explain why the DBMS does not automatically create an index for every column of a table (h) 16.35 parts (a) and (b), but with block size being 1024 bytes and the Address requires 60 bytes (i) Give an example of a situation where we would prefer to use a B+ tree index instead of a B tree index (j) Explain how multileval indexing improves the efficiency of an index file
blocks will be b Tbo-99/273)1-5 blocks, and the number of third level blocks will be b(b2lfo)(5/273)-1 block. Hence, the third level is the top level of the index, and 3. To access a record by searching the multilevel index we must access one block at each level plus one block from the data file, so we need t + 1-3 + 1-4 block accesses. Compare this to Example 3, where 12 block accesses were needed when a single-level index and binary search were used. Notice that we could also have a multilevel primary index, which would be non dense. Exercise 17.18(c) illustrates this case, where we must access the data block from the file before we can determine whether the record being searched for is in the file. For a dense index, this can be determined by accessing the first index level The numbering scheme for index levels used here is the reverse of the way levels are commonly defined for tree data structures. In tree data structures, is referred to as level 0 (zero), 2-1 is level 1, and so on 17.2 Multilevel Indoxes 615 Figure 17.6 A two-level primary index resembling ISAM (indexed sequential accoss method) organization. Two-level index Data file First (base) koy fiold 15 24 12 15 21 Second (top) 35 39 36 51 52 63 71 80 63 71 78 80 82 89 616 Chapter 17 Indexing Structures for Files and Physical Database Design (without having to access a data block), since there is an index entry for every record in the file. blocks will be b Tbo-99/273)1-5 blocks, and the number of third level blocks will be b(b2lfo)(5/273)-1 block. Hence, the third level is the top level of the index, and 3. To access a record by searching the multilevel index we must access one block at each level plus one block from the data file, so we need t + 1-3 + 1-4 block accesses. Compare this to Example 3, where 12 block accesses were needed when a single-level index and binary search were used. Notice that we could also have a multilevel primary index, which would be non dense. Exercise 17.18(c) illustrates this case, where we must access the data block from the file before we can determine whether the record being searched for is in the file. For a dense index, this can be determined by accessing the first index level The numbering scheme for index levels used here is the reverse of the way levels are commonly defined for tree data structures. In tree data structures, is referred to as level 0 (zero), 2-1 is level 1, and so on 17.2 Multilevel Indoxes 615 Figure 17.6 A two-level primary index resembling ISAM (indexed sequential accoss method) organization. Two-level index Data file First (base) koy fiold 15 24 12 15 21 Second (top) 35 39 36 51 52 63 71 80 63 71 78 80 82 89 616 Chapter 17 Indexing Structures for Files and Physical Database Design (without having to access a data block), since there is an index entry for every record in the file
