Homework 8
Document last modified: 

1. (3) Explain under what circumstances, if any, redundant DISK-WRITE or DISK-READ operations are performed during the course of executing a call to B-TREE-INSERT. A redundant DISK-READ is reading a page that is already in memory. A redundant DISK-WRITE is writing an identical page to one that has already been written. Hint: Examine B-TREE-INSERT and the methods used.

    

2. (3) Give a method to return the maximum key of a B-tree, given a root node of a subtree. Include any disk access.
    
3. (3) The following method will traverse a B-tree, visiting all entries in order of keys (smaller keys first). It assumes that a complete node is read at a time (all keys and children pointers but not the children nodes of a single node are read from the disk) and also that h (height) nodes can be held in memory at a time.

   For example:

       Disk_Read( x )

   reads the keys and children pointers of node x.

   Disk_Read ( c_i[ x ])

   reads the keys and children pointers of node c_i[ x ].

   a) Modify the algorithm to implement a more realistic assumption that only the root and the current node is held in memory.

   b) What is the number of disk accesses for your traversal method on Figure 18.7e? Assume only the root and the current node are in memory.

   void B_Tree_Traverse (Node x)       // pre: x points to root node of subtree    if leaf[ x ] then                       // at a leaf, print      for  i ¬ 1 to n[ x ]           print keyi [x]    else      for  i ¬ 1 to n[ x ]                 // print left subtree first          Disk_Read ( ci[ x ])         B_Tree_Traverse( ci[ x ] )         print keyi [x]      Disk_Read ( cn[x]+1[ x ])      B_Tree_Traverse( cn[x]+1[ x ] )

    

4. (8) a) Give a method that will traverse a B-tree, visiting all entries in reverse order of keys (larger keys first). Assume that a complete node is read at a time (all keys and children pointers but not the children nodes of a single node are read from the disk). Also assume that h (height) nodes can be held in memory at a time. For example:

       Disk_Read( x )

   reads the keys and children pointers of node x.

   Disk_Read ( c_i[ x ])

   reads the keys and children pointers of node c_i[ x ]

   b) What is the number of disk accesses for your traversal method on Figure 18.7e? Assume the root and height nodes are always in memory.

   c) What is a good estimate of the maximum number of disk accesses for your traversal on a B-tree in general in terms of t and h? Examine the recursion tree in Figure 18.4 to help understand the order of growth.

    

5. (3) As a function of the minimum degree t derive the maximum number of keys that can be stored in a B-tree of height h.

Turn in

1. Cover sheet with your name, C455, date, and Homework 8.
2. Typed or neat handwritten answers.