CSC 417, assignment 4

Due Friday, 5 October 2007

In short: Exercises 13.2.6 (a) & (b), 13.3.5 (a,b,c,  f,g,h)

Exercise 13.2.6, p. 621
Assume a block can hold either 3 records, 10 key-pointer pairs, or 50 pointers. We want to find the one movie made by Disney in 1995, there are dense indexes on both studio and year. Assume 51 Disney movies, and 101 movies made in 1995. How many disk I/O's?
  1. Using buckets, intersect the pointers and retrieve the one record. Assume that 'Disney' is among the first 10 studios, and that movies have been made every year since 1910.
  2. Without buckets, use the index on studio to retrieve all the Disney movie records, and select those made in 1995. Assume that no two Disney movies are on the same block. Let's also assume that the first Disney key is in the 15th block of the index.
Exercise 13.3.5 , p. 647 (refers to figure on p. 635, here it is) For (a) - (c), you may draw the path of pointers followed using 3 different colours, and also state how many block reads are required in all.
Figure 13.23
  1. Look up record 41
  2. Look up record 40
  3. Look up all records in the range 20 to 30
For insert and delete, it might be good to draw the portion of the tree that changes. Remember to count the write operations.
  1. Insert a record with key 1
  2. Insert records with keys 14, 15, & 16 (starting with original tree)
  3. Deleter the record with key 23 (again starting with original tree)